힙(Heap)

힙(Heap)?

'무엇인가를 쌓아올린 더미'라는 뜻을 가진 영단어입니다. 힙 트리를 줄여 힙이라 부릅니다.

이 의미를 잘 기억해두고, 힙이 어떤 형태와 특성을 가지고 있기에 이런 이름이 붙여졌는지 알아보겠습니다.

 

특징

• 힙의 목적은 '최대값 또는 최소값을 빠르게 찾기'
• 최대 힙과 최소 힙 2 종류가 있습니다.
  최대 힙은 부모 노드의 값이 자식 노드 보다 항상 큰 힙이고, 최소 힙은 부모 노드의 값이 자식 노드 보다 항상 작은 힙입니다.
• 루트 노드에는 항상 최대값 또는 최소값이 저장되어 있어 최대값/최소값을 한 번에 찾을 수 있습니다.O(1)

 

시간 복잡도

최대값/최소값 검색: O(1)

삽입/삭제: O(logn)

 

용도

• 우선순위 큐(priority queue) 구현
• 힙 정렬(heap sort) 구현

 

구현

최대 힙 구현

class MaxHeap {
    constructor() {
        // index 계산을 간편하게 하기 위해 index=1 부터 시작
        this.arr = [null];
    }
    // 삽입
    insert(data) {
        this.arr.push(data);
        // 삽입한 데이터의 index
        let index = this.arr.length - 1;
        // 1이 되면 벗어난다.
        while (index > 1) {
            // 부모 노드의 index
            let parentIndex = Math.floor(index / 2);
            if (this.arr[parentIndex] < this.arr[index]) {
                // 부모 노드보다 크면 swap
                let temp = this.arr[parentIndex];
                this.arr[parentIndex] = this.arr[index];
                this.arr[index] = temp;

                index = parentIndex;
            } else {
                break;
            }
        }
    }
    // 루트 노드(최대값) 삭제
    delete() {
        // heap 사이즈가 1이하이면(비어있으면) null 반환 후 종료
        if (this.arr.length <= 1) {
            return "힙이 비었습니다.";
        }
        // 말단 노드와 swap
        const temp = this.arr[1];
        this.arr[1] = this.arr[this.arr.length - 1];
        this.arr[this.arr.length - 1] = temp;
        const removed = this.arr.pop();

        let index = 1;
        while (true) {
            let leftChildIndex = index * 2;
            let rightChildIndex = index * 2 + 1;
            let swapIndex = null;
            
            // 왼쪽, 오른쪽 자식 순으로 비교 후 더 큰 수의 index 저장
            if (this.arr[index] < this.arr[leftChildIndex]) {
                swapIndex = leftChildIndex;
            }
            if (this.arr[index] < this.arr[rightChildIndex]) {
                swapIndex = rightChildIndex;
            }
            // 저장된 swap index가 없을 경우, swap 종료;
            if (swapIndex === null) {
                break;
            }
            // swap
            let temp = this.arr[index];
            this.arr[index] = this.arr[swapIndex];
            this.arr[swapIndex] = temp;
        }
        return removed;
    }
}
let maxHeap = new MaxHeap();
maxHeap.insert(1);
maxHeap.insert(2);
maxHeap.insert(3);
maxHeap.insert(4);
maxHeap.insert(5);
maxHeap.insert(6);
maxHeap.insert(7);
console.log(maxHeap.delete());
console.log(maxHeap.delete());
console.log(maxHeap.delete());
console.log(maxHeap.delete());
console.log(maxHeap.delete());
console.log(maxHeap.delete());

/* 실행 결과
7
6
5
4
3
2
*/

 

Reference

• https://namu.wiki/w/%ED%9E%99%20%ED%8A%B8%EB%A6%AC
• https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)