[JavaScript] JavaScript로 힙(Heap) 구현하기

Heap

 

힙(Heap) 이란?
최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로 한 자료구조로서 다음과 같은 힙 속성을 만족한다. A가 B의 부모 노드 이면, A의 키값과 B의 키값 사이에는 대소 관계가 성립한다. 

• 트리구조이기 때문에 시간 복잡도 O(logN)이 소요된다.
• 최댓값 최솟값을 빠르게 구하기 찾을 수 있다.
• JavaScript의 경우 내장 라이브러리에 Heap구조가 없기 때문에 직접 구현해야 한다. (외부 라이브러리로는 적용 가능)

 

 

Heap 자료구조

위의 이미지는 1부터 100까지의 정수를 저장한 최대 힙의 예시 모습이다. 모든 부모 노드들이 그 자식 노드들보다 큰 값을 가진다.

 

 

 

 

---

1. Heap에서의 부모

이진트리로 부모와 자식 노드가 발생하며, 완전 이진트리가 아니라 반정렬 상태를 갖는다.
최댓값을 구하는 Heap이라면 큰 값이 부모 노드로 가고,  최솟값을 구하는 Heap은 작은 값이 부모 노드 쪽으로 가게 된다. 자식 노드는 부모 노드보다 작은 값만 유지하면 된다.

 

 

 

---

2. 최소 힙( Min Heap ) 구현

최대 힙(Max Heap)이라면 반대의 계산 결과로 적용

 

class Heap {
    constructor() {
        // index의 시작은 0으로 계산의 편의성을 위해 첫 번째를 비워둔다. (1번이 1번 index)
        this.heap = [ null ]; 
    }
    
    size() {
        return this.heap.length - 1;
    }
    
    getMin() {
        return this.heap[1] ? this.heap[1] : null;
    }
    
    swap(a, b) {
        [ this.heap[a], this.heap[b] ] = [ this.heap[b], this.heap[a] ];
    }
    
    push(value) {
        this.heap.push(value);
        let curIdx = this.heap.length - 1;
        let parIdx = (curIdx / 2) >> 0;
        
        // 부모가 노드가 제일 작아야 하므로, 부모노드가 현재노드보다 큰 지  반복하여 체크한다.
        while(curIdx > 1 && this.heap[parIdx] > this.heap[curIdx]) {
        	// 구조분해 할당을 이용해 부모와 자식을 swap 한다.
            this.swap(parIdx, curIdx)
            curIdx = parIdx;
            parIdx = (curIdx / 2) >> 0;
        }
    }
    
    pop() {
        // 배열 첫 원소를 비워두므로 root는 heap[1]에 항상 위치한다.
        const min = this.heap[1];	
        
        /*  
            배열 마지막 원소를 root 위치에 배치 과정.
            if-else로 분기되는 이유는 추후 heap이 비었는지 아닌지 확인하기 위해 
            size 체크 함수를 만들때 -1을 통해 0을 만들어주기 때문.
        */
        if(this.heap.length <= 2) this.heap = [ null ];
        else this.heap[1] = this.heap.pop();   
        
        
        let curIdx = 1;
        let leftIdx = curIdx * 2;
        let rightIdx = curIdx * 2 + 1; 
        
        if(!this.heap[leftIdx]) return min;
         // 왼쪽 자식이 없다는 것은 오른쪽 자식도 없는, 즉 루트만 있는 상태이므로 바로 반환!
        if(!this.heap[rightIdx]) {
            if(this.heap[leftIdx] < this.heap[curIdx]) {
				// 오른쪽 자식이 없다면 왼쪽 자식하나만 있다는 것을 의미한다.
                this.swap(leftIdx, curIdx);
            }
            return min;
        }

       // 위에 조건에 걸리지 않는 경우 왼쪽과 오른쪽 자식이 모두 있는 경우이다.
       // 따라서 현재 노드가 왼쪽 또는 오른쪽 보다 큰 지 작은지를 검사하며 반복한다.
        while(this.heap[leftIdx] < this.heap[curIdx] || this.heap[rightIdx] < this.heap[curIdx]) {
            // 왼쪽과 오른쪽 자식 중에 더 작은 값과 현재 노드를 교체하면 된다.
            const minIdx = this.heap[leftIdx] > this.heap[rightIdx] ? rightIdx : leftIdx;
            this.swap(minIdx, curIdx);
            curIdx = minIdx;
            leftIdx = curIdx * 2;
            rightIdx = curIdx * 2 + 1;
        }

        return min;
    }
}