[C++ Data Structure] 힙(Heap)

힙

힙(Heap)은 우선순위 큐(Priority Queue)를 구현하는 데 주로 사용되는 자료구조입니다.
C++에서는 std::priority_queue가 있습니다.

주로 우선순위가 있는 작업을 처리할 때 많이 사용됩니다.
즉, 우선순위 큐는 일반 큐와 다르게 각 요소에 우선순위가 있어 높은 우선순위를 가진 요소가 먼저 처리되는 자료구조입니다.

삽입과 삭제의 시간 복잡도는 $O(log \ n)$이며, 최댓값과 최솟값의 조회는 $O(1)$입니다.
하지만, 중간 요소에 접근하려하면 선형 탐색이 필요하기 때문에 검색이나 삭제가 $O(n)$으로 비효율적입니다.

배열 기반의 완전 이진 트리 형태로 구현되기 때문에 포인터 기반 트리보다 메모리 낭비가 적습니다.

힙 정렬에 활용 가능합니다.

최대 힙과 최소 힙

힙에는 최대 힙(Max Heap)과 최소 힙(Min Heap)이 있습니다.

최대 힙은 부모 노드가 자식 노드보다 큰 값을 가지며, 루트 노드는 항상 최대값입니다.
최소 힙은 부모 노드가 자식 노드보다 작은 값을 가지며, 루트 노드는 항상 최소값입니다.

버블업

최대 힙을 기준으로 새로운 요소를 힙에 추가할 때 버블 업(Bubble Up)이라는 방법을 사용합니다.
버블 업은 요소를 맨 끝에 추가한 후에 부모 노드와 비교하면서 힙의 규칙을 유지할 때까지 위치를 바꿔줍니다.
예를 들어, 새로운 요소가 부모 노드보다 크면 부모와 자리를 바꾸면서 올라가게 되며, 새로운 요소가 올바른 위치에 배치되도록 합니다.

버블업 구현 예시

#include <iostream>
#include <vector>

class MaxHeap
{
private:
    std::vector<int> heap; // 힙을 저장할 벡터

public:
    MaxHeap() {}

    void insert(int value)
    {
        heap.push_back(value); // 새 값을 힙 벡터의 끝에 추가
        bubbleUp(); // 버블 업으로 올바른 위치로 재정렬
    }

    void bubbleUp()
    {
        int index = heap.size() - 1; // 삽입된 노드의 인덱스

        while (index > 0)
        {
            int parentIndex = (index - 1) / 2;

            if (heap[index] > heap[parentIndex])
            {
                std::swap(heap[index], heap[parentIndex]);
                index = parentIndex; // 현재 인덱스를 부모 인덱스로 갱신
            }
            else
            {
                break; // 부모보다 크지 않으면 종료
            }
        }
    }

    // 힙의 현재 상태 출력
    void printHeap()
    {
        for (int i = 0; i < heap.size(); i++)
        {
            std::cout << heap[i] << " ";
        }
        std::cout << std::endl;
    }
};

int main()
{
    // 힙을 사용 예시
    MaxHeap maxHeap;
    maxHeap.insert(10);
    maxHeap.insert(20);
    maxHeap.insert(5);
    maxHeap.insert(30);
    maxHeap.insert(15);

    // 현재 힙 상태 출력
    maxHeap.printHeap();
}

다음 링크에서 직접 값을 추가하거나 제거했을 때 알고리즘의 과정을 시각적으로 살펴볼 수 있습니다.

Heap Animation by Y. Daniel Liang
Binary Heap (Priority Queue) - VisuAlgo