[JS] 힙(Heap) - 큐 외길인생에서 힙을 만나다.

스택과 큐로 모든 자료구조를 다 처리할 수 있었던 프로그래머스의 레벨 2문제와 다르게

레벨 3만 되어도 다양한 자료구조들을 쓰는 걸 발견했다.

 

힙(Heap)이나 트라이(Trie)등 아직 익숙하지 않은 자료 구조를 하나하나 정리해볼 생각이다.

그리고 여담이지만 js에서는 자료구조 라이브러리가 없어서 다 직접 구현해줘야한다.

js 환경에서 class만드는게 익숙하진 않았지만, 수 십 번의 큐를 만들면서 구조가 나름 익숙해졌다.

 

자 힙에 대해 알아보자!

---

힙과 우선순위 큐

최소 힙 (출처는 https://blog.hexabrain.net/249)

일반적인 큐는 FIFO 구조를 따르기 때문에 먼저 enqueue 된 요소가 먼저 나가지만,

우선순위 큐에서는 가장 우선 순위가 높은 요소가 먼저 나간다.

조금만 생각해보면 이 이상한 구조가 매번 요소 삽입때마다 정렬을 해줘야한다는 걸 알 수 있을 것이다.

 

힙과 우선 순위 큐는 같아보이지만 사실 범주가 꽤나 다르다.

우선 순위 큐 구현에서 힙을 이용하면 유용한 건 맞지만, 그냥 사실 배열을 만든 다음 요소 삽입때마다 정렬해줘도 우선 순위 큐라고 할 수 있다.

결국 가장 효율적인 우선 순위 큐를 만드는 자료구조는 힙이다. 라고 이해하면 좋을 것 같다.

 

힙에서의 요소 추가 그리고 삭제

힙을 다룰 때 가장 핵심적인 건 "요소를 추가할 때 그리고 요소를 삭제할 때 정렬을 어떻게 해줄 것인가"이다.

삭제와 추가 모두 이진 트리 구조를 따르는 힙의 특성 때문에 O(logN)의 시간 복잡도를 갖는다.

자 이제 어떤 순서로 구현되는지 정리해보자.

 

힙에서의 요소 추가 과정

1. 요소를 추가한 뒤에 자신의 부모 노드와 비교한다.
2. 추가된 요소가 부모노드 보다 우선순위가 높다면 순서를 바꾼다.
3. 부모 노드보다 우선 순위가 낮을 때까지 반복한다.

 

힙에서의 요소 삭제 과정

1. 힙에서 요소 삭제는 루트 정점에서만 가능하다.
2. 삭제된 위치에는 가장 마지막 요소가 위치하게 된다.
3. 자식과 비교 후, 더 우선 순위가 높은 정점과 교체한다.
4. 자식보다 크기가 클 때까지 계속 진행한다.

 

JS 환경에서 힙 요소 구현

자 이제 가장 중요하다.

javascript에서 구현할 수 있는 힙을 정의해보자.

힙은 특성에 따라 최대 힙(maxHeap) 그리고 최소 힙(minHeap)이 있다.

삽입과 삭제에서 정렬 순서만 조정해준다면 문제 없이 구현이 가능하다.

 

class MaxHeap {
	constructor() {
    	this.heap=[null];
    }
    
    push(value) {
    	this.heap.push(value);
        let currIdx = this.heap.length - 1;
        let parentIdx = Math.floor(currIdx / 2);
        
        while(parentIdx !== 0 && this.heap[parentIdx] < value) {
        	const temp = this.heap[parentIdx];
            this.heap[parentIdx] = value;
            this.heap[currIdx] = temp;
            
            currIdx = parentIdx;
            parentIdx = Math.floor(currIdx / 2);
        }
    }
    
    pop() {
    	const val = this.heap[1];
        this.heap[1] = this.heap.pop();
        let currIdx = 1;
        let [pl, pr] = [2, 3];
        
        while(
        	this.heap[currIdx] < this.heap[pl] ||
            this.heap[currIdx] < this.heap[pr]
        ) {
        	if (this.heap[pl] < this.heap[pr]) {
            	const temp = this.heap[currIdx];
                this.heap[currIdx] = this.heap[pl];
                this.heap[pr] = temp;
                currIdx = pr;
            } else {
            	const temp = this.heap[currIdx];
                this.heap[currIdx] = this.heap[pl];
                this.heap[pl] = temp;
                currIdx = pl;
            }
            pl = currIdx * 2;
            pl = currIdx * 2 + 1;
        }
        return val;
    }
}

 

핵심적인 부분은 자식 노드에서 부모 노드를 찾을 때

// currIdx is index of current pushed location.
const parentIdx = Math.floor(currIdx / 2);

 

반대로 부모 노드에서 자식 노드를 찾을 때는

// children are two in binary tree.
let leftChildNode = parentIdx * 2;
let rightChildNode = parentIdx * 2 + 1;

 

이렇게 2를 나누거나 2를 곱한다는 사실을 알아야한다.

나머지 로직들은 값을 바꾸기 위해 temp를 사용하여 교체해주는 과정이다.

사실 구조분해 할당을 통해 바꿀 수 있을 것 같은데 나중에 한 번 해봐야겠다.

 

큐에 비해서 로직이 상당히 복잡하다.

관련 문제가 많지 않아서 외울 수는 없겠지만, 핵심적인 부분들 (자식에서 부모노드 접근, 부모노드에서 자식노드 접근) 같은 부분들은 알아놓는게 여러모로 좋을 듯하다.