What is Heap Operations in C++?

Algorithms for creating, maintaining, querying, and sorting heap-ordered ranges in-place using random-access iterators.

Which C++ standard introduced Heap Operations?

Heap Operations was introduced in C++98.

What is the difficulty level of Heap Operations?

Heap Operations is considered Intermediate-level C++ material.

Heap Operations

Heap Operationssince C++98

A family of <algorithm> functions that create, extend, shrink, validate, and sort ranges satisfying the heap property — where the first element is always the maximum under a given comparator.

Overview

A heap in this context is a range [first, last) stored in a flat, random-access container where *first is the greatest element and every parent is no less than its children (a max-heap). The invariant is defined relative to a comparator comp; the default is std::less<>, which makes the greatest element the root. These algorithms never allocate memory — they rearrange elements in-place. They are the implementation substrate of std::priority_queue.

Six functions cover the complete heap lifecycle:

Function	Complexity	Introduced
`std::make_heap`	O(N)	C++98
`std::push_heap`	O(log N)	C++98
`std::pop_heap`	O(log N)	C++98
`std::sort_heap`	O(N log N)	C++98
`std::is_heap`	O(N)	C++11
`std::is_heap_until`	O(N)	C++11

C++17 added parallel execution-policy overloads for std::is_heap and std::is_heap_until. C++20 introduced std::ranges:: counterparts for all six, with projection support.

Syntax

cpp

Godbolt

#include <algorithm>

// Create a heap from an arbitrary range (linear time)
void make_heap(RaIt first, RaIt last);
void make_heap(RaIt first, RaIt last, Compare comp);

// Extend: [first, last-1) must already be a heap; incorporates *(last-1)
void push_heap(RaIt first, RaIt last);
void push_heap(RaIt first, RaIt last, Compare comp);

// Shrink: moves *first to *(last-1); [first, last-1) becomes a valid heap
void pop_heap(RaIt first, RaIt last);
void pop_heap(RaIt first, RaIt last, Compare comp);

// Sort ascending; requires a valid heap as input; destroys heap property
void sort_heap(RaIt first, RaIt last);
void sort_heap(RaIt first, RaIt last, Compare comp);

// Query whether range satisfies heap property (C++11)
bool    is_heap(RaIt first, RaIt last);
bool    is_heap(RaIt first, RaIt last, Compare comp);

// Returns iterator to first element violating heap property (C++11)
RaIt    is_heap_until(RaIt first, RaIt last);
RaIt    is_heap_until(RaIt first, RaIt last, Compare comp);

// Parallel overloads for is_heap / is_heap_until only (C++17)
bool    is_heap(ExecutionPolicy&& pol, RaIt first, RaIt last);
RaIt    is_heap_until(ExecutionPolicy&& pol, RaIt first, RaIt last);

All comparator-taking overloads require strict weak ordering. The same comparator must be used consistently across every operation on a given heap — mixing comparators silently corrupts the invariant.

Examples

Basic heap lifecycle

cpp

Godbolt

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

int main() {
    std::vector<int> v{4, 3, 2, 1, 5, 6, 7, 9, 10};

    std::make_heap(v.begin(), v.end());   // O(N); v[0] == 10
    std::cout << v.front() << '\n';       // 10

    // Step 1: append to the vector; Step 2: sift up
    v.push_back(100);
    std::push_heap(v.begin(), v.end());   // O(log N); v[0] == 100

    // Step 1: move max to back; Step 2: erase from vector
    std::pop_heap(v.begin(), v.end());    // O(log N)
    int top = v.back();
    v.pop_back();
    std::cout << top << '\n';             // 100
}

The two-step protocol for push_heap and pop_heap is deliberate: the algorithms never resize the container, so the caller retains full control over allocation.

Min-heap via custom comparator

cpp

Godbolt

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

int main() {
    std::vector<int> v{5, 3, 8, 1, 9, 2};

    // std::greater inverts the comparison → minimum element at front
    std::make_heap(v.begin(), v.end(), std::greater<int>{});
    std::cout << v.front() << '\n';  // 1

    v.push_back(0);
    std::push_heap(v.begin(), v.end(), std::greater<int>{});
    std::cout << v.front() << '\n';  // 0

    std::pop_heap(v.begin(), v.end(), std::greater<int>{});
    int min = v.back();  // 0
    v.pop_back();
}

Heap sort

cpp

Godbolt

#include <algorithm>
#include <vector>

// O(N log N) in-place, ascending. Not stable.
std::vector<int> heap_sort(std::vector<int> v) {
    std::make_heap(v.begin(), v.end());   // O(N)
    std::sort_heap(v.begin(), v.end());   // O(N log N) — ascending order
    return v;                             // heap property is destroyed
}

sort_heap produces ascending order from a max-heap because it repeatedly pops the maximum to the back and shrinks the active heap range.

Validating heap integrity (C++11)

cpp

Godbolt

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

void demonstrate() {
    std::vector<int> v{9, 5, 7, 1, 3, 2};

    assert(!std::is_heap(v.begin(), v.end()));  // C++11 — not yet a heap

    std::make_heap(v.begin(), v.end());
    assert(std::is_heap(v.begin(), v.end()));   // C++11 — now valid

    // Corrupt the heap by direct mutation — never do this in production
    v[1] = 999;
    auto it = std::is_heap_until(v.begin(), v.end());  // C++11
    // 'it' points to the first element violating the heap property
    std::cout << "violation at index "
              << std::distance(v.begin(), it) << '\n';
}

std::is_heap_until is invaluable in assertions and post-condition checks to pinpoint exactly where an invariant breaks.

Efficient bulk insertion

cpp

Godbolt

#include <algorithm>
#include <vector>

// Inserting N elements one-by-one: O(N log N)
void slow_way(std::vector<int>& heap, const std::vector<int>& incoming) {
    for (int x : incoming) {
        heap.push_back(x);
        std::push_heap(heap.begin(), heap.end());
    }
}

// Append all then heapify: O(N) — prefer this for batch inserts
void fast_way(std::vector<int>& heap, const std::vector<int>& incoming) {
    heap.insert(heap.end(), incoming.begin(), incoming.end());
    std::make_heap(heap.begin(), heap.end());
}

C++20 ranges interface

cpp

Godbolt

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

int main() {
    std::vector<int> v{4, 1, 7, 3, 9, 2};

    std::ranges::make_heap(v);           // C++20 — accepts range directly
    std::cout << v.front() << '\n';      // 9

    v.push_back(15);
    std::ranges::push_heap(v);           // C++20
    std::cout << v.front() << '\n';      // 15

    std::ranges::pop_heap(v);            // C++20
    v.pop_back();

    std::ranges::sort_heap(v);           // C++20 — ascending order
}

The ranges versions eliminate the begin/end boilerplate and support projections, letting you heap on a struct member without a custom comparator lambda.

Best Practices

Keep comparator and container together. Because the same comparator must be threaded through every call, inconsistency is easy to introduce across call sites. Encapsulate both in a thin wrapper or, for most use cases, just use std::priority_queue instead.

Prefer std::priority_queue for encapsulation. The raw algorithms demand that callers manually uphold invariants. std::priority_queue enforces the two-step push and pop protocols automatically at zero additional cost. Reach for the bare algorithms only when you need simultaneous access to the underlying storage — e.g., to inspect all elements, serialise the container, or call sort_heap to consume the heap as a sorted sequence.

Gate is_heap behind NDEBUG. The O(N) check is a powerful invariant guard in debug builds:

cpp

Godbolt

assert(std::is_heap(v.begin(), v.end(), comp));

In release mode this disappears entirely; in debug mode it catches silent corruption immediately.

Batch-insert with make_heap, not repeated push_heap. Adding N elements via push_heap costs O(N log N); appending them all then calling make_heap once costs O(N). The savings are significant for large N.

Common Pitfalls

Direct mutation invalidates the heap. Assigning to an element inside the heap range (e.g., v[2] = 999) changes a value without rebalancing the tree. All modifications must go through push_heap and pop_heap.

Calling push_heap without first appending the element. push_heap's precondition is that [first, last-1) is already a valid heap and *(last-1) is the candidate element. Calling it on a range where the last element hasn't been placed there first is undefined behavior.

Calling pop_heap then forgetting to erase. After std::pop_heap, the maximum element is at v.back() but the vector's size is unchanged — the displaced element remains in the live range. Forgetting v.pop_back() leaves it there to corrupt the next operation.

Passing a non-heap to sort_heap. The precondition is a valid heap. Calling sort_heap on an arbitrary range is undefined behavior; always call make_heap first if the heap status is unknown.

Mismatched comparators with sort_heap. A heap built with std::greater and sorted with the default std::less will produce incorrect results. If you built a min-heap with std::greater, pass std::greater to sort_heap as well — the sorted output will then be in descending order.

make_heap and sort_heap have no parallel overloads. In C++17, only is_heap and is_heap_until gained ExecutionPolicy overloads. The construction and sorting algorithms remain sequential.