How to Use STL Heap Algorithms in C++

Use C++ STL heap algorithms to turn a std::vector range into a max-heap, sort that range, or move its largest value to the end. std::pop_heap moves the value; erase it separately if you want to remove it from the vector.

Use the std::make_heap Function to Convert a Range Into a Heap

A heap is a range arranged to satisfy a parent-child rule. With the default comparison, std::make_heap creates a max-heap: each parent is greater than or equal to its children, so the largest value is at the front. For a vector-backed binary heap, the children of the element at index i are at 2 * i + 1 and 2 * i + 2, when those positions are within the range. A min-heap uses a different comparison, such as std::greater<int>.

std::make_heap rearranges the elements to satisfy the heap property; it does not sort the entire range. Many arrangements can satisfy the same property, so code should depend on the front value and parent-child comparisons rather than a particular sequence of values after the call.

The following standalone example builds a heap and checks its parent-child rule. It was executed successfully; the observed output is shown below.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{11, 82, 39, 72, 51, 32, 91};
    std::make_heap(values.begin(), values.end());

    bool is_max_heap = true;
    for (std::size_t child = 1; child < values.size(); ++child) {
        const std::size_t parent = (child - 1) / 2;
        if (values[parent] < values[child]) {
            is_max_heap = false;
            break;
        }
    }

    std::cout << "max-heap: " << std::boolalpha << is_max_heap << '\n';
    std::cout << "top: " << values.front() << '\n';
}

max-heap: true
top: 91

The front element is the heap’s top value. The vector’s remaining order is only constrained by the heap property, which is why it should not be treated as an ascending or descending list.

Use the std::sort_heap Function to Sort a Heap Range

Call std::sort_heap on a range that already satisfies the heap property. With the default comparison, it rearranges the range into ascending order. After sorting, the range no longer satisfies the heap property, so call std::make_heap again before using a heap operation on the full range.

For example, after std::make_heap(values.begin(), values.end()), call std::sort_heap(values.begin(), values.end()) to sort the same range. The default comparison produces ascending order.

The overload with a comparator accepts a function or function object that defines the ordering. Use the same comparison when constructing and sorting a heap; for example, a heap built with std::greater<int> must be sorted with that comparator. The default overload is suitable when ascending output is the goal.

Use the std::pop_heap Function to Remove the Next Element in the Heap

std::pop_heap moves the top value to the last position in the range and restores the heap property in the preceding range. It does not change the vector’s size. To remove that value from the container, call pop_back() after std::pop_heap.

To add an element, append it to the vector and call std::push_heap. The range before the appended element must already be a heap; std::push_heap then restores the heap property across the enlarged range. For both algorithms, use the same comparator that defines the heap.

This standalone example checks the moved top value, erases it separately, and then adds a value while maintaining the heap. It was executed successfully; the observed output is shown below.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{11, 82, 39, 72, 51, 32, 91};
    std::make_heap(values.begin(), values.end());

    std::pop_heap(values.begin(), values.end());
    std::cout << "moved top: " << values.back() << '\n';
    values.pop_back();

    values.push_back(95);
    std::push_heap(values.begin(), values.end());
    std::cout << "new top: " << values.front() << '\n';
}

moved top: 91
new top: 95

After std::pop_heap, the prefix ending before the final element is the heap to reuse. Once pop_back() removes the final value, the vector itself again contains exactly that heap range. Appending without first preserving this invariant does not meet std::push_heap’s precondition.