힙(Heap)은 이진 트리 기반의 데이터 구조로, 우선순위 큐를 구현하는 데 사용됩니다. 힙은 “최댓값 또는 최솟값을 빠르게 찾을 수 있는 완전 이진 트리(complete binary tree)”입니다.

힙의 종류

힙은 크게 두 가지 종류로 나뉩니다.

최대 힙

• 부모 노드가 자식 노드보다 큰 값을 가지는 힙입니다.
• 가장 큰 값이 항상 루트 노드에 위치합니다.

최소 힙

• 부모 노드가 자식 노드보다 작은 값을 가지는 힙입니다.
• 가장 작은 값이 항상 루트 노드에 위치합니다.

C++에서의 힙 구현

C++ 표준 라이브러리(STL)는 priority_queue 클래스를 통해 힙을 지원합니다. 다음은 최대 힙을 사용하는 예제 코드입니다.

#include <queue>
#include <iostream>

int main() {
    std::priority_queue<int> maxHeap;
    maxHeap.push(3);
    maxHeap.push(5);
    maxHeap.push(1);

    while (!maxHeap.empty()) {
        std::cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
    // 출력: 5 3 1
}

요약

힙은 자료를 정렬된 상태로 유지하고, 데이터의 삽입과 삭제를 빠르게 처리할 수 있는 자료 구조입니다. C++에서는 priority_queue를 활용하여 간단하게 힙을 사용할 수 있습니다.

더 많은 자세한 내용은 C++ 힙 공식 문서를 참고하세요.