C++ make_heap·push_heap·pop_heap: priority_queue 대신 힙을 직접 다룰 때
이 글의 핵심
힙 알고리즘은 push_back 뒤에 push_heap을, pop_heap 뒤에 pop_back을 호출해야 하는 순서 규칙이 있어 하나만 빠져도 힙 속성이 깨집니다. 비교자 방향이 최소·최대 힙을 뒤집는 방식과 흔한 실수를 짚고, priority_queue 대신 벡터 힙을 써야 하는 경우를 판단할 수 있게 합니다.
힙은 정렬이 아니라 재배열이다
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {3, 1, 4, 1, 5};
std::make_heap(v.begin(), v.end());
std::cout << v.front() << "\n"; // 5
}
힙(heap)은 “부모가 자식보다 크거나 같다”는 조건만 지키는 완전 이진 트리입니다. 트리라고 해도 포인터로 노드를 연결하지 않고, 배열 인덱스 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이 하는 일
표준 힙 함수의 기본은 최대 힙(max-heap)입니다. 비교자가 기본값(std::less)이면 v.front()가 항상 가장 큰 원소이고, 같은 값이 여러 개면 그중 어느 것이 앞에 올지는 정해져 있지 않습니다.
| 연산 | 전제 | 효과 | 복잡도 |
|---|---|---|---|
make_heap(b, e) | 없음 | [b,e)를 힙 구조로 재배열 | O(n), 비교 최대 3n회 |
push_heap(b, e) | [b,e-1)가 이미 힙, 새 값은 e-1 | 새 원소를 끌어올려 다시 힙으로 | O(log n) |
pop_heap(b, e) | [b,e)가 힙 | 최상단(최대)을 e-1 위치로 보내고 나머지를 힙으로 | O(log n) |
sort_heap(b, e) | [b,e)가 힙 | 전체를 오름차순 정렬(기본 비교자 기준) | O(n log n) |
사용 순서에는 규칙이 있습니다. 삽입할 때는 v.push_back(x);로 새 원소를 끝에 둔 다음 push_heap(v.begin(), v.end())를 호출하고, 꺼낼 때는 pop_heap(v.begin(), v.end())로 최댓값을 끝으로 보낸 다음 v.pop_back()으로 실제로 제거합니다.
std::vector<int> v = {3, 1, 4, 1, 5};
std::make_heap(v.begin(), v.end());
std::pop_heap(v.begin(), v.end()); // 최댓값 5를 v.back()으로
int top = v.back(); // 필요하면 여기서 꺼내 씀
v.pop_back();
v.push_back(9); // 끝에 추가한 뒤
std::push_heap(v.begin(), v.end()); // 제자리로 끌어올림
순서가 이렇게 정해진 이유는 이 함수들이 벡터의 크기를 바꾸지 않기 때문입니다. 알고리즘은 반복자 두 개만 받으므로 원소를 추가하거나 지울 수 없고, 컨테이너를 바꾸는 일은 호출하는 쪽이 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()))를 넣거나, std::is_heap_until로 처음 깨진 위치를 찾아 범위를 좁혀 가는 것이 가장 빠릅니다.
priority_queue와의 관계
std::priority_queue는 컨테이너 어댑터로, 표준이 내부 동작을 push_heap/pop_heap으로 규정하고 있습니다. pq.push(x)는 c.push_back(x); push_heap(...)과, pq.pop()은 pop_heap(...); c.pop_back()과 같습니다. 차이는 인터페이스에 있습니다.
std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
std::cout << pq.top() << "\n"; // 4
std::vector<int> heap;
for (int x : {3, 1, 4}) {
heap.push_back(x);
std::push_heap(heap.begin(), heap.end());
}
std::cout << heap.front() << "\n"; // 4
priority_queue는 push/top/pop만 노출하므로 순서 규칙을 어길 방법이 없지만, 내부 원소를 순회할 방법도 없어서 “현재 대기 중인 작업 목록 출력” 같은 기능을 만들 수 없고, 다 쓴 뒤 남은 원소를 정렬된 벡터로 꺼내려면 하나씩 pop해야 합니다. 벡터 힙은 언제든 전체를 순회할 수 있고, 마지막에 sort_heap 한 번으로 정렬된 결과를 얻을 수 있으며, reserve로 메모리를 미리 잡아 두기도 쉽습니다. priority_queue::top()은 const 참조만 돌려줘서 std::unique_ptr 같은 이동 전용 타입을 꺼낼 수 없다는 불편도 있는데, 벡터 힙이라면 pop_heap 후 std::move(v.back())으로 꺼낼 수 있습니다.
두 방식의 성능 차이는 거의 없으므로 선택 기준은 힙 내부에 접근할 일이 있는가입니다. 그런 이점이 필요 없다면 실수할 여지가 적은 priority_queue를 기본으로 쓰는 편이 좋습니다.
커스텀 비교자와 최소 힙
make_heap, push_heap, pop_heap, sort_heap은 모두 선택적 Compare 인자를 받습니다. 기본 std::less는 최대 힙(가장 큰 값이 front)을, std::greater는 최소 힙(가장 작은 값이 front)을 만듭니다.
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
int main() {
std::vector<int> heap = {3, 1, 4, 1, 5};
std::make_heap(heap.begin(), heap.end(), std::greater<>()); // 최소 힙
std::cout << "최소: " << heap.front() << "\n"; // 1
heap.push_back(0);
std::push_heap(heap.begin(), heap.end(), std::greater<>()); // 같은 비교자
std::pop_heap(heap.begin(), heap.end(), std::greater<>());
heap.pop_back(); // 0 제거
}
모든 힙 연산에 같은 Compare를 넘겨야 합니다. make_heap은 std::greater<>()로 하고 push_heap은 기본 비교자로 호출하는 식으로 하나만 달라도 힙 불변식이 깨지고, 이후의 pop_heap은 정의되지 않은 동작이 됩니다. priority_queue에서는 std::priority_queue<int, std::vector<int>, std::greater<int>>처럼 세 번째 템플릿 인자로 지정합니다.
사용자 정의 타입이면 operator<나 람다로 우선순위 기준을 명확히 합니다.
struct Task { int id; int priority; };
std::vector<Task> tasks = {{1, 2}, {2, 5}, {3, 1}};
auto cmp = [](const Task& a, const Task& b) {
return a.priority < b.priority; // priority가 큰 작업이 front
};
std::make_heap(tasks.begin(), tasks.end(), cmp);
비교자의 방향은 직관과 반대라서 가장 많이 헷갈립니다. 힙은 비교상 “가장 큰” 원소를 맨 앞에 두므로, 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의 힙을 유지하면 O(n log K)로 줄일 수 있습니다.
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
std::vector<int> topK(const std::vector<int>& data, std::size_t k) {
if (k == 0) return {};
std::vector<int> heap;
heap.reserve(k);
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};
for (int x : topK(data, 3)) 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()를 호출하게 되고, 이는 정의되지 않은 동작입니다. 데이터가 이미 모두 메모리에 있고 원본을 수정해도 된다면 std::partial_sort(상위 K개를 정렬된 상태로)나 std::nth_element(K번째 경계만 맞추고 앞쪽은 순서 무관, 평균 O(n))가 코드도 짧고 대개 더 빠릅니다.
힙 정렬
make_heap으로 최대 힙을 만든 뒤 sort_heap을 호출하면 오름차순으로 정렬됩니다. sort_heap은 내부에서 pop_heap을 반복해 큰 값부터 뒤쪽에 쌓는 것과 같습니다.
#include <algorithm>
#include <iostream>
#include <vector>
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
}
sort_heap은 이미 힙인 구간에 대해서만 동작합니다. 힙이 아닌 벡터에 바로 sort_heap을 호출하면 정의되지 않은 동작이므로 먼저 make_heap이 필요합니다.
힙 정렬은 추가 메모리 없이(제자리) 최악의 경우에도 O(n log n)을 보장한다는 장점이 있지만, 원소를 배열 전체에 걸쳐 멀리 떨어진 위치와 교환하기 때문에 캐시 효율이 나빠 실제 속도는 std::sort보다 느린 경우가 대부분입니다. 같은 값의 상대 순서도 유지하지 않습니다(불안정 정렬). std::sort의 일반적인 구현(introsort 계열)은 퀵소트의 재귀가 너무 깊어지면 힙 정렬로 전환해 최악의 경우를 막는데, 힙 정렬의 최악 보장이 여기서 쓰입니다. 정렬 알고리즘 전반의 비교는 C++ 정렬 알고리즘 구현과 비교에서 다룹니다.
순서를 틀렸을 때 생기는 일
push_back보다 push_heap을 먼저 호출하면 어떻게 될까요.
std::vector<int> heap = {3, 1, 4};
std::make_heap(heap.begin(), heap.end()); // {4, 1, 3}
// 잘못된 순서
std::push_heap(heap.begin(), heap.end()); // 마지막 원소 3을 새 값으로 착각
heap.push_back(5); // 5는 힙 규칙과 무관하게 끝에 놓임
// heap.front()는 5가 아니라 4
첫 push_heap은 마지막 원소(이미 힙에 있던 값)를 새 값으로 착각해 처리할 뿐이라 겉으로는 문제가 없어 보이고, 그다음에 추가한 5는 끝에 그냥 놓입니다. 이후 front()는 5가 아니라 4를 돌려주고, 이 상태로 연산을 이어 가면 힙이 점점 망가집니다. 오류 메시지 없이 “가끔 최댓값이 틀린” 버그로 나타나는 이유입니다.
반대로 pop_heap보다 pop_back()을 먼저 하면 최댓값이 아니라 배열의 마지막 원소(힙에서 아무 의미 없는 위치의 값)가 사라집니다. 최댓값은 그대로 맨 앞에 남고, 이어지는 pop_heap이 그 최댓값을 끝으로 보내므로 결과적으로 원하지 않는 값이 하나 사라지고 최댓값은 남는 셈입니다. priority_queue::pop()은 내부에서 정확히 pop_heap 다음 pop_back을 호출하므로, 이 실수를 구조적으로 막고 싶다면 priority_queue를 쓰는 것이 가장 간단합니다.
이 맥에서 직접 실행해 확인한 결과
환경은 Apple clang 21.0.0(libc++), macOS arm64, -std=c++20이고 성능 측정은 -O2입니다. 본문 코드는 작은 프로그램으로 옮겨 sanitizer와 함께 돌렸고, GCC와 MSVC는 확인하지 못했습니다.
동작 확인
| 확인 | 결과 |
|---|---|
make_heap의 결과 ({3,1,4,1,5}) | 5 3 4 1 1 (본문의 {5, 3, 4, 1, 1}과 같음) |
make_heap 비교 횟수 (무작위에 가까운 순열) | n=1,000일 때 1,835회, n=100,000일 때 185,699회. 모두 3n(3,000, 300,000) 아래이고 약 1.8n 수준 |
잘못된 순서: push_heap 먼저, push_back 나중 ({4,1,3} + 5) | 4 1 3 5, front()=4, is_heap=false |
pop_back을 pop_heap보다 먼저 호출 | 최댓값 5는 그대로 앞에 남고 {5,3,4,1}로 마지막 원소 1만 사라짐 |
최소 힙을 greater로 만든 뒤 push_heap은 기본 비교자 | is_heap(greater)가 false, front()=1이 아닌 상태로 힙 규칙이 깨짐 |
힙이 아닌 {9,2,7,4,1}에 sort_heap | 1 4 2 7 9, 정렬되지 않음 |
힙 {5,3,4,1,1}에 v[2] = 100 대입 | is_heap=false, is_heap_until이 인덱스 2를 돌려줌 (처음 깨진 위치) |
k == 0일 때 가드를 뺀 topK | libc++ 하드닝 모드에서 front() called on an empty vector 단언 실패 |
priority_queue<unique_ptr<int>>에서 std::move(q.top()) | 에러: call to implicitly-deleted copy constructor of 'unique_ptr<int>' (top()이 const 참조라서 이동이 아니라 복사로 해석됨) |
sort_heap을 힙이 아닌 구간에 쓰면 에러 없이 틀린 순서가 나온다는 점, 직접 값을 바꾸면is_heap_until로 깨진 위치를 찾을 수 있다는 점이 그대로 확인됐습니다. 본문이 권한assert(std::is_heap(...))가 실제로 이런 버그를 잡아냅니다.- 하드닝 모드의
front()단언은-D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_DEBUG를 켰을 때의 결과입니다. 기본 빌드에서는 정의되지 않은 동작이라 크래시 대신 쓰레기 값이 나올 수 있습니다.
성능
정수 500만 개를 무작위로 채워 3회 실행한 결과(ms)입니다.
| 작업 | 시간 |
|---|---|
make_heap 한 번 | 16~23 |
push_heap을 500만 번 | 43~45 |
힙 정렬 (make_heap + sort_heap) | 357~503 |
std::sort | 93~98 |
| 상위 100개를 찾는 방법 | 시간 |
|---|---|
크기 100짜리 최소 힙 유지 (본문 topK) | 3 |
partial_sort | 2 |
nth_element | 16 |
전체 std::sort | 87~88 |
(힙 방식을 뺀 나머지는 원본 복사 시간이 함께 들어 있습니다.)
- 한꺼번에 받은 데이터는
make_heap한 번이push_heap을 반복하는 것보다 약 2~3배 빨랐습니다. 본문의 “한꺼번에 받으면make_heap”이라는 권고와 맞습니다. 다만 무작위 데이터에서는push_heap의 평균 비용이 작아서 차이가 O(n)과 O(n log n)이 암시하는 것만큼 크지는 않았습니다. - 힙 정렬은
std::sort보다 3.7~5.3배 느렸습니다. 본문의 “캐시 효율이 나빠 실제로는std::sort보다 느린 경우가 대부분”이 이 환경에서 그대로 나왔습니다. - 상위 K개에서 본문은
partial_sort나nth_element가 “대개 더 빠르다”고 했는데, 이 측정에서는partial_sort가 힙 방식과 비슷하게(2ms 대 3ms) 빨랐고nth_element는 오히려 16ms로 더 느렸습니다. 이 구간에서nth_element는 K번째 경계를 맞추려고 전체를 한 번 분할하기 때문입니다. K가 작고 데이터가 크면 힙이나partial_sort가 낫고,nth_element는 경계 안의 원소 순서가 필요 없고 K가 클 때를 살펴볼 선택지라고 읽는 편이 맞습니다. - 한 머신에서 정수 데이터 하나로 잰 값입니다. 구조체처럼 큰 원소나 K가 큰 경우, 다른 컴파일러에서는 순서가 달라질 수 있습니다.