Javascript Priority Queue 오름 차순

Javascript는 Priority Queue 내장함수가 없어서 직접 만들어서 써야 한다.

Binary 방식으로 메모리를 관리 한다.

코드를 만들 때 주의 해야 할 것은

1. pop 할때 내부 Array의 사이즈를 항상 1로 유지 하는 것

2. Array 자체의 사이즈가 2일 때는 1상태로 돌려주는 부분이다.

class PriorityQ {
    constructor() {
        this.arr = new Array();
        this.arr.push('');
    }

    push(cost, elem) {
        this.arr.push([cost, elem]);
        let curPosition = this.arr.length-1;

        while (1 < curPosition && this.arr[curPosition][0] < this.arr[Math.floor(curPosition / 2)][0]) {
            let tmp = this.arr[Math.floor(curPosition / 2)];
            this.arr[Math.floor(curPosition / 2)] = this.arr[curPosition];
            this.arr[curPosition] = tmp;
            curPosition = Math.floor(curPosition / 2);
        }
    }

    pop(){
        if(this.arr.length <= 1) return null;
        let curPosition = 1;
        let last = this.arr[curPosition];
        if(2 < this.arr.length) this.arr[curPosition] = this.arr.pop();
        else this.arr.pop();

        while (curPosition * 2 < this.arr.length) {
            if (curPosition * 2 + 1 < this.arr.length && this.arr[curPosition * 2 + 1][0] <= this.arr[curPosition * 2][0] && this.arr[curPosition * 2 + 1][0] < this.arr[curPosition][0]) { //양쪽이 있고 왼쪽이 작을 경우
                    let tmp = this.arr[curPosition * 2 + 1];
                    this.arr[curPosition * 2 + 1] = this.arr[curPosition];
                    this.arr[curPosition] = tmp;
                    curPosition = curPosition * 2 + 1;
            } else if (this.arr[curPosition * 2][0] < this.arr[curPosition][0]){
                let tmp = this.arr[curPosition * 2];
                this.arr[curPosition * 2] = this.arr[curPosition];
                this.arr[curPosition] = tmp;
                curPosition = curPosition * 2;
            } else {
                break;
            }
        }

        return last;
    }
}

 사용 방법은 아래와 같다.

여기서 elem은 어떤 객체든 상관은 없다.

let pq = new PriorityQ();
pq.push(1000, [1, 1]);
pq.push(1, [1, 1]);
pq.push(2, [1, 1]);
pq.push(3, [1, 1]);
pq.push(-10000, [1, 1]);
pq.push(19999, [1, 1]);
pq.push(4, [1, 1]);
pq.push(0, [1, 1]);


console.assert(pq.pop()[0]==-10000, '1 fail');
console.assert(pq.pop()[0]==0, '2 fail');
console.assert(pq.pop()[0]==1, '3 fail');
console.assert(pq.pop()[0]==2, '4 fail');

pq.push(-1000, [1, 1]);
pq.push(1, [1, 1]);
pq.push(2, [1, 1]);
pq.push(3, [1, 1]);

console.assert(pq.pop()[0]==-1000, '5 fail');
console.assert(pq.pop()[0]==1, '6 fail');
console.assert(pq.pop()[0]==2, '7 fail');
console.assert(pq.pop()[0]==3, '8 fail');
console.assert(pq.pop()[0]==3, '9 fail');

pq.push(-10000, [1, 1]);
console.assert(pq.pop()[0]==-10000, '10 fail');
pq.push(200000, [1, 1]);

console.assert(pq.pop()[0]==4, '11 fail');
console.assert(pq.pop()[0]==1000, '12 fail');
console.assert(pq.pop()[0]==19999, '13 fail');
console.assert(pq.pop()[0]==200000, '14 fail');
console.assert(pq.pop()==null, '15 fail');

Max Heap과 Min Heap을 선택 할 수있는 부분을 넣어서 업데이트 한다.

class PriorityQ {
    constructor(asc = true) { //Min heap true, Max heap false
        this.arr = new Array();
        this.arr.push('');
        this.asc = asc;
    }

    _compare(a, b){
        if (this.asc) {
            return a < b;
        } else {
            return a > b;
        }
    }

    _compareEq(a, b){
        if (this.asc) {
            return a <= b;
        } else {
            return a >= b;
        }
    }

    push(cost, elem) {
        this.arr.push([cost, elem]);
        let curPosition = this.arr.length-1;

        while (1 < curPosition && this._compare(this.arr[curPosition][0], this.arr[Math.floor(curPosition / 2)][0]) ) {
            let tmp = this.arr[Math.floor(curPosition / 2)];
            this.arr[Math.floor(curPosition / 2)] = this.arr[curPosition];
            this.arr[curPosition] = tmp;
            curPosition = Math.floor(curPosition / 2);
        }
    }

    pop(){
        if(this.arr.length <= 1) return null;
        let curPosition = 1;
        let last = this.arr[curPosition];
        if(2 < this.arr.length) this.arr[curPosition] = this.arr.pop();
        else this.arr.pop();

        while (curPosition * 2 < this.arr.length) {
            if (curPosition * 2 + 1 < this.arr.length && this._compareEq(this.arr[curPosition * 2 + 1][0], this.arr[curPosition * 2][0]) && this._compare(this.arr[curPosition * 2 + 1][0],this.arr[curPosition][0])) { //양쪽이 있고 왼쪽이 작을 경우
                let tmp = this.arr[curPosition * 2 + 1];
                this.arr[curPosition * 2 + 1] = this.arr[curPosition];
                this.arr[curPosition] = tmp;
                curPosition = curPosition * 2 + 1;
            } else if (this._compare(this.arr[curPosition * 2][0],this.arr[curPosition][0])){
                let tmp = this.arr[curPosition * 2];
                this.arr[curPosition * 2] = this.arr[curPosition];
                this.arr[curPosition] = tmp;
                curPosition = curPosition * 2;
            } else {
                break;
            }
        }

        return last;
    }
}