[c++] 이진 힙 구현 알고리즘

08 Dec 2023

이진 힙은 힙(Heap)이라고도 불리는데, 우선순위 큐(priority queue)를 구현하는 데 사용되는 자료구조입니다. 이진 힙은 배열을 기반으로 하며, 각 노드는 특정 순서를 유지하면서 저장됩니다. 이진 힙은 대개 완전 이진 트리로 구성되어 있으며, 부모 노드의 값이 자식 노드의 값보다 작은지 또는 큰지에 따라 최소 힙(Min Heap) 또는 최대 힙(Max Heap)으로 나뉩니다.

이진 힙 구현 알고리즘

다음은 C++로 최소 힙(Min Heap)을 구현하는 예제 코드입니다.

#include <iostream>
#include <vector>

class BinaryHeap {
private:
    std::vector<int> heap;

    int parent(int i) { return (i - 1) / 2; }
    int leftChild(int i) { return 2 * i + 1; }
    int rightChild(int i) { return 2 * i + 2; }

    void siftUp(int i) {
        while (i > 0 && heap[parent(i)] > heap[i]) {
            std::swap(heap[parent(i)], heap[i]);
            i = parent(i);
        }
    }

    void siftDown(int i) {
        int minIndex = i;
        int l = leftChild(i);
        if (l < heap.size() && heap[l] < heap[minIndex])
            minIndex = l;
        int r = rightChild(i);
        if (r < heap.size() && heap[r] < heap[minIndex])
            minIndex = r;
        if (i != minIndex) {
            std::swap(heap[i], heap[minIndex]);
            siftDown(minIndex);
        }
    }

public:
    void insert(int key) {
        heap.push_back(key);
        siftUp(heap.size() - 1);
    }

    int extractMin() {
        int root = heap.front();
        std::swap(heap.front(), heap.back());
        heap.pop_back();
        if (!heap.empty())
            siftDown(0);
        return root;
    }
};

위의 코드는 최소 힙(Min Heap)을 구현하는 BinaryHeap 클래스를 보여줍니다. insert 함수는 새로운 값을 힙에 삽입하고, extractMin 함수는 최소 값을 추출합니다. 효율적인 siftUp과 siftDown 함수를 사용하여 힙의 속성을 유지합니다.

마치며

이진 힙은 효율적으로 우선순위 큐를 구현하는 데 사용되는 중요한 자료구조입니다. 이진 힙의 구현 방법과 관련 코드를 이해하는 것은 값진 경험일 것입니다.

더 많은 정보를 원하시거나 깊이 있는 내용을 찾으시려면 Binary Heap을 확인해보세요.