Vector heap vs std::priority_queue?

Use priority_queue when you only need push/top/pop. Use heap algorithms when you must splice the same range with other algorithms or inspect intermediate state.

Is the vector sorted after push_heap?

No — only the heap property holds. Use sort_heap for full order.

How do I get a min-heap?

Pass std::greater or an equivalent comparator consistently to all heap operations; same idea as priority_queue , greater >.

For large n and small K, a size-K heap or nth_element often beats sorting everything — profile your case.

C++ Heap Algorithms: make_heap, push_heap, pop_heap & sort_heap

2026년 3월 12일 · 16분 읽기 · 수정 2026년 3월 30일 Intermediate tutorial

이 글의 핵심

How heap algorithms work with vectors, how they compare to priority_queue, and when to use min/max heaps and top-K.

Heap algorithms

The standard default is a max-heap: with default std::less, v.front() is the largest element.

Operation	Precondition	Effect	Complexity (typical)
`make_heap(b, e)`	—	Rearrange `[b,e)` into a heap	Linear
`push_heap(b, e)`	`[b,e-1)` is heap; new at `e-1`	Insert into heap	Logarithmic
`pop_heap(b, e)`	`[b,e)` is heap	Move max to `e-1`, heap the rest	Logarithmic
`sort_heap(b, e)`	`[b,e)` is heap	Sort the range	O(n log n)

Typical sequence

Insert: v.push_back(x); then push_heap(v.begin(), v.end()).
Extract max: pop_heap(v.begin(), v.end()); then v.pop_back();.

Use is_heap / is_heap_until to debug broken invariants.

Relation to priority_queue

std::priority_queue is usually vector + push_heap / pop_heap, with a simpler interface. Direct heap algorithms help when you split one range into heap and non-heap parts or need custom pipelines.

Min-heap: std::make_heap(v.begin(), v.end(), std::greater<>()); — use the same Compare for every heap call or you get undefined behavior.

Custom comparators

The element that should be “first” (highest priority) must compare as smallest according to Compare for make_heap with std::less-style APIs — mirror priority_queue rules and stay consistent across make_heap, push_heap, pop_heap, sort_heap.

Top-K

Maintaining a size-K min-heap while scanning n elements yields O(n log K) for “largest K” variants. For K ≈ n, consider partial_sort or nth_element.

Heap 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());

Do not call sort_heap on a non-heap range — call make_heap first.

FAQ (abbreviated)

Q: What is a heap here? Max/min heap layout in a random-access range.

Q: make_heap? Builds a heap from a range.

Q: push_heap / pop_heap? Insert / extract according to heap rules.

Q: priority_queue? Convenient adapter; same underlying idea.

Q: Reading? Introduction to Algorithms, Effective STL, cppreference.

C++ Algorithm Numeric
C++ Algorithm Reverse
C++ Algorithm Count

Keywords

make_heap, push_heap, pop_heap, sort_heap, priority_queue, std::greater, STL