C++ STL 힙(Heap) 완벽 가이드 – make_heap부터 is_heap_until까지

C++ STL 힙(Heap)이란?

C++ STL은 컨테이너를 힙 구조로 손쉽게 변환하고 관리할 수 있는 함수들을 제공합니다. 힙을 활용하면 데이터를 빠르게 삽입할 수 있고, 요소를 꺼낼 때마다 남아 있는 값 중 항상 가장 큰 값이 반환됩니다. 나머지 요소들의 배치는 내부 구현 방식에 따라 달라질 수 있습니다.

1. make_heap()과 front()

• make_heap() – 반복자로 지정한 범위를 힙 구조로 변환합니다.
• front() – 힙의 첫 번째 요소, 즉 최댓값을 반환합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> heap = {33, 43, 53, 38, 28};
    make_heap(heap.begin(), heap.end());
    cout << "힙의 최댓값 : " << heap.front() << endl;
}

실행 결과

힙의 최댓값 : 53

2. push_heap()과 pop_heap()

• push_heap() – 새 요소를 삽입한 뒤 힙을 재정렬합니다. 힙의 크기는 1 증가하며, 새 요소는 알맞은 위치에 배치됩니다.
• pop_heap() – 최댓값을 삭제한 뒤 힙을 재정렬합니다. 힙의 크기는 1 감소하며, 나머지 요소들이 그에 맞게 재배치됩니다.

실제로는 push_back()으로 요소를 추가한 후 push_heap()을 호출하고, pop_heap() 실행 후 pop_back()으로 마지막 요소를 제거하는 패턴으로 사용합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> heap = {33, 43, 53, 38, 28};
    make_heap(heap.begin(), heap.end());
    cout << "힙의 최댓값 : " << heap.front() << endl;

    heap.push_back(60);                  // 새 요소 추가
    push_heap(heap.begin(), heap.end()); // 힙 재정렬
    cout << "삽입 후 최댓값 : " << heap.front() << endl;

    pop_heap(heap.begin(), heap.end());  // 최댓값을 마지막으로 이동
    heap.pop_back();                     // 실제 삭제
    cout << "삭제 후 최댓값 : " << heap.front() << endl;
}

실행 결과

힙의 최댓값 : 53
삽입 후 최댓값 : 60
삭제 후 최댓값 : 53

3. sort_heap()

sort_heap()은 힙 정렬(heapsort) 기법을 이용해 힙의 모든 요소를 오름차순으로 정렬합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> heap = {33, 43, 53, 38, 28};
    make_heap(heap.begin(), heap.end());

    cout << "정렬 전 : ";
    for (const auto &i : heap) {
        cout << i << ' ';
    }

    sort_heap(heap.begin(), heap.end());

    cout << "\n정렬 후 : ";
    for (const auto &i : heap) {
        cout << i << ' ';
    }
}

실행 결과

정렬 전 : 53 43 33 38 28
정렬 후 : 28 33 38 43 53

4. is_heap()과 is_heap_until()

• is_heap() – 해당 범위가 힙인지 검사합니다. 대부분의 구현에서 내림차순으로 정렬된 컨테이너 역시 힙으로 간주되며, 힙이면 true, 아니면 false를 반환합니다.
• is_heap_until() – 컨테이너가 힙 상태를 유지하는 위치까지의 반복자를 찾아 반환합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> heap = {33, 43, 53, 38, 28};
    vector<int>::iterator iter;

    is_heap(heap.begin(), heap.end())
        ? cout << "힙입니다."
        : cout << "힙이 아닙니다.";
    cout << endl;

    make_heap(heap.begin(), heap.end());
    cout << "make_heap 적용 후" << endl;

    is_heap(heap.begin(), heap.end())
        ? cout << "힙입니다."
        : cout << "힙이 아닙니다.";
    cout << endl;

    vector<int>::iterator iter2 = is_heap_until(heap.begin(), heap.end());
    cout << "힙 범위의 요소들 : ";
    for (iter = heap.begin(); iter != iter2; iter++)
        cout << *iter << " ";
}

실행 결과

힙이 아닙니다.
make_heap 적용 후
힙입니다.
힙 범위의 요소들 : 53 43 33 38 28

마무리

C++ STL의 힙 함수들을 활용하면 별도의 힙 구조체를 직접 구현하지 않고도 우선순위 큐와 유사한 동작을 손쉽게 만들 수 있습니다. 참고로 주요 연산의 시간 복잡도는 make_heap()이 O(N), push_heap()과 pop_heap()은 O(log N), sort_heap()은 O(N log N)입니다.