[JS] 힙/우선 순위 큐 새로 짜봤습니다.

짤 출처: https://realworld.to/projects/kgQezzTal_aCArVGxt0pbQ

Javascript에서 힙이 필요하면 매번 구현을 해줘야하는 정말.. 험난한 여정이 있는데요.

저번에 제가 대략적으로 공유한 코드가 모든 상황에서 쓰이기 힘들더라구요.

 

특히 pop에서 최상단 노드부터 왼쪽 노드, 오른쪽 노드를 비교해줘야하는데,

이 과정에서 undefined와 관련해서 많은 오류가 있는 걸 확인했습니다. 새로 짠 코드를 공유해드릴게요.

 

Heap.js

class MinHeap {
    constructor() {
        this.heap = [null];
    }
    
    push(val) {
        this.heap.push(val);
        let currentIndex = this.heap.length - 1;
        let parentIndex = Math.floor(currentIndex / 2);
        
        while (parentIndex !== 0 && this.heap[currentIndex] < this.heap[parentIndex]) {
            this._swap(currentIndex, parentIndex);
            currentIndex = parentIndex;
            parentIndex = Math.floor(currentIndex / 2);
        }
    }
    
    pop() {
        if (this.isEmpty()) return;
        if (this.heap.length === 2) return this.heap.pop();
        
        const val = this.heap[1];
        this.heap[1] = this.heap.pop();
        
        let currentIndex = 1;
        let leftIndex = 2;
        let rightIndex = 3;
        
        while (
            this.heap[leftIndex] && this.heap[currentIndex] > this.heap[leftIndex] ||
            this.heap[rightIndex] && this.heap[currentIndex] > this.heap[rightIndex] 
        ) {
            if (this.heap[leftIndex] === undefined) {
                this._swap(rightIndex, currentIndex);
            } else if (this.heap[rightIndex] === undefined) {
                this._swap(leftIndex, currentIndex);
            } else if (this.heap[leftIndex] > this.heap[rightIndex]) {
                this._swap(currentIndex, rightIndex);
                currentIndex = rightIndex;
            } else if (this.heap[leftIndex] <= this.heap[rightIndex]) {
                this._swap(currentIndex, leftIndex);
                currentIndex = leftIndex;
            }
            
            leftIndex = currentIndex * 2;
            rightIndex = currentIndex * 2 + 1;
        }
        
        return val;
    }
    
    isEmpty() {
        return this.heap.length === 1;
    }
    
    _swap(a, b) {
        [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
    }
}

 

1. pop에서 undefined index 처리

while (
    this.heap[leftIndex] && this.heap[currentIndex] > this.heap[leftIndex] ||
    this.heap[rightIndex] && this.heap[currentIndex] > this.heap[rightIndex] 
) {
    if (this.heap[leftIndex] === undefined) {
        this._swap(rightIndex, currentIndex);
    } else if (this.heap[rightIndex] === undefined) {
        this._swap(leftIndex, currentIndex);
        ...

 

이전엔 undefined 처리를 위해서 위에 지저분하게 코드를 끼워넣고 그랬었는데요..

이렇게 바꿔줬습니다.

다만, !this.heap[leftIndex]와 같은 방식은 혹여나 위험할 수 있습니다. 저번에 다른 분들 코드 보다가 알았는데 이런 접근을 했을 때 값이 0인 경우를 같이 걸러내더라구요. 귀찮더라도 꼭 undefined로 명시해줍시다.

 

 

2. 부모와 자식노드의 관계성

let currentIndex = 1;
let leftIndex = currentIndex * 2;
let rightIndex = currentIndex * 2 + 1;

맨날 1,2,3을 넣다보니,,,,

자연스럽게 관계성을 까먹곤 했는데요. 자식 노드는 부모노드의 2배라는 점 꼭 알아두시면 편할 것 같습니다.

 

//          1
//     2          3
//  4     5    6     7
// 8 9 10 11 12 13 14 15
...

정말 해당 관계를 만족하는 걸 확인할 수 있습니다.

여기서 팁이 하나 있는데요. 간혹 최소(최대)힙에서 최대(최소)값을 요구하는 문제들이 있습니다.

이런 값들은 가장 최하단 depth에 있다는게 보장되니(부모와 항상 비교하니 더 높은 depth로 갈 순 없습니다.) 혹시 이런 연산이 필요하다면, 가장 아래 depth에 접근해서 Math.max/min 으로 접근하시는게 마음 편하실 것 같습니다.

 

그럼 이만!