Min Heap and Max Heap in C++

A heap is a complete binary tree where every parent compares a fixed way against its children: smaller in a min heap, larger in a max heap. That single rule puts the smallest or largest element at the root, so you read it in O(1) and pull it out in O(log n). C++ ships heaps two ways: std::priority_queue for a ready-made container, and the std::make_heap / std::push_heap / std::pop_heap family in <algorithm> for a heap laid over your own vector.

This guide covers both. You get the array math that makes a tree fit inside a flat vector, the heapify operation that keeps the order intact, working min-heap and max-heap code that compiles, heap sort, and a comparator example for custom types. If a graded assignment is the reason you landed here, our C++ assignment help service pairs you with a developer who works in the STL daily, and you pay the second half only after the code runs on your machine.

What is a heap and the heap property

A heap is a complete binary tree that obeys one ordering rule between each parent and its children. Complete means every level is full except possibly the last, and the last level fills left to right with no gaps. That shape is what lets the whole structure live in a contiguous array instead of nodes joined by pointers.

The ordering rule is the heap property, and it comes in two forms:

• Min-heap property: every parent is less than or equal to both of its children. The minimum sits at the root.
• Max-heap property: every parent is greater than or equal to both of its children. The maximum sits at the root.

The property is local, not global. It constrains each parent against its direct children only, so a min heap is not a sorted array. The root holds the minimum, but a node deep on the left can be larger than a node high on the right. That weaker promise is exactly why a heap inserts in O(log n) instead of the O(n) a fully sorted array pays.

How an array stores a binary tree

A heap needs no node objects and no child pointers because index arithmetic encodes the tree. Store the root at index 0, then for any node at index i:

| Relationship | Formula (0-based) | | --- | --- | | Left child | 2 * i + 1 | | Right child | 2 * i + 2 | | Parent | (i - 1) / 2 |

Walk it on the vector [1, 2, 7, 9, 4]. The root 1 sits at index 0. Its children live at indices 1 and 2, the values 2 and 7, both larger than 1. The node 2 at index 1 has children at indices 3 and 4, the values 9 and 4, again both larger. Every parent beats its children, so the min-heap property holds. Reading down the array is not sorted order, but the root is always the smallest, which is the only guarantee a min heap makes.

This layout is why heaps are cache-friendly. The elements sit next to each other in memory, so a sift travels a single root-to-leaf path with good locality, unlike a pointer-based tree that scatters nodes across the heap allocator.

Heapify: keeping the property after every change

Heapify is the repair step that moves one element along a single path until the heap property holds again. Two directions cover every case.

Sift-up runs after an insertion. A new element goes into the next open array slot, then you compare it with its parent. In a min heap, if the child is smaller, the two swap, and the value keeps rising until its parent is smaller or it reaches the root. A max heap swaps when the child is larger.

Sift-down runs after the root is removed. You move the last element into the root slot, then compare it with its children and swap with the smaller child in a min heap (the larger child in a max heap). The value sinks until both children obey the property or it lands on a leaf.

Each pass touches at most the height of the tree, which is log n for n elements, so a single insert or extract costs O(log n). Building a heap all at once with std::make_heap is cheaper than it looks: sift-down from the last internal node up to the root runs in O(n), not O(n log n), because most nodes sit near the leaves and travel a short distance.

Min heap and max heap in C++ with std::priority_queue

The fastest way to get a heap in C++ is std::priority_queue from <queue>. It wraps a heap over a std::vector and exposes push, pop, and top. The default is a max heap, so top() returns the largest element.

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

int main() {
    // Default priority_queue is a MAX heap: top() is the largest.
    std::priority_queue<int> maxHeap;

    for (int value : {9, 4, 7, 2, 1}) {
        maxHeap.push(value);          // O(log n) each, sift-up
    }

    std::cout << "Max heap top: " << maxHeap.top() << "\n";  // 9

    maxHeap.pop();                    // remove 9, sift-down
    std::cout << "After pop, top: " << maxHeap.top() << "\n"; // 7
    return 0;
}

For a min heap, switch the comparator to std::greater<int>. That reverses the ordering, so top() returns the smallest element. The template needs all three type arguments because the comparator is the third one.

#include <functional>   // std::greater
#include <iostream>
#include <queue>
#include <vector>

int main() {
    // MIN heap: pass std::greater so top() is the smallest.
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    for (int value : {9, 4, 7, 2, 1}) {
        minHeap.push(value);
    }

    std::cout << "Min heap top: " << minHeap.top() << "\n";   // 1

    minHeap.pop();                    // remove 1
    std::cout << "After pop, top: " << minHeap.top() << "\n"; // 2
    return 0;
}

Three operations carry almost every heap task: top() peeks at the root in O(1), push() inserts in O(log n), and pop() removes the root in O(log n). priority_queue has no iterator and no way to inspect elements below the root, which is the trade for its speed. When you need to walk the underlying storage, drop to the algorithm-level API in the next section.

Heaps directly over a vector with the STL heap algorithms

When you want the heap to live in a vector you control, <algorithm> gives you std::make_heap, std::push_heap, std::pop_heap, and std::sort_heap. These operate in place on any random-access range, so you keep full access to the data while the heap property holds.

std::make_heap rearranges an existing range into a max heap in O(n). After that, push_heap and pop_heap maintain it. The pattern has a sharp edge worth memorizing: pop_heap does not remove anything. It swaps the root to the back of the range and re-heapifies the front, leaving the old root sitting at back() for you to read and then drop with pop_back().

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

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

    std::make_heap(v.begin(), v.end());        // max heap, O(n)
    std::cout << "Max: " << v.front() << "\n"; // 9

    v.push_back(11);                           // add to the back
    std::push_heap(v.begin(), v.end());        // sift the new value up
    std::cout << "Max: " << v.front() << "\n"; // 11

    std::pop_heap(v.begin(), v.end());         // move max to v.back()
    v.pop_back();                              // now actually remove it
    std::cout << "Max: " << v.front() << "\n"; // 9
    return 0;
}

For a min heap over a vector, pass std::greater<int>{} as the extra comparator argument to every call. The comparator must match across make_heap, push_heap, and pop_heap, or the operations corrupt the structure silently.

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

int main() {
    std::vector<int> v{9, 4, 7, 2, 1};
    auto cmp = std::greater<int>{};            // min heap comparator

    std::make_heap(v.begin(), v.end(), cmp);
    std::cout << "Min: " << v.front() << "\n"; // 1

    v.push_back(0);
    std::push_heap(v.begin(), v.end(), cmp);
    std::cout << "Min: " << v.front() << "\n"; // 0

    std::pop_heap(v.begin(), v.end(), cmp);    // move min to back
    v.pop_back();
    std::cout << "Min: " << v.front() << "\n"; // 1
    return 0;
}

The earlier WordPress version of this post shipped empty #include lines and called std::greater() without a type. Both fail to compile. The headers above are the real ones each example needs, and std::greater<int> carries the template argument the comparator requires.

Heap sort: the heap as a sorting engine

Heap sort builds a max heap from the input, then repeatedly extracts the root to produce ascending order, all in place. The STL pair make_heap + sort_heap does it in two lines, and the result is O(n log n) with no extra array.

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

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

    std::make_heap(data.begin(), data.end());  // O(n)
    std::sort_heap(data.begin(), data.end());  // O(n log n), ascending

    for (int x : data) std::cout << x << ' ';  // 1 2 3 4 7 9 11
    std::cout << '\n';
    return 0;
}

sort_heap works by calling pop_heap n times. Each pop sends the current maximum to the back of the shrinking heap range, so the sorted tail grows from the right while the heap shrinks from the left. Heap sort guarantees O(n log n) in the worst case, unlike quicksort, and sorts in place, unlike merge sort. It is not stable, so equal keys can swap order. For a wider comparison of when each method wins, see our walkthrough of sorting algorithms in Java and their implementation; the complexity tradeoffs carry straight over to C++.

Heaps with custom types and comparators

A heap is not limited to int. Supply a comparator and it orders any type. The comparator is a callable that returns true when its first argument has lower priority than its second, which for priority_queue means it sits deeper in the heap.

This Task example orders jobs so the nearest deadline surfaces first, a min heap on the deadline field built with a lambda comparator.

#include <iostream>
#include <queue>
#include <string>
#include <vector>

struct Task {
    std::string name;
    int deadline;   // smaller = more urgent
};

int main() {
    // Lambda returns true when 'a' has LOWER priority than 'b'.
    // Larger deadline = lower priority -> the earliest deadline ends up on top.
    auto later = [](const Task& a, const Task& b) {
        return a.deadline > b.deadline;
    };

    std::priority_queue<Task, std::vector<Task>, decltype(later)> queue(later);

    queue.push({"submit lab", 5});
    queue.push({"fix segfault", 2});
    queue.push({"write tests", 9});

    while (!queue.empty()) {
        const Task& t = queue.top();
        std::cout << t.deadline << ": " << t.name << "\n";
        queue.pop();
    }
    // 2: fix segfault
    // 5: submit lab
    // 9: write tests
    return 0;
}

Flip the comparison to a.deadline < b.deadline and the same code becomes a max heap that serves the latest deadline first. The comparator is the only thing that changes between a min heap and a max heap on a custom type, which is the cleanest way to think about the whole min-versus-max distinction.

Min heap vs max heap: when to reach for each

The choice is driven by which extreme you keep asking for. A min heap when you repeatedly need the smallest item, a max heap when you repeatedly need the largest.

| Aspect | Min heap | Max heap | | --- | --- | --- | | Root holds | Smallest element | Largest element | | priority_queue setup | std::greater<int> comparator | Default (std::less<int>) | | top() returns | Minimum, O(1) | Maximum, O(1) | | Typical use | Dijkstra, Prim, k smallest, event scheduling | k largest, median tracking, bandwidth allocation | | Sorting direction | Descending via repeated extract | Ascending via repeated extract |

Min heaps drive Dijkstra's shortest-path and Prim's minimum-spanning-tree algorithms, where you always expand the cheapest frontier edge next. Max heaps power "top k" queries, load balancers that hand work to the busiest or least busy server, and the running-median trick that pairs a max heap with a min heap. Both share the same array, the same heapify, and the same O(log n) cost; only the comparator differs.

If you are comparing heaps against other tree structures for a course, a binary search tree in Java gives sorted traversal and range queries that a heap cannot, while a heap wins on repeated min or max extraction. And since both STL heap APIs sit on top of a vector, a solid grasp of vectors in C++ makes the underlying storage far less mysterious.

Common heap mistakes in C++ assignments

Five errors account for most heap submissions that fail an autograder:

1. Forgetting pop_heap then pop_back. std::pop_heap only moves the root to the back. Skip pop_back() and the element stays in the container, so the size never shrinks and the next front() lies.
2. Mismatched comparators across calls. make_heap with std::greater followed by push_heap without it scrambles the heap. The comparator must be identical on every call against the same range.
3. Dropping the template arguments on a min heap. std::priority_queue<int, std::greater<int>> does not compile, because the second template parameter is the container, not the comparator. The comparator is the third argument, so the container std::vector<int> has to appear in between.
4. Calling top() on an empty heap. Reading the root of an empty priority_queue is undefined behavior. Guard every top() and pop() with an empty() check inside the loop.
5. Expecting sorted iteration. A heap is not sorted. Iterating the backing vector returns heap order, not ascending order. Use sort_heap or repeated pop when you actually need a sorted sequence.

A clean submission also matches the exact output format the grader expects, including spacing and newlines, which is where logically correct heap code still loses points. If a deadline is closing in, our C++ assignment help team builds the heap, matches the autograder format, and walks you through the code so you can defend it. Pricing starts at $29, you pay 50% to begin and 50% after the code runs, and every brief is covered by an NDA.

Frequently asked questions

What is the difference between a min heap and a max heap in C++?

A min heap keeps the smallest element at the root, so every parent holds a value less than or equal to its children. A max heap keeps the largest element at the root, so every parent holds a value greater than or equal to its children. In C++, std::priority_queue defaults to a max heap; pass std::greater to turn it into a min heap.

Is std::priority_queue a min heap or a max heap by default?

By default std::priority_queue is a max heap, so top() returns the largest element. To build a min heap, declare it as std::priority_queue<int, std::vector<int>, std::greater<int>>, which makes top() return the smallest element.

What is the time complexity of heap operations?

Reading the root with top() is O(1). Insertion with push() and removal with pop() are both O(log n) because the element travels at most the height of the tree. Building a heap from an existing array with std::make_heap is O(n), faster than n separate insertions.

How do I convert a min heap into a max heap?

Negate every value, push the negatives into a min heap, then negate again on the way out, which flips the ordering. The cleaner option is to switch the comparator: drop std::greater so std::priority_queue uses its default std::less, which gives a max heap directly.

When should I use a heap instead of a sorted array?

Use a heap when you repeatedly need the smallest or largest element while the data keeps changing. A heap gives O(log n) insert and O(log n) extract with O(1) peek. A sorted array gives O(1) peek but O(n) insert, so it loses on workloads with frequent updates such as Dijkstra's algorithm or a task scheduler.

Can a heap store custom objects, not just integers?

Yes. Supply a comparator that defines the ordering. For a struct, pass a lambda or a struct with operator() to std::priority_queue, or overload operator< on the type. The comparator decides which field drives priority, so a Task ordered by deadline and a Task ordered by cost use the same heap with different comparators.

What is heapify and why does it matter?

Heapify restores the heap property after an insert or a removal by moving one element along a root-to-leaf path. Sift-up runs after push and bubbles a new value toward the root; sift-down runs after pop and pushes the displaced root toward the leaves. Each pass touches at most log n nodes, which is what keeps push and pop logarithmic.