[자료구조] 힙(Heap)

힙 (Heap)

이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬되는 특징이 있다.

힙의 특징

• 우선순위가 높은 요소가 먼저 나가는 특징을 가진다.(우선순위가 높은 요소를 루트에 배치하고 루트가 가장 먼저 나간다.)
• 루트가 가장 큰 값이 되는 최대 힙(Max Heap)과 루트가 가장 작은 값이 되는 최소 힙(Min Heap)이 있다.
• 자바스크립트에서는 Heap을 사용하기 위해서는 직접 구현해서 사용해야 한다.

우선순위 큐

• 일반적인 큐(FIFO)와 달리 우선 순위가 높은 요소가 먼저 나가는 큐이다.
• 우선순위 큐는 자료구조가 아닌 개념이다. 그렇게 우선순위 큐를 구현하는 방법은 다양하게 있다.
• 우선순위 큐 != 힙 (우선순위 큐는 힙보다 효율이 떨어진다.)

힙 요소 추가 알고리즘

• 요소가 추가될 때는 트리의 가장 마지막 정점에 위치한다.
• 추가 후 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꾼다.
• 위 과정을 반복하면 결국 가장 우선순위가 높은 정점이 루트가 된다.
• 완전 이진 트리의 높이는 log N이기에 힙 요소 추가 알고리즘은 O(log N)의 시간 복잡도를 가진다.

힙 요소 제거 알고리즘

• 요소 제거는 루트 정점만 가능하다.
• 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치한다.
• 루트 정점의 두 자식 정점 중 더 우선순위가 높은 정점과 바꾼다.
• 두 자식 정점이 우선순위가 더 낮을 때 까지 반복한다.
• 완전 이진 트리의 높이는 log N이기에 힙의 요소 제거 알고리즘은 O(log N)의 시간 복잡도를 가진다.

최대 힙(Max Heap) 구현

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

    push(value) {
        this.heap.push(value);
        let currentIndex = this.heap.length - 1;
        let parentIndex = Math.floor(currentIndex / 2);

        while (parentIndex !== 0 && this.heap[parentIndex] < value) {
            const temp = this.heap[parentIndex];
            this.heap[parentIndex] = value;
            this.heap[currentIndex] = temp;

            currentIndex = parentIndex;
            parentIndex = Math.floor(currentIndex / 2);
        }
    }

    pop() {
        const value = this.heap[1];
        this.heap[1] = this.heap.pop();

        let currentIndex = 1;
        let leftChild = currentIndex * 2;
        let rightChild = currentIndex * 2 + 1;
        while (this.heap[currentIndex] < this.heap[leftChild] ||
            this.heap[currentIndex] < this.heap[rightChild]) {
            const temp = this.heap[currentIndex];
            if (this.heap[leftChild] < this.heap[rightChild]) {
                this.heap[currentIndex] = this.heap[rightChild];
                this.heap[rightChild] = temp;
                currentIndex = rightChild;
            } else {
                this.heap[currentIndex] = this.heap[leftChild];
                this.heap[leftChild] = temp;
                currentIndex = leftChild;
            }

            leftChild = currentIndex * 2;
            rightChild = currentIndex * 2 + 1;
        }
        return value;
    }
}

최소 힙(Min Heap) 구현

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

    push(value) {
        this.heap.push(value);
        let currentIndex = this.heap.length - 1;
        let parentIndex = Math.floor(currentIndex / 2);

        while (parentIndex !== 0 && this.heap[parentIndex] > value) {
            const temp = this.heap[parentIndex];
            this.heap[parentIndex] = value;
            this.heap[currentIndex] = temp;

            currentIndex = parentIndex;
            parentIndex = Math.floor(currentIndex / 2);
        }
    }

    pop() {
        const value = this.heap[1];
        this.heap[1] = this.heap.pop();

        let currentIndex = 1;
        let leftChild = currentIndex * 2;
        let rightChild = currentIndex * 2 + 1;

        while (this.heap[currentIndex] > this.heap[leftChild] ||
            this.heap[currentIndex] > this.heap[rightChild]) {
            const temp = this.heap[currentIndex];
            if (this.heap[leftChild] > this.heap[rightChild]) {
                this.heap[currentIndex] = this.heap[rightChild];
                this.heap[rightChild] = temp;
                currentIndex = rightChild;
            } else {
                this.heap[currentIndex] = this.heap[leftChild];
                this.heap[leftChild] = temp;
                currentIndex = leftChild;
            }

            leftChild = currentIndex * 2;
            rightChild = currentIndex * 2 + 1;
        }
        return value;
    }
}