C++ make_heap·push_heap·pop_heap: priority_queue 대신 힙을 직접 다룰 때

힙 알고리즘

힙 자료구조 (최대 힙)

#include <algorithm>
#include <vector>

std::vector<int> v = {3, 1, 4, 1, 5};

// 힙 생성
std::make_heap(v.begin(), v.end());

// 최대값
std::cout << v.front() << std::endl;  // 5

힙은 “부모가 자식보다 크거나 같다”는 조건만 지키는 완전 이진 트리입니다. 트리라고 해도 포인터로 노드를 연결하지 않고, 배열 인덱스 i의 자식을 2i+1, 2i+2에 두는 방식으로 벡터 하나에 그대로 담습니다. 그래서 <algorithm>의 힙 함수들은 새 자료구조가 아니라 이미 있는 연속 구간을 힙 규칙에 맞게 재배열하는 알고리즘입니다. 위 코드 실행 후 v는 {5, 3, 4, 1, 1} 같은 순서가 되는데(구현마다 다를 수 있음), 정렬된 상태가 아니라 맨 앞만 최대라는 점이 보장될 뿐입니다.

이 부분 정렬이 힙의 장점입니다. 전체를 정렬하면 O(n log n)이 들지만, 최댓값을 꺼내고 새 값을 넣는 작업만 반복한다면 매번 O(log n)이면 충분합니다. 작업 스케줄러, 다익스트라 최단 경로, 이벤트 시뮬레이션처럼 “지금 가장 우선인 것 하나”만 계속 필요한 문제가 전형적인 사용처입니다.

make_heap, push_heap, pop_heap이 하는 일

C++ 표준의 기본 힙은 최대 힙(max-heap) 입니다. 비교 객체가 기본(std::less)일 때, v.front()가 항상 가장 “큰” 원소를 가리킵니다(동률이면 구현에 따라 어느 쪽이든).

연산	전제	효과	복잡도(대략)
make_heap(b, e)	없음	[b,e)를 힙 구조로 재배열	선형
push_heap(b, e)	[b,e-1)가 이미 힙, 새 값은 e-1	새 원소를 끼워 넣어 다시 힙으로	로그
pop_heap(b, e)	[b,e)가 힙	최상단(최대)을 e-1 위치로 보내고 나머지를 힙으로	로그
sort_heap(b, e)	[b,e)가 힙	전체를 오름차순 정렬(최대 힙 기준)	O(n log n)

중요한 사용 순서:

1. 삽입: v.push_back(x); 후 push_heap(v.begin(), v.end()) — 새 원소가 마지막에 있어야 합니다.
2. 추출: pop_heap(v.begin(), v.end()); 후 v.pop_back(); — pop_heap이 “가장 큰 값”을 끝으로 보낸 뒤, 물리적으로 제거는 pop_back으로 합니다.

is_heap, is_heap_until로 디버깅 시 힙 속성이 깨졌는지 확인할 수 있습니다.

순서가 이렇게 정해진 이유는 함수들이 벡터의 크기를 바꾸지 않기 때문입니다. 알고리즘은 반복자 두 개만 받으므로 원소를 추가하거나 지울 수 없고, 컨테이너를 바꾸는 일은 호출하는 쪽이 push_back/pop_back으로 해야 합니다. push_heap은 “마지막 원소가 새로 들어온 값”이라고 가정하고 그 값을 위로 끌어올리며(sift-up), pop_heap은 맨 앞의 최댓값과 마지막 원소를 바꾼 뒤 [b, e-1)을 다시 힙으로 만듭니다(sift-down). 그래서 pop_heap 직후 최댓값은 v.back()에 있고, 필요하면 pop_back() 전에 꺼내 쓸 수 있습니다.

make_heap이 선형 시간이라는 점도 기억해 둘 만합니다. 원소 n개를 하나씩 push_heap하면 O(n log n)이지만, 이미 모인 데이터를 한 번에 make_heap하면 아래 층부터 정리하는 방식이라 비교 횟수가 최대 3n 정도로 끝납니다. 데이터를 한꺼번에 받는다면 모두 넣은 뒤 make_heap 한 번이 더 빠릅니다.

벡터를 힙으로 쓰는 동안 중간에 v[2] = 100;처럼 원소를 직접 바꾸거나 std::sort, insert로 순서를 건드리면 힙 속성이 조용히 깨집니다. 그 뒤의 pop_heap은 정의되지 않은 동작이라 크래시 대신 틀린 값이 나오는 경우가 많아, 원인 추적이 어렵습니다. 의심스러울 때는 연산 직후에 assert(std::is_heap(v.begin(), v.end()))를 넣어 어디서 깨졌는지 좁혀 가는 것이 가장 빠릅니다.

---

priority_queue와의 관계

std::priority_queue는 컨테이너 어댑터로, 내부적으로 보통 vector + push_heap / pop_heap 과 같은 힙 연산을 씁니다. 차이는 인터페이스입니다.

• priority_queue: push/top/pop만 노출하며, 내부 벡터의 나머지 원소는 캡슐화됩니다. 가장 큰(또는 비교자에 따른 최우선) 하나만 꺼내는 큐로 쓰기 좋습니다.
• 힙 알고리즘 직접 사용: 같은 vector를 힙 구간과 비힙 구간으로 나누거나, 중간 상태를 직접 순회·수정해야 할 때 유리합니다(예: 힙 일부만 유지, 커스텀 파이프라인).

// 개념적으로 유사: pq.push(3) ≈ v.push_back(3); push_heap(...)
// 실행 예제
std::priority_queue<int> pq;
std::vector<int> v;

pq.push(3);
v.push_back(3);
std::push_heap(v.begin(), v.end());

최소 힙이 필요하면 priority_queue<int, vector<int>, greater<int>>처럼 비교자를 주면 되고, 아래 커스텀 비교자와 동일한 규칙을 힙 함수들에도 일관되게 적용해야 합니다.

직접 힙을 다룰 때 얻는 구체적인 이점은 이렇습니다. priority_queue는 내부 원소를 순회할 방법이 없어서 “현재 대기 중인 작업 목록 출력” 같은 기능을 만들 수 없고, 다 쓴 뒤 남은 원소를 정렬된 벡터로 꺼내려면 하나씩 pop해야 합니다. 벡터 힙은 언제든 전체를 순회할 수 있고, 마지막에 sort_heap 한 번으로 정렬된 결과를 얻을 수 있으며, reserve로 메모리를 미리 잡아 두기도 쉽습니다. 반대로 그만큼 실수할 여지도 커지므로, 팀 코드에서 이런 이점이 필요 없다면 priority_queue가 기본값입니다. priority_queue도 top()이 const 참조만 돌려줘서 std::unique_ptr 같은 이동 전용 타입을 꺼낼 수 없다는 불편이 있는데, 벡터 힙이라면 pop_heap 후 std::move(v.back())으로 꺼낼 수 있습니다.

---

커스텀 비교자(Comparator)와 주의점

make_heap, push_heap, pop_heap, sort_heap은 모두 선택적 Compare 인자를 받습니다. std::priority_queue의 Compare와 마찬가지로, 힙에서 “가장 앞에 올” 원소가 비교 의미상 “가장 우선”인 쪽이 됩니다.

• 기본 std::less → 최대 힙(가장 큰 값이 front).
• std::greater → 최소 힙(가장 작은 값이 front).

std::vector<int> v = {3, 1, 4};
std::make_heap(v.begin(), v.end(), std::greater<>()); // 최소 힙

모든 힙 연산에 동일한 Compare를 넘겨야 합니다. 하나만 다르면 힙 불변식이 깨져 이후 pop_heap 등이 UB입니다.

사용자 정의 타입이면 operator< 또는 람다로 “정렬 기준”을 명확히 하세요.

struct Task { int id; int priority; };

std::vector<Task> tasks = /* ... */;
auto cmp = [](const Task& a, const Task& b) {
    return a.priority < b.priority; // priority 큰 것이 top
};
std::make_heap(tasks.begin(), tasks.end(), cmp);

비교자의 방향이 직관과 반대라서 가장 많이 헷갈립니다. 비교자 comp(a, b)가 true면 “a는 b보다 뒤에(아래에) 있어야 한다”는 뜻이고, 그 결과 비교상 “가장 큰” 원소가 맨 앞에 옵니다. 그래서 std::less(작다)를 주면 최대 힙, std::greater(크다)를 주면 최소 힙이 됩니다. 정렬(std::sort)에 less를 주면 오름차순이 되는 것과 방향이 반대로 느껴지는 이유입니다. Task 예제도 a.priority < b.priority라서 priority가 가장 큰 작업이 맨 앞에 옵니다. “숫자가 작을수록 우선”인 규칙(1순위, 2순위)이라면 >로 바꿔야 하는데, 이 방향을 반대로 적어 가장 덜 급한 작업부터 처리하는 버그는 테스트 데이터가 적을 때 잘 드러나지 않습니다.

비교자는 엄격한 약순서(strict weak ordering)를 지켜야 합니다. <=처럼 같은 값에서 true를 돌려주는 비교자를 쓰면 힙 연산의 결과가 정의되지 않습니다. 또 우선순위가 같은 작업끼리의 순서는 보장되지 않습니다. 힙은 안정적이지 않아서 먼저 들어온 작업이 먼저 나온다는 보장이 없으므로, FIFO가 필요하면 {priority, 순번}을 함께 비교하는 비교자를 만들어야 합니다.

최소 힙을 만들려고 값에 -를 붙여 넣는 트릭도 있지만, INT_MIN은 부호를 뒤집을 수 없어 오버플로(정의되지 않은 동작)가 나고 코드 의도도 흐려집니다. std::greater<>를 쓰는 편이 안전합니다.

---

실전: 상위 K개 찾기 (Top-K)

전체를 정렬하면 O(n log n)이지만, K가 작을 때 크기 K의 힙을 유지하면 O(n log K) 로 줄일 수 있습니다. “가장 큰 K개”를 원하면 최소 힙(가장 작은 값이 루트) 을 K개 유지하며, 더 큰 값이 들어오면 루트를 교체합니다(기존 예시와 동일한 패턴).

• K ≪ n 이면 전체 정렬보다 유리한 경우가 많습니다.
• K가 n에 가깝다면 partial_sort나 nth_element가 나을 수 있어, 프로파일링으로 선택하세요.
• 동일 값이 많을 때 순서가 중요하면 stable_sort 등 다른 요구와 맞는지 확인합니다.

---

힙 정렬(Heap sort) 정리

make_heap으로 최대 힙을 만든 뒤, pop_heap을 반복하면 큰 값부터 뒤로 정렬되고, 결국 sort_heap 한 번으로 오름차순 전체 정렬이 됩니다. 교과서적인 힙 정렬과 동일하며, 실무에서는 보통 std::sort 가 더 빠른 경우가 많아 학습·인터뷰·제약 환경에서 선택하는 경우가 많습니다.

std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
std::make_heap(v.begin(), v.end());
std::sort_heap(v.begin(), v.end());
// v는 비교자에 따른 정렬 순서(기본은 오름차순)

sort_heap은 이미 힙인 구간에 대해 동작합니다. 힙이 아닌 벡터에 바로 sort_heap만 호출하면 안 됩니다. 먼저 make_heap이 필요합니다.

힙 정렬은 추가 메모리 없이(제자리) 최악의 경우에도 O(n log n)을 보장한다는 장점이 있지만, 원소를 배열 전체에 걸쳐 멀리 떨어진 위치와 교환하기 때문에 캐시 효율이 나빠 실제 속도는 std::sort보다 느린 경우가 대부분입니다. 같은 값의 상대 순서도 유지하지 않습니다(불안정 정렬). 흥미롭게도 std::sort의 일반적인 구현(introsort)은 퀵소트의 재귀가 너무 깊어지면 힙 정렬로 전환해 최악의 경우를 막는데, 힙 정렬의 최악 보장이 여기서 쓰입니다. 정렬 알고리즘 전반의 비교는 정렬 알고리즘에서 다룹니다.

기본 사용

#include <algorithm>

std::vector<int> v = {3, 1, 4, 1, 5};

// 힙 생성
std::make_heap(v.begin(), v.end());

// 최대값 제거
std::pop_heap(v.begin(), v.end());
v.pop_back();

// 값 추가
v.push_back(9);
std::push_heap(v.begin(), v.end());

실전 예시

예시 1: 최대 힙

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> heap;
    
    // 요소 추가
    for (int x : {3, 1, 4, 1, 5, 9, 2, 6}) {
        heap.push_back(x);
        std::push_heap(heap.begin(), heap.end());
    }
    
    // 최대값부터 제거
    while (!heap.empty()) {
        std::cout << heap.front() << " ";
        std::pop_heap(heap.begin(), heap.end());
        heap.pop_back();
    }
    // 9 6 5 4 3 2 1 1
}

예시 2: 최소 힙

#include <algorithm>
#include <vector>
#include <functional>

int main() {
    std::vector<int> heap = {3, 1, 4, 1, 5};
    
    // 최소 힙
    std::make_heap(heap.begin(), heap.end(), std::greater<>());
    
    std::cout << "최소: " << heap.front() << std::endl;  // 1
}

예시 3: 상위 k개

#include <algorithm>
#include <vector>

std::vector<int> topK(const std::vector<int>& data, size_t k) {
    std::vector<int> heap;
    
    for (int x : data) {
        if (heap.size() < k) {
            heap.push_back(x);
            std::push_heap(heap.begin(), heap.end(), std::greater<>());
        } else if (x > heap.front()) {
            std::pop_heap(heap.begin(), heap.end(), std::greater<>());
            heap.back() = x;
            std::push_heap(heap.begin(), heap.end(), std::greater<>());
        }
    }
    
    std::sort_heap(heap.begin(), heap.end(), std::greater<>());
    return heap;
}

int main() {
    std::vector<int> data = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    auto top3 = topK(data, 3);
    
    for (int x : top3) {
        std::cout << x << " ";  // 9 6 5
    }
}

“큰 값 K개”를 찾는데 최소 힙을 쓰는 이유는, 힙의 루트가 지금까지 모은 K개 중 가장 작은 값, 즉 “커트라인”이기 때문입니다. 새 값이 커트라인보다 크면 커트라인을 버리고 새 값을 넣고, 작으면 볼 필요도 없습니다. 힙 크기가 K로 고정되므로 메모리가 O(K)이고, 데이터를 한 번만 훑으면 되어 스트림처럼 끝을 모르는 입력에도 쓸 수 있습니다.

교체 부분의 pop_heap → heap.back() = x → push_heap 세 줄은 pop_back과 push_back을 생략하고 마지막 자리를 재활용하는 방식입니다. 벡터 크기가 변하지 않아 재할당이 일어나지 않습니다. 마지막 sort_heap에도 같은 std::greater<>를 넘겼기 때문에 결과가 내림차순(9 6 5)이 됩니다. 여기서 비교자를 빼면 최소 힙 상태의 구간을 최대 힙으로 가정하고 정렬하게 되어 결과가 틀립니다.

k가 0이면 첫 조건 heap.size() < k가 항상 거짓이 되어 heap.front()를 빈 벡터에서 호출하게 됩니다. 이것은 정의되지 않은 동작이므로 함수 시작에서 if (k == 0) return {};로 막아야 합니다. 데이터가 이미 모두 메모리에 있고 원본을 수정해도 된다면 std::partial_sort(상위 K개를 정렬된 상태로)나 std::nth_element(K번째 경계만 맞추고 앞쪽은 순서 무관, 평균 O(n))가 코드도 짧고 대개 더 빠릅니다.

예시 4: 힙 정렬

#include <algorithm>

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
    
    // 힙 생성
    std::make_heap(v.begin(), v.end());
    
    // 힙 정렬
    std::sort_heap(v.begin(), v.end());
    
    for (int x : v) {
        std::cout << x << " ";  // 1 1 2 3 4 5 6 9
    }
}

힙 연산

// 힙 생성
std::make_heap(begin, end)

// 요소 추가
v.push_back(value);
std::push_heap(begin, end)

// 요소 제거
std::pop_heap(begin, end)
v.pop_back()

// 힙 정렬
std::sort_heap(begin, end)

// 힙 확인
bool isHeap = std::is_heap(begin, end)

자주 발생하는 문제

문제 1: 힙 속성

std::vector<int> v = {3, 1, 4, 1, 5};

// ❌ 힙 아님
// std::pop_heap(v.begin(), v.end());  // 정의되지 않은 동작

// ✅ 힙 생성 후
std::make_heap(v.begin(), v.end());
std::pop_heap(v.begin(), v.end());

문제 2: push_heap 순서

std::vector<int> heap = {3, 1, 4};
std::make_heap(heap.begin(), heap.end());

// ❌ 잘못된 순서
// std::push_heap(heap.begin(), heap.end());
// heap.push_back(5);  // 늦게 추가

// ✅ 올바른 순서
heap.push_back(5);
std::push_heap(heap.begin(), heap.end());

잘못된 순서에서 첫 push_heap은 마지막 원소(이미 힙에 있던 값)를 새 값으로 착각해 처리할 뿐이라 겉으로는 문제가 없어 보이고, 그다음에 추가한 5는 힙 규칙과 무관하게 끝에 놓입니다. 이후 front()는 5가 아니라 4를 돌려주고, 이 상태로 연산을 이어 가면 힙이 점점 망가집니다. 오류 메시지 없이 “가끔 최댓값이 틀린” 버그로 나타나는 이유입니다.

문제 3: pop_heap 순서

std::vector<int> heap = {5, 4, 3, 1, 1};

// ✅ 올바른 순서
std::pop_heap(heap.begin(), heap.end());  // 최대값을 끝으로
heap.pop_back();  // 제거

// ❌ 잘못된 순서
// heap.pop_back();
// std::pop_heap(heap.begin(), heap.end());

pop_back()을 먼저 하면 최댓값이 아니라 배열의 마지막 원소(힙에서 아무 의미 없는 위치의 값)가 사라집니다. 최댓값 5는 그대로 맨 앞에 남고, 이어지는 pop_heap이 5를 끝으로 보내므로 다음 front()는 또 다른 값이 됩니다. 결과적으로 원하지 않는 값이 하나 사라지고 최댓값은 남는 셈입니다. priority_queue::pop()이 내부에서 정확히 pop_heap 다음 pop_back을 호출해 주므로, 이 실수를 막고 싶다면 priority_queue를 쓰는 것이 가장 간단한 해결책입니다.

문제 4: 비교 함수

// 최대 힙 (기본)
std::make_heap(v.begin(), v.end());

// 최소 힙
std::make_heap(v.begin(), v.end(), std::greater<>());

// 모든 힙 연산에 같은 비교 함수 사용
std::push_heap(v.begin(), v.end(), std::greater<>());
std::pop_heap(v.begin(), v.end(), std::greater<>());

priority_queue vs 힙

// priority_queue: 래퍼
std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
std::cout << pq.top() << std::endl;  // 4

// 힙 알고리즘: 직접 제어
std::vector<int> heap;
heap.push_back(3);
std::push_heap(heap.begin(), heap.end());
heap.push_back(1);
std::push_heap(heap.begin(), heap.end());
heap.push_back(4);
std::push_heap(heap.begin(), heap.end());
std::cout << heap.front() << std::endl;  // 4

두 코드는 같은 일을 합니다. priority_queue는 한 줄로 끝나고 순서 규칙을 어길 방법이 없으며, 벡터 힙은 두 줄씩 필요하지만 heap 전체를 순회하거나 정렬된 결과로 바꿀 수 있습니다. 성능 차이는 거의 없으므로 선택 기준은 “힙 내부에 접근할 일이 있는가”입니다.

FAQ

Q1: 힙은?

A: 부모가 자식보다 우선한다는 조건만 지키는 완전 이진 트리를 배열에 담은 구조입니다. 맨 앞이 항상 최대(또는 최소)이고, 삽입과 최우선 원소 제거가 O(log n)입니다.

Q2: make_heap?

A: 임의의 구간을 힙 순서로 재배열합니다. 선형 시간이라 원소를 하나씩 push_heap하는 것보다 빠릅니다.

Q3: push_heap?

A: push_back으로 끝에 추가한 원소를 제자리로 올려 힙을 복구합니다. 원소를 직접 추가하지는 않으므로 반드시 push_back 뒤에 호출합니다.

Q4: pop_heap?

A: 최우선 원소를 구간 끝으로 옮기고 나머지를 다시 힙으로 만듭니다. 원소를 지우지는 않으므로 뒤이어 pop_back을 호출합니다.

Q5: priority_queue?

A: 벡터와 힙 알고리즘을 감싼 컨테이너 어댑터입니다. 순서 규칙을 대신 지켜 주는 대신 내부 원소 순회나 이동 전용 타입 꺼내기는 할 수 없습니다.

---

같이 보면 좋은 글

• C++ Algorithm Numeric | accumulate·reduce
• C++ reverse·rotate·reverse_copy: 범위 뒤집기와 회전 알고리즘 사용법
• C++ count·count_if와 all_of·any_of·none_of로 조건 집계하기
• C++ Algorithm Copy
• C++ Algorithm Generate
• C++ STL 알고리즘 기초: sort·find·transform·accumulate 실전 활용
• C++ Algorithm MinMax

실전 팁 (C++)

• 컴파일러 경고를 최대로 켜고(-Wall -Wextra 등 팀 합의), Sanitizer(ASan/UBSan)로 미정의 동작을 조기에 잡습니다.
• 최적화는 프로파일 결과를 본 뒤에 합니다.
• STL <algorithm> 사용 시 반복자 무효화·비교자 일관성을 함께 검토합니다.