[Greedy]우선순위 큐

배열

const Pq = class {
    constructor() {
        this.arr = [];
    }
    get () {
        return this.arr.pop();
    }
    put (x) {
        var isPush = false;
        for (var i=0; i<this.arr.length; i++) {
            if (this.arr[i] <= x) {
                this.arr.splice(i,0,x);
                isPush = true;
                break;
            }
        }
        if (!isPush) this.arr.push(x);
    }
}

var pq = new Pq();
pq.put(x);
pq.get();

 

힙

힙 구현이 빠르다고 하여 다른 블로그를 참고해서 구현해봄

다들 index 계산 때문에 0번째를 null로 채우고 0번째는 안쓰는 방식을 택함

나는 0번째부터 모두 쓰는걸로 구현해봄

class MaxHeap {
    constructor() {
        this.heap = [];
    }
    put(value) {
        this.heap.push(value);
        let currentIndex = this.heap.length - 1;
        let parentIndex = Math.floor((currentIndex - 1) / 2);
        while (parentIndex !== -1 && this.heap[parentIndex] < value) {
            const temp = this.heap[parentIndex];
            this.heap[parentIndex] = value;
            this.heap[currentIndex] = temp;
            currentIndex = parentIndex;
            parentIndex = Math.floor((currentIndex - 1) / 2);
        }
    }

    pop() {
        if (this.heap.length == 1) return this.heap.pop();

        let returnValue = this.heap[0];
        this.heap[0] = this.heap.pop();
        let currentIndex = 0;
        let leftIndex = 1;
        let rightIndex = 2;
        while (this.heap[currentIndex] < this.heap[leftIndex] ||
               this.heap[currentIndex] < this.heap[rightIndex]) {
            const temp = this.heap[currentIndex];
            if (this.heap[leftIndex] < this.heap[rightIndex]) {
                this.heap[currentIndex] = this.heap[rightIndex];
                this.heap[rightIndex] = temp;
                currentIndex = rightIndex;
            } else {
                this.heap[currentIndex] = this.heap[leftIndex];
                this.heap[leftIndex] = temp;
                currentIndex = leftIndex;
            }
            leftIndex = currentIndex * 2 + 1;
            rightIndex = leftIndex + 1;
        }
        return returnValue;
    }
}

class MinHeap {
    constructor() {
        this.heap = [];
    }
    put(value) {
        this.heap.push(value);
        let currentIndex = this.heap.length - 1;
        let parentIndex = Math.floor((currentIndex - 1) / 2);
        while (parentIndex !== -1 && this.heap[parentIndex] > value) {
            const temp = this.heap[parentIndex];
            this.heap[parentIndex] = value;
            this.heap[currentIndex] = temp;
            currentIndex = parentIndex;
            parentIndex = Math.floor((currentIndex - 1) / 2);
        }
    }

    pop() {
        if (this.heap.length == 1) return this.heap.pop();

        let returnValue = this.heap[0];
        this.heap[0] = this.heap.pop();
        let currentIndex = 0;
        let leftIndex = 1;
        let rightIndex = 2;
        while (this.heap[currentIndex] > this.heap[leftIndex] ||
               this.heap[currentIndex] > this.heap[rightIndex]) {
            const temp = this.heap[currentIndex];
            if (this.heap[leftIndex] < this.heap[rightIndex]) {
                this.heap[currentIndex] = this.heap[leftIndex];
                this.heap[leftIndex] = temp;
                currentIndex = leftIndex;
            } else {
                this.heap[currentIndex] = this.heap[rightIndex];
                this.heap[rightIndex] = temp;
                currentIndex = rightIndex;
            }
            leftIndex = currentIndex * 2 + 1;
            rightIndex = leftIndex + 1;
        }
        return returnValue;
    }
}

힙 구현시, 오해할지도 모를 점

항상 this.heap은 정렬되어 있어야 한다?

직접 put하고 pop해보면서 this.heap을 살펴보자

const pq1 = new MaxHeap();
pq1.put(1)
pq1.put(2)
pq1.put(3)
pq1.put(4)
console.log(pq1.heap)
console.log(pq1.pop())
console.log(pq1.heap)
console.log(pq1.pop())
console.log(pq1.heap)

두번째 this.heap [3,1,2]가 이상했음. 소스를 잘못 짰나? 근데 tree를 그려보니까 저게 맞음.

어쨌든, 규칙에 맞게 정상적으로 pop되도록 잘 put되기만 하면 되는거로 생각됌