C++ Heap Algorithms: make_heap, push_heap, pop_heap

By 0xmote · Apr 27, 2026 · 23 min read · Updated Sep 27, 2026 Intermediate Tutorial

Key takeaways

The heap algorithms only rearrange a range, so forgetting push_back before push_heap or pop_back after pop_heap silently corrupts the heap. The post explains the heap invariant, each function's preconditions and cost, priority_queue as a wrapper, comparator pitfalls, and common heap bugs.

Why Heap Algorithms Matter

If you have solved competitive programming problems, built a job scheduler, or implemented Dijkstra’s shortest path, you have almost certainly reached for a heap without necessarily thinking about how it is implemented under the hood. In C++, the heap is not a class you instantiate — it is a property that an existing random-access range can satisfy, maintained by a family of free functions declared in <algorithm>: std::make_heap, std::push_heap, std::pop_heap, std::sort_heap, and the query functions std::is_heap / std::is_heap_until. This design choice is deliberate and worth understanding before you write a single line of heap code, because it explains both the power of these functions and the sharp edges that trip up even experienced developers.

Note: this post focuses on how the free heap algorithms work internally and how they relate to std::priority_queue. If you want a more compact, example-first walkthrough of the same four functions, see the companion guide C++ Algorithm Heap — the two are written for different reading styles rather than covering the same ground twice.

Problem: Priority Queue Operations

Problem: You need:

Fast access to max/min element (O(1))
Efficient insertion (O(log n))
Efficient removal (O(log n)) Solution: Heap data structure (binary heap).

flowchart TD
    subgraph Max Heap
        A[100]
        B[80]
        C[90]
        D[50]
        E[70]
        F[60]
        G[85]
        A --> B
        A --> C
        B --> D
        B --> E
        C --> F
        C --> G
    end

Heap property: Parent ≥ children (max heap) or parent ≤ children (min heap).

A binary heap is a complete binary tree — every level is fully filled except possibly the last, and the last level fills left to right — that additionally satisfies the heap property shown above. Because the tree is complete, it can be stored compactly in a flat array with no pointers at all: the parent-child relationship is purely arithmetic (index i’s children live at 2i+1 and 2i+2), so traversing “up” or “down” the tree is just index arithmetic on a contiguous buffer. This is exactly why std::vector is the natural backing store for a heap, and why the standard library expresses heap operations as algorithms over an iterator range (RandomAccessIterator first, RandomAccessIterator last) rather than as methods on a dedicated Heap<T> container.

That separation between algorithm and container is the STL’s central design idea, and heaps are a particularly good illustration of why it pays off: make_heap/push_heap/pop_heap do not know or care whether the underlying storage is a std::vector, a std::deque, or a raw array, as long as you can hand them random-access iterators. You can heapify part of a buffer you already own, interleave heap operations with ordinary vector operations like reserve or resize, or reuse the same storage for a heap sort without ever allocating a wrapper object. The cost of that flexibility is that the algorithms have no memory of their own — every function only rearranges elements that already exist in [first, last); none of them can grow or shrink the underlying container. That single fact is the root cause of the most common heap bug in C++, covered in detail in the pop_heap section below.

Heap Fundamentals

Binary Heap Structure

Binary heap: Complete binary tree stored in array.

Array: [100, 80, 90, 50, 70, 60, 85]
Index:   0   1   2   3   4   5   6
Tree:
       100
      /   \
    80     90
   / \    / \
  50 70  60 85

Parent-child relationship:

Parent of i: (i - 1) / 2
Left child of i: 2 * i + 1
Right child of i: 2 * i + 2

These three formulas are the entire “structure” of a binary heap — there is no explicit tree object, no left/right pointers to allocate or follow. Compare that to a linked binary search tree, where every node needs pointer storage and every traversal chases pointers around the heap (in the memory-allocation sense, not the data-structure sense — the name overlap is a frequent source of confusion for beginners). An array-based heap, by contrast, is cache-friendly: index arithmetic on a contiguous vector<int> means sequential-ish memory access patterns, which in practice makes heap operations considerably faster than their asymptotic complexity alone would suggest, especially for the int/double-sized elements common in competitive programming and scheduling code.

Max Heap vs Min Heap

Type	Property	Root
Max heap	Parent ≥ children	Maximum element
Min heap	Parent ≤ children	Minimum element

C++‘s heap algorithms default to a max heap because the default comparator is std::less<T>, and the convention is “the comparator answers whether the first argument should sort before — i.e., be considered lower priority than — the second.” Passing std::greater<T> flips that ordering, which is why every min-heap example in this guide swaps in std::greater. This is a common point of confusion: many developers expect std::less to mean “produces an ascending, min-first order” by analogy with std::sort, but for heaps it means the opposite. If your heap keeps popping the wrong extreme, check your comparator direction first — it is the single most common heap bug after the pop_heap/pop_back mistake described later in this post.

Complexity at a Glance

Operation	Complexity	Why
`make_heap`	O(n)	Bottom-up heapify only sifts internal nodes, not every element individually
`push_heap`	O(log n)	Sift-up walks at most `log₂ n` levels from a leaf to the root
`pop_heap`	O(log n)	Sift-down walks at most `log₂ n` levels from the root to a leaf
`sort_heap`	O(n log n)	Repeated `pop_heap` over the whole range — n pops, each O(log n)
`is_heap` / `is_heap_until`	O(n)	Must inspect every parent-child pair in the worst case

The make_heap complexity deserves a second look because it is easy to guess wrong. Calling push_heap n times to build a heap one element at a time costs O(n log n) in total, since each individual push is O(log n). make_heap, however, does not do that — it uses Floyd’s bottom-up build-heap algorithm, which sifts down starting from the last internal (non-leaf) node and works backward toward the root. Because most nodes in a complete binary tree are near the bottom (where a sift-down has very little distance left to travel), the total work sums to O(n), not O(n log n). This is a genuinely non-obvious result — the proof involves summing a geometric-like series over tree heights — but the practical takeaway is simple: always prefer make_heap over a loop of push_heap calls when you are heapifying a range you already have, and reserve push_heap for genuinely incremental insertion into a heap that is already valid.

make_heap: Build Heap

Syntax

template<class RandomIt>
void make_heap(RandomIt first, RandomIt last);
template<class RandomIt, class Compare>
void make_heap(RandomIt first, RandomIt last, Compare comp);

Example: Max Heap

#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};
    
    std::make_heap(vec.begin(), vec.end());
    
    std::cout << "Max heap: ";
    for (int x : vec) {
        std::cout << x << " ";
    }
    std::cout << "\n";
    
    std::cout << "Max element: " << vec.front() << "\n";
}

Output:

Max heap: 9 6 4 3 5 1 2 1
Max element: 9

Complexity: O(n)

Note that the resulting order — 9 6 4 3 5 1 2 1 — is not fully sorted; it is only “heap-ordered,” meaning every parent satisfies the heap property relative to its children, but siblings and distant relatives can appear in any order. This surprises newcomers who expect make_heap to behave like sort. The only guarantee a valid max heap gives you is that front() holds the maximum element — nothing about the relative order of the rest of the array. If you need the full ordering, call sort_heap afterward (covered below), which is a different operation with a different, more expensive complexity.

Example: Min Heap

std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};
std::make_heap(vec.begin(), vec.end(), std::greater<int>());
std::cout << "Min heap: ";
for (int x : vec) {
    std::cout << x << " ";
}
std::cout << "\n";
std::cout << "Min element: " << vec.front() << "\n";

Output:

Min heap: 1 1 2 3 5 9 4 6
Min element: 1

push_heap: Insert Element

Syntax

template<class RandomIt>
void push_heap(RandomIt first, RandomIt last);

Usage

Precondition: [first, last-1) is already a heap, and the new element to insert has already been placed at *(last-1) — typically via push_back.

This precondition is where the “algorithms don’t own the container” design becomes concrete. push_heap cannot insert an element into the vector for you, because it only receives a pair of iterators, not the vector itself — it has no way to call push_back. So the calling code is always a two-step dance: first grow the container by one element (push_back), then ask push_heap to restore the heap property over the now-larger range. Forgetting the push_back and calling push_heap on an unchanged range is undefined behavior, since push_heap assumes the “new” last element is already sitting there waiting to be sifted up.

std::vector<int> vec = {9, 6, 4, 3, 5, 1, 2, 1};
// vec is already a max heap
vec.push_back(8);  // Add to end
std::push_heap(vec.begin(), vec.end());  // Restore heap property
std::cout << "After push: ";
for (int x : vec) {
    std::cout << x << " ";
}
std::cout << "\n";
std::cout << "Max element: " << vec.front() << "\n";

Output:

After push: 9 8 4 6 5 1 2 1 3
Max element: 9

Complexity: O(log n)

How push_heap Works

flowchart TD
    A[1. Add element to end]
    B[2. Compare with parent]
    C{Parent < child?}
    D[3. Swap with parent]
    E[4. Move up]
    F[Done]
    A --> B
    B --> C
    C -->|Yes| D
    D --> E
    E --> B
    C -->|No| F

This process is called sift-up (or “bubble-up”): the newly appended element starts life at the bottom of the tree and repeatedly compares itself against its parent, swapping upward whenever it violates the heap property, until either it finds a parent it is not “greater than” (for a max heap) or it reaches the root. Because a complete binary tree of n elements has height ⌈log₂(n+1)⌉, the element can travel at most that many levels — which is exactly where the O(log n) bound comes from. In the worst case (inserting a new maximum), the element sifts all the way to the root; in the best case (inserting a new minimum into a max heap), it does not move at all and the call is effectively O(1).

pop_heap: Remove Max

Syntax

template<class RandomIt>
void pop_heap(RandomIt first, RandomIt last);

Usage

Postcondition: Max element moved to last-1, [first, last-1) is heap.

Read that postcondition carefully, because it is the single most misunderstood line in all of <algorithm>’s heap interface: pop_heap does not remove anything from the container. The name is misleading by analogy with std::stack::pop() or std::vector::pop_back(), which do shrink their container. pop_heap only rearranges the range — it swaps the maximum (at first) with the last element, then sifts the new root down to restore the heap property over [first, last-1). The former maximum is left sitting at *(last-1), still logically part of the vector, just now outside the heap-ordered portion. If you stop there, vec.size() is unchanged and the “removed” element is still occupying storage — you must call vec.pop_back() yourself to actually shrink the container and reclaim that slot. This two-step pattern (pop_heap then pop_back) mirrors push_back then push_heap for insertion, and forgetting either half is the most common heap-related bug reported in C++ code review: omitting pop_back() leaves a stale duplicate “maximum” in the vector that silently corrupts every subsequent heap operation, because algorithms downstream will treat the whole [first, last) range — max included — as heap-ordered data when it no longer is.

std::vector<int> vec = {9, 8, 4, 6, 5, 1, 2, 1, 3};
// vec is a max heap
std::pop_heap(vec.begin(), vec.end());  // Move max to end
int max = vec.back();
vec.pop_back();  // Remove max
std::cout << "Popped: " << max << "\n";
std::cout << "After pop: ";
for (int x : vec) {
    std::cout << x << " ";
}
std::cout << "\n";

Output:

Popped: 9
After pop: 8 6 4 3 5 1 2 1

Complexity: O(log n)

How pop_heap Works

flowchart TD
    A[1. Swap root with last]
    B[2. Move last to end]
    C[3. Compare with children]
    D{Smaller than max child?}
    E[4. Swap with max child]
    F[5. Move down]
    G[Done]
    A --> B
    B --> C
    C --> D
    D -->|Yes| E
    E --> F
    F --> C
    D -->|No| G

This is the mirror image of push_heap’s sift-up and is usually called sift-down (or “heapify-down”). Once the old root and the old last element have swapped, the algorithm compares the new root against its two children, swaps with whichever child is larger (for a max heap — swapping with the smaller one would not restore the property), and repeats until the displaced value either has no larger child or has reached a leaf. As with push_heap, the number of swaps is bounded by the tree height, giving O(log n). One subtlety worth internalizing: sift-down must compare against both children and pick the larger, whereas sift-up only ever compares against a single parent — this asymmetry is why the two operations, despite looking superficially similar, are implemented as genuinely different traversal logic in every standard library.

sort_heap: Heap Sort

Syntax

template<class RandomIt>
void sort_heap(RandomIt first, RandomIt last);

Usage

Precondition: [first, last) is a heap. Postcondition: [first, last) is sorted (ascending for max heap).

std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};
std::make_heap(vec.begin(), vec.end());
std::cout << "Heap: ";
for (int x : vec) {
    std::cout << x << " ";
}
std::cout << "\n";
std::sort_heap(vec.begin(), vec.end());
std::cout << "Sorted: ";
for (int x : vec) {
    std::cout << x << " ";
}
std::cout << "\n";

Output:

Heap: 9 6 4 3 5 1 2 1
Sorted: 1 1 2 3 4 5 6 9

Complexity: O(n log n) Note: After sort_heap, the range is no longer a heap.

sort_heap is essentially heapsort spelled out as a library call: internally it repeatedly applies the same pop_heap logic — swap the current maximum to the (shrinking) end of the range and sift the new root down — until the entire range is exhausted, at which point the array happens to be in ascending order (for a max heap; a min-heap built with std::greater sorts into descending order under sort_heap, which is a frequent source of confusion). Because it performs n pop-style operations at O(log n) each, the total cost is O(n log n) — the same asymptotic bound as std::sort. In practice, std::sort’s introsort is usually faster in wall-clock terms thanks to a better cache-access pattern and a insertion-sort fallback for small ranges, so sort_heap is rarely the right tool when your only goal is “sort this data.” Where sort_heap genuinely earns its place is when you already have a heap sitting in memory — for example, you built one incrementally with push_heap while streaming data in — and you want the final sorted output without allocating a separate structure or restarting the sort from scratch with std::sort.

priority_queue: Container Adapter

What is priority_queue?

priority_queue: Container adapter that wraps heap operations.

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

std::priority_queue is not a separately-implemented data structure — every major standard library implementation (libstdc++, libc++, MSVC STL) builds it directly on top of the exact same make_heap/push_heap/pop_heap algorithms covered above, applied to an internal Container (a std::vector<T> by default). Conceptually, pq.push(x) is equivalent to c.push_back(x); std::push_heap(c.begin(), c.end(), comp);, and pq.pop() is equivalent to std::pop_heap(c.begin(), c.end(), comp); c.pop_back(); — the container adapter simply performs the two-step dance for you and hides the raw vector behind a narrower interface (push, pop, top, empty, size) so that you cannot accidentally call std::sort on it or index into the middle and break the heap invariant. This is precisely why the “you still need pop_back()” bug described in the pop_heap section cannot happen with priority_queue — the adapter’s pop() always performs both steps atomically from the caller’s point of view.

The trade-off is that priority_queue deliberately does not expose iterators over its elements or begin()/end(), because arbitrary read/write access would let you violate the heap property that the class exists to protect. If your use case needs to inspect, iterate, or selectively remove elements from the middle of the range — not just look at the top — you genuinely need the free heap algorithms (or an alternative structure like std::multiset/std::set with an ordering comparator), because priority_queue has intentionally sacrificed that flexibility for safety.

Basic Usage

#include <queue>
#include <iostream>
int main() {
    std::priority_queue<int> pq;
    
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);
    pq.push(5);
    
    std::cout << "Priority queue (max heap):\n";
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    std::cout << "\n";
}

Output:

Priority queue (max heap):
5 4 3 1 1

Min Priority Queue

std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(3);
min_pq.push(1);
min_pq.push(4);
min_pq.push(1);
min_pq.push(5);
std::cout << "Min priority queue:\n";
while (!min_pq.empty()) {
    std::cout << min_pq.top() << " ";
    min_pq.pop();
}
std::cout << "\n";

Output:

Min priority queue:
1 1 3 4 5

Custom Comparators

All of the heap algorithms — and priority_queue itself — accept a comparator with the same semantics as std::sort: a strict weak ordering, callable as comp(a, b) and returning true when a should be considered “lower priority” than b. The one rule that is easy to get wrong when the comparator involves multiple fields (as in the task-scheduler pattern below) is that it must be consistent and total — if comp(a, b) and comp(b, a) are both true for distinct elements, or the comparator is not transitive, the heap’s internal invariants silently break and you get corrupted, seemingly random ordering with no compiler warning. When comparing structs by several fields, always give every tie a well-defined fallback (as the Task example below does with priority first, then deadline), rather than leaving equal cases undefined.

Custom Struct

struct Task {
    std::string name;
    int priority;
    
    bool operator<(const Task& other) const {
        return priority < other.priority;  // Max heap by priority
    }
};
int main() {
    std::priority_queue<Task> pq;
    
    pq.push({"Task A", 3});
    pq.push({"Task B", 1});
    pq.push({"Task C", 5});
    pq.push({"Task D", 2});
    
    std::cout << "Tasks by priority:\n";
    while (!pq.empty()) {
        const auto& task = pq.top();
        std::cout << task.name << " (priority: " << task.priority << ")\n";
        pq.pop();
    }
}

Output:

Tasks by priority:
Task C (priority: 5)
Task A (priority: 3)
Task D (priority: 2)
Task B (priority: 1)

Lambda Comparator

auto cmp = [](const Task& a, const Task& b) {
    return a.priority < b.priority;  // Max heap
};
std::priority_queue<Task, std::vector<Task>, decltype(cmp)> pq(cmp);
pq.push({"Task A", 3});
pq.push({"Task B", 1});
pq.push({"Task C", 5});
while (!pq.empty()) {
    std::cout << pq.top().name << "\n";
    pq.pop();
}

Output:

Task C
Task A
Task B

Production Patterns

The three patterns below are the ones that show up most often in real backend code and coding interviews alike, and each one leans on a specific property of heaps that a plain sorted container would not give you as cheaply.

Pattern 1: Top K Elements

The “top K” pattern deliberately uses a min-heap of size K, which feels backwards at first — why would finding the largest elements use a min heap? The trick is that the heap only ever needs to answer one question cheaply: “is the current candidate bigger than the smallest element I am currently keeping?” A min-heap gives O(1) access to that smallest kept element via top(), and O(log k) to evict it and insert the new candidate. Because k is typically much smaller than n (the full dataset), this runs in O(n log k) rather than the O(n log n) a full sort would cost — a meaningful difference when n is in the millions and k is a small constant like 10 or 100.

std::vector<int> top_k(const std::vector<int>& data, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
    
    for (int x : data) {
        if (min_heap.size() < k) {
            min_heap.push(x);
        } else if (x > min_heap.top()) {
            min_heap.pop();
            min_heap.push(x);
        }
    }
    
    std::vector<int> result;
    while (!min_heap.empty()) {
        result.push_back(min_heap.top());
        min_heap.pop();
    }
    
    std::reverse(result.begin(), result.end());
    return result;
}
int main() {
    std::vector<int> data = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    auto top3 = top_k(data, 3);
    
    std::cout << "Top 3: ";
    for (int x : top3) {
        std::cout << x << " ";
    }
    std::cout << "\n";
}

Output:

Top 3: 9 6 5

Complexity: O(n log k)

Pattern 2: Merge K Sorted Arrays

Merging k already-sorted sequences is the classic use case where a heap beats the naive approach outright. Comparing the current head of all k arrays on every step with a linear scan costs O(k) per output element, or O(nk) total. Keeping those k heads in a min-heap instead reduces the per-element cost to O(log k), because finding and replacing the smallest head is a heap pop/push pair rather than a full scan — giving the O(n log k) bound noted below. This exact pattern is also how external merge sort works when data does not fit in memory, and how log-structured storage engines merge sorted SSTable segments during compaction.

struct Element {
    int value;
    int array_index;
    int element_index;
    
    bool operator>(const Element& other) const {
        return value > other.value;  // Min heap
    }
};
std::vector<int> merge_k_sorted(const std::vector<std::vector<int>>& arrays) {
    std::priority_queue<Element, std::vector<Element>, std::greater<Element>> min_heap;
    
    // Initialize heap with first element from each array
    for (int i = 0; i < arrays.size(); ++i) {
        if (!arrays[i].empty()) {
            min_heap.push({arrays[i][0], i, 0});
        }
    }
    
    std::vector<int> result;
    
    while (!min_heap.empty()) {
        auto elem = min_heap.top();
        min_heap.pop();
        
        result.push_back(elem.value);
        
        // Add next element from same array
        int next_index = elem.element_index + 1;
        if (next_index < arrays[elem.array_index].size()) {
            min_heap.push({
                arrays[elem.array_index][next_index],
                elem.array_index,
                next_index
            });
        }
    }
    
    return result;
}
int main() {
    std::vector<std::vector<int>> arrays = {
        {1, 4, 7},
        {2, 5, 8},
        {3, 6, 9}
    };
    
    auto merged = merge_k_sorted(arrays);
    
    std::cout << "Merged: ";
    for (int x : merged) {
        std::cout << x << " ";
    }
    std::cout << "\n";
}

Output:

Merged: 1 2 3 4 5 6 7 8 9

Complexity: O(n log k), where n = total elements, k = number of arrays.

Pattern 3: Task Scheduler

struct Task {
    std::string name;
    int priority;
    std::chrono::system_clock::time_point deadline;
    
    bool operator<(const Task& other) const {
        if (priority != other.priority) {
            return priority < other.priority;  // Higher priority first
        }
        return deadline > other.deadline;  // Earlier deadline first
    }
};
class TaskScheduler {
public:
    void add_task(const Task& task) {
        tasks_.push(task);
    }
    
    std::optional<Task> get_next_task() {
        if (tasks_.empty()) {
            return std::nullopt;
        }
        
        Task task = tasks_.top();
        tasks_.pop();
        return task;
    }
    
    std::size_t pending_count() const {
        return tasks_.size();
    }
private:
    std::priority_queue<Task> tasks_;
};
int main() {
    TaskScheduler scheduler;
    
    auto now = std::chrono::system_clock::now();
    
    scheduler.add_task({"Task A", 3, now + std::chrono::hours(2)});
    scheduler.add_task({"Task B", 5, now + std::chrono::hours(1)});
    scheduler.add_task({"Task C", 3, now + std::chrono::hours(1)});
    scheduler.add_task({"Task D", 1, now + std::chrono::hours(3)});
    
    std::cout << "Task execution order:\n";
    while (auto task = scheduler.get_next_task()) {
        std::cout << task->name << " (priority: " << task->priority << ")\n";
    }
}

Output:

Task execution order:
Task B (priority: 5)
Task C (priority: 3)
Task A (priority: 3)
Task D (priority: 1)

Key: Priority queue for task scheduling with priority and deadline.

Complete Example

#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
#include <chrono>
#include <random>
// Benchmark heap operations
void benchmark_heap() {
    std::vector<int> data(100000);
    std::mt19937 gen(42);
    std::uniform_int_distribution<> dis(1, 1000000);
    
    for (auto& x : data) {
        x = dis(gen);
    }
    
    // make_heap
    auto start = std::chrono::high_resolution_clock::now();
    std::make_heap(data.begin(), data.end());
    auto end = std::chrono::high_resolution_clock::now();
    auto make_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
    
    // push_heap
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 1000; ++i) {
        data.push_back(dis(gen));
        std::push_heap(data.begin(), data.end());
    }
    end = std::chrono::high_resolution_clock::now();
    auto push_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
    
    // pop_heap
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 1000; ++i) {
        std::pop_heap(data.begin(), data.end());
        data.pop_back();
    }
    end = std::chrono::high_resolution_clock::now();
    auto pop_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
    
    std::cout << "Heap Benchmark (100K elements):\n";
    std::cout << "make_heap: " << make_time << " μs\n";
    std::cout << "push_heap (1K ops): " << push_time << " μs\n";
    std::cout << "pop_heap (1K ops): " << pop_time << " μs\n";
}
int main() {
    // Demo: Basic heap operations
    std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};
    
    std::cout << "Original: ";
    for (int x : vec) std::cout << x << " ";
    std::cout << "\n\n";
    
    std::make_heap(vec.begin(), vec.end());
    std::cout << "After make_heap: ";
    for (int x : vec) std::cout << x << " ";
    std::cout << "\nMax: " << vec.front() << "\n\n";
    
    vec.push_back(10);
    std::push_heap(vec.begin(), vec.end());
    std::cout << "After push_heap(10): ";
    for (int x : vec) std::cout << x << " ";
    std::cout << "\nMax: " << vec.front() << "\n\n";
    
    std::pop_heap(vec.begin(), vec.end());
    int max = vec.back();
    vec.pop_back();
    std::cout << "After pop_heap: ";
    for (int x : vec) std::cout << x << " ";
    std::cout << "\nPopped: " << max << "\n\n";
    
    std::sort_heap(vec.begin(), vec.end());
    std::cout << "After sort_heap: ";
    for (int x : vec) std::cout << x << " ";
    std::cout << "\n\n";
    
    // Benchmark
    benchmark_heap();
}

Output:

Original: 3 1 4 1 5 9 2 6
After make_heap: 9 6 4 3 5 1 2 1
Max: 9
After push_heap(10): 10 9 4 6 5 1 2 1 3
Max: 10
After pop_heap: 9 6 4 3 5 1 2 1
Popped: 10
After sort_heap: 1 1 2 3 4 5 6 9
Heap Benchmark (100K elements):
make_heap: 1234 μs
push_heap (1K ops): 567 μs
pop_heap (1K ops): 543 μs

Troubleshooting: Common Heap Bugs

The heap algorithms have very few functions but a surprising number of ways to misuse them, because the precondition/postcondition contracts described above are enforced by nothing except your own discipline — most implementations skip runtime checks for these preconditions in release builds for performance, so a violated precondition usually manifests as silently wrong output rather than a crash or exception.

1. Forgetting pop_back() after pop_heap. Covered in depth above — this is by far the most common bug. Symptom: the container’s size() never shrinks, and later heap operations behave as if a “ghost” duplicate of the old maximum is still part of the heap.

2. Calling push_heap before push_back. push_heap assumes the new element is already sitting at *(last-1). If you call it on the unchanged range and only append afterward, you have sifted a stale (often out-of-heap-order) element and left the true new element unheapified.

3. Mismatched comparators across calls on the same range. If you build a heap with make_heap(v.begin(), v.end(), std::greater<int>()) but later call push_heap or pop_heap on the same vector with the default std::less, the heap property assumed by each call is different — the range silently stops being a valid heap under either ordering. Always pass the same comparator object (or an equivalent one) to every heap call on a given range.

4. Assuming heap order is sort order. As shown in the make_heap example, only front() is guaranteed to be the extremum; the rest of the array has no defined relative order. Do not iterate a heap-ordered vector expecting ascending or descending values — use sort_heap (destroys the heap) or std::sort if you need that.

5. Not verifying assumptions with is_heap during debugging. std::is_heap and std::is_heap_until are O(n) query functions that are easy to forget exist, but they are the fastest way to confirm a suspected heap-corruption bug rather than guessing:

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

std::vector<int> vec = {9, 6, 4, 3, 5, 1, 2, 1};

std::cout << std::boolalpha << std::is_heap(vec.begin(), vec.end()) << "\n"; // true

vec[0] = 0; // manually corrupt the heap property
std::cout << std::is_heap(vec.begin(), vec.end()) << "\n"; // false

auto it = std::is_heap_until(vec.begin(), vec.end());
std::cout << "Valid heap prefix length: " << (it - vec.begin()) << "\n";

is_heap_until is particularly useful in a debugger or a unit test assertion: it returns an iterator to the first position where the heap property breaks, so you can pinpoint exactly which element corrupted the structure instead of only knowing that something did.

Free Algorithms vs. `priority_queue`: Which to Reach For

As a rule of thumb: default to priority_queue for ordinary “give me the next highest/lowest priority item” use cases — task schedulers, Dijkstra’s algorithm, top-K/merge-K patterns — because its narrower interface makes it much harder to accidentally corrupt the heap, and the two-step pop_heap/pop_back dance is exactly the kind of easy-to-forget boilerplate a container adapter exists to eliminate. Reach for the free make_heap/push_heap/pop_heap functions directly only when you need something priority_queue cannot give you: iteration or random access into the middle of the range, the ability to heapify a subrange of a buffer you already manage, interoperability with other <algorithm> functions on the same storage, or reuse of one buffer for both an in-progress heap and, later, a fully sorted array via sort_heap.

Heap algorithms or priority_queue

Operation	Complexity	Purpose
make_heap	O(n)	Build heap from range
push_heap	O(log n)	Insert element
pop_heap	O(log n)	Remove max/min
sort_heap	O(n log n)	Sort heap (destroys heap)
is_heap	O(n)	Check if range is heap

Use std::priority_queue when all you need is push, top and pop: it cannot be used incorrectly because it hides the container. Use the raw algorithms on a std::vector when you also need the elements themselves, for example to iterate over all pending items, remove or reprioritize an arbitrary entry and then call make_heap again, reserve capacity, or hand the storage to other code.

With the raw algorithms, the bug to watch for is an inconsistent comparator. Every call on the same range (make_heap, push_heap, pop_heap, is_heap) must receive the same comparator; building with std::greater<> and popping with the default std::less does not fail to compile, it silently returns the wrong element. Also remember that push_heap expects the new element to already be at the back of the range, and pop_heap only moves the top to the back, so it still has to be removed with pop_back.

Frequently Asked Questions

When would I use this in production code?

Reach for priority_queue whenever you need “give me the next highest/lowest priority item” behavior — job schedulers, Dijkstra’s algorithm, top-K and merge-K-sorted-lists patterns are the most common cases. Reach for the free make_heap/push_heap/pop_heap functions directly only when priority_queue’s narrower interface gets in your way — see the “Free Algorithms vs. priority_queue” comparison above for the concrete trade-offs.

Where can I go deeper?

cppreference’s heap algorithm pages document the exact preconditions and complexity guarantees for every function referenced in this guide, including the edge cases around custom allocators and exception safety that are out of scope here.

C++ Algorithm Heap — a shorter, example-first walkthrough of the same core functions
C++ stack, queue and priority_queue: How the Adapters Work and the Mistakes They Invite — how priority_queue fits alongside stack and queue
C++
C++ Algorithm Problems & Coding Test Patterns

Key takeaways

Why Heap Algorithms Matter

Problem: Priority Queue Operations

Heap Fundamentals

Binary Heap Structure

Max Heap vs Min Heap

Complexity at a Glance

make_heap: Build Heap

Syntax

Example: Max Heap

Example: Min Heap

push_heap: Insert Element

Syntax

Usage

How push_heap Works

pop_heap: Remove Max

Syntax

Usage

How pop_heap Works

sort_heap: Heap Sort

Syntax

Usage

priority_queue: Container Adapter

What is priority_queue?

Basic Usage

Min Priority Queue

Custom Comparators

Custom Struct

Lambda Comparator

Production Patterns

Pattern 1: Top K Elements

Pattern 2: Merge K Sorted Arrays

Pattern 3: Task Scheduler

Complete Example

Troubleshooting: Common Heap Bugs

Free Algorithms vs. priority_queue: Which to Reach For

Heap algorithms or priority_queue

Frequently Asked Questions

When would I use this in production code?

Where can I go deeper?

Related Reading

Free Algorithms vs. `priority_queue`: Which to Reach For