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.

C++20 Ranges Equivalents

All six heap algorithms gained std::ranges:: counterparts in C++20. They are niebloids — algorithm function objects, not plain function templates — which means ADL cannot find them and explicit template arguments cannot be supplied. The full signatures accept an optional comparator and an optional projection:

cpp

Godbolt

#include <algorithm>  // all ranges:: heap algorithms live here

// Overload (1): iterator-sentinel pair
std::ranges::make_heap(first, last, comp = {}, proj = {});

// Overload (2): range directly — eliminates begin/end boilerplate
std::ranges::make_heap(r, comp = {}, proj = {});

// Same two-overload pattern for all six:
std::ranges::push_heap(r, comp = {}, proj = {});
std::ranges::pop_heap(r, comp = {}, proj = {});
std::ranges::sort_heap(r, comp = {}, proj = {});
std::ranges::is_heap(r, comp = {}, proj = {});        // → bool
std::ranges::is_heap_until(r, comp = {}, proj = {});  // → borrowed_iterator

Projections are the main ergonomic win over the classic algorithms. They let you heap on a derived key — a struct member, a computed value — without writing a comparison lambda that dereferences the full object:

cpp

Godbolt

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

struct Task {
    std::string name;
    int priority;
};

int main() {
    std::vector<Task> tasks{
        {"render",  3},
        {"network", 9},
        {"audio",   5},
        {"input",   7},
    };

    // Build a max-heap ordered by Task::priority — no lambda needed
    std::ranges::make_heap(tasks, {}, &Task::priority);
    std::cout << tasks.front().name << '\n';  // "network" (priority 9)

    tasks.push_back({"physics", 11});
    std::ranges::push_heap(tasks, {}, &Task::priority);
    std::cout << tasks.front().name << '\n';  // "physics" (priority 11)

    // Pop the highest-priority task
    std::ranges::pop_heap(tasks, {}, &Task::priority);
    Task top = std::move(tasks.back());
    tasks.pop_back();
    std::cout << "dispatching: " << top.name << '\n';  // "physics"

    // Validate with is_heap
    bool ok = std::ranges::is_heap(tasks, {}, &Task::priority);
    std::cout << std::boolalpha << ok << '\n';  // true
}

Note: the ranges versions have no parallel execution-policy overloads — std::execution::par cannot be combined with std::ranges:: algorithms. For parallel is_heap/is_heap_until, continue using the classic iterator-based overloads with an execution policy.

`std::priority_queue` vs Manual Heap Operations

std::priority_queue is the right default. It enforces the two-step push/pop protocol automatically, prevents accidental direct mutation, and has zero overhead relative to raw heap operations — it is implemented on top of them. Choose based on what you need from the underlying storage:

Situation	Prefer
Simple priority-ordered processing, no need to inspect all elements	`std::priority_queue`
Need to iterate or serialize all elements	Raw heap + `std::vector`
Need to call `sort_heap` to consume in sorted order	Raw heap (avoids copy-out)
Batch load then process — use `make_heap` once	Both work; raw heap makes it explicit
Need a custom allocator on the container	`std::priority_queue<T, std::vector<T, A>, Comp>`

When you need to inspect the underlying data, std::priority_queue requires a subclass or std::move-out trick. Raw heap operations on a std::vector give you direct access at all times:

cpp

Godbolt

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

int main() {
    // priority_queue: no direct access to all elements
    std::priority_queue<int> pq;
    for (int x : {5, 1, 9, 3, 7}) pq.push(x);
    // Can only see pq.top(); cannot iterate without destructive pops

    // Raw heap on vector: full visibility at any point
    std::vector<int> v{5, 1, 9, 3, 7};
    std::make_heap(v.begin(), v.end());

    // Inspect all elements freely (order within heap is unspecified except v[0])
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';  // e.g. 9 7 5 3 1 (heap order, not sorted)

    // Consume as sorted sequence without an extra container
    std::sort_heap(v.begin(), v.end());
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';  // 1 3 5 7 9
}

The pop_heap + pop_back pattern from raw heap operations also enables a trick that std::priority_queue cannot do: modify the top element in-place before reinserting it, as shown in the "Efficient bulk insertion" example from Šimon Tóth — pop_heap, mutate v.back(), then push_heap.

K-Way Merge Pattern

Merging K sorted ranges into a single sorted output is a classic heap application. A min-heap of size K tracks the current front element from each source; each extraction costs O(log K), giving O(N log K) total where N is the combined element count.

cpp

Godbolt

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

// Merge k sorted vectors into one sorted vector.
// Each heap entry: {value, source_index, position_in_source}
std::vector<int> merge_k_sorted(const std::vector<std::vector<int>>& sources) {
    using Entry = std::tuple<int, std::size_t, std::size_t>;  // value, src, pos

    // Seed the min-heap with the first element of each non-empty source
    std::vector<Entry> heap;
    heap.reserve(sources.size());
    for (std::size_t s = 0; s < sources.size(); ++s) {
        if (!sources[s].empty())
            heap.emplace_back(sources[s][0], s, 0);
    }

    // Min-heap: smallest value at front
    auto cmp = std::greater<Entry>{};
    std::make_heap(heap.begin(), heap.end(), cmp);

    std::vector<int> result;
    while (!heap.empty()) {
        std::pop_heap(heap.begin(), heap.end(), cmp);
        auto [val, src, pos] = heap.back();
        heap.pop_back();

        result.push_back(val);

        // Advance to the next element in the same source, if any
        if (pos + 1 < sources[src].size()) {
            heap.emplace_back(sources[src][pos + 1], src, pos + 1);
            std::push_heap(heap.begin(), heap.end(), cmp);
        }
    }
    return result;
}

int main() {
    std::vector<std::vector<int>> sources{
        {1, 4, 7},
        {2, 5, 8},
        {3, 6, 9},
    };
    auto merged = merge_k_sorted(sources);
    for (int x : merged) std::cout << x << ' ';
    std::cout << '\n';  // 1 2 3 4 5 6 7 8 9
}

The comparator std::greater<Entry> makes std::tuple comparison flip to minimum-at-front because pop_heap always surfaces the element that compares greater than all others under the supplied comparator — using greater inverts that to yield the minimum.

Partial Sort via Heap (K Largest Elements)

Finding the K largest elements costs O(N + K log N): one linear make_heap pass then K pops, each O(log N). This beats a full std::sort at O(N log N) when K is small relative to N, and beats std::partial_sort (O(N log K)) for large K with small N.

cpp

Godbolt

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

// Extract the k largest elements from v, returned in descending order.
// v is modified in-place: the k largest end up sorted at the back.
void find_k_largest(std::vector<int>& v, int k) {
    // O(N): establish max-heap so v[0] is the largest
    std::make_heap(v.begin(), v.end());

    // O(k log N): pop the max k times; each pop moves it to the shrinking tail
    for (int i = 0; i < k; ++i) {
        std::pop_heap(v.begin(), v.end() - i);
        // After pop i: v[v.size()-1-i] holds the (i+1)-th largest value
    }
    // v.end()-k .. v.end() now contains the k largest, in ascending order
}

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

    std::cout << k << " largest: ";
    for (auto it = v.end() - k; it != v.end(); ++it)
        std::cout << *it << ' ';
    std::cout << '\n';  // 5 5 6 9  (the four largest, ascending)
}

Contrast with std::partial_sort(v.begin(), v.begin() + k, v.end(), std::greater<int>{}), which sorts the K largest into the front of the range in O(N log K). The heap approach is preferable when you want to defer the final sort or intend to call sort_heap over the result anyway.