C++ Reference ยท Algorithms
The std::make_heap, push_heap and pop_heap algorithms
Reference for C++ make_heap, push_heap, pop_heap, sort_heap and is_heap: build a binary max-heap in a vector, with complexity and std::priority_queue links.
The heap algorithms treat a random-access range as a binary heap. By default it is a max-heap: the largest element is at the front (v.front()), and every parent is not less than its children. The heap lives inside your own container, usually a std::vector, which makes it a flexible alternative to std::priority_queue.
The family has five members. make_heap turns an arbitrary range into a heap. push_heap restores the heap after you appended an element with push_back. pop_heap moves the top element to the back (you then pop_back it). sort_heap turns a heap into a sorted ascending range. is_heap tests the property.
std::make_heap(v.begin(), v.end()); v.push_back(x); std::push_heap(v.begin(), v.end()); std::pop_heap(v.begin(), v.end()); v.pop_back();
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Syntax
template<class RandomIt> void make_heap(RandomIt first, RandomIt last); template<class RandomIt> void push_heap(RandomIt first, RandomIt last); template<class RandomIt> void pop_heap(RandomIt first, RandomIt last); template<class RandomIt> void sort_heap(RandomIt first, RandomIt last); template<class RandomIt> bool is_heap(RandomIt first, RandomIt last); template<class RandomIt> RandomIt is_heap_until(RandomIt first, RandomIt last); // each has an overload taking Compare comp as the last argument
| Name | Description |
|---|---|
first, last |
The random-access range that holds (or will hold) the heap. |
comp |
Strict weak ordering. With the default < you get a max-heap; with std::greater a min-heap. |
Returns: nothing, except is_heap (bool) and is_heap_until (the first element that breaks the property).
Errors / undefined behavior: push_heap and pop_heap require the range (minus the new element for push_heap) to already be a heap under the same comparator. pop_heap on an empty range is undefined; so is pop_back on an empty vector afterwards.
Usage notes
- Two-step pop and push: the algorithms never change the container size. After
pop_heapthe old top is atback(); you read it and callpop_back(). Forpush_heapyou callpush_back()first. - Complexity:
make_heapis O(n),push_heapandpop_heapare O(log n),sort_heapis O(n log n). - Same comparator every time. Mixing a default call with a
std::greatercall on the same heap corrupts it. - Only the front is ordered. The rest of the vector is in heap order, not sorted order; do not iterate it expecting sorted output.
- Top-k: to get the k smallest or largest values of a stream, keep a heap of size k. For a one-off,
std::nth_elementorpartial_sortis simpler. std::priority_queueis a thin wrapper over exactly these algorithms and is easier when you do not need to access the container.- Heap sort:
make_heapfollowed bysort_heapis in-place heap sort; it is not stable.