Skip to content
Tutorials Center
My learning

Topics

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.

C++
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

C++ A max-heap in a vector

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.

C++ Min-heap, sort_heap and a custom type

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

C++
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_heap the old top is at back(); you read it and call pop_back(). For push_heap you call push_back() first.
  • Complexity: make_heap is O(n), push_heap and pop_heap are O(log n), sort_heap is O(n log n).
  • Same comparator every time. Mixing a default call with a std::greater call 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_element or partial_sort is simpler.
  • std::priority_queue is a thin wrapper over exactly these algorithms and is easier when you do not need to access the container.
  • Heap sort: make_heap followed by sort_heap is in-place heap sort; it is not stable.