자바스크립트로 우선순위 큐 구현하기

자바스크립트는 heap 을 따로 제공하지 않는다. 

따라서 우선순위 큐를 사용하기 위해서는 직접 구현을 해야하는데, 다음과 같다.

class PriorityQueue {
    constructor() {
        this.heap = [];
    }

    getLeftChildIndex(parentIndex) {
        return parentIndex * 2 + 1;
    }

    getRightChildIndex(parentIndex) {
        return parentIndex * 2 + 2;
    }

    getParentIndex(childIndex) {
        return Math.floor((childIndex - 1) / 2);
    }

    empty() {
        return this.heap.length === 0;
    }

    peek() {
        return this.heap[0];
    }

    push(data) {
        this.heap.push(data);
        this.heapifyUp();
    }

    // 최근에 삽입된 노드가 제 자리를 찾아갈 수 있도록 하는 메소드
    heapifyUp() {
        let index = this.heap.length - 1;

        while (index > 0) {
            const parentIndex = this.getParentIndex(index);
            if (this.heap[parentIndex] > this.heap[index]) {
                [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
                index = parentIndex;
            } else break;
        }
    }

    pop() {
        const len = this.heap.length;
        const rootNode = this.peek();

        if (len <= 0) return;
        if (len === 1) this.heap = [];
        else {
            this.heap[0] = this.heap.pop(); // 끝에 있는 노드를 루트노드로 변경
            this.heapifyDown();
        }
        return rootNode;
    }

    // 변경된 루트노드가 제 자리를 찾아가도록 하는 메소드
    heapifyDown() {
        let index = 0;
        const len = this.heap.length;
        const rootNode = this.peek();

        while (this.getLeftChildIndex(index) < len) {
            const leftChildIndex = this.getLeftChildIndex(index);
            const rightChildIndex = this.getRightChildIndex(index);
            const smallerChildIndex = rightChildIndex < len && this.heap[rightChildIndex] < this.heap[leftChildIndex] ? rightChildIndex : leftChildIndex;

            // 자식 노드의 키 값이 루트노드보다 작다면 위로 끌어올린다.
            if (this.heap[smallerChildIndex] <= rootNode) {
                [this.heap[index], this.heap[smallerChildIndex]] = [this.heap[smallerChildIndex], this.heap[index]];
                index = smallerChildIndex;
            } else break;
        }
    }
}