Binary Heap: O(n) Heapify, Heapsort, PriorityQueue

Revised November 2026. This tutorial first appeared in Korean in 2021. We rebuilt its C++ min-heap with Apple clang 21, using -Wall -Wextra and -fsanitize=address,undefined -g. It produced one warning (-Wnull-conversion) and the same output as in 2021. We also ran 400,000 random insert/extract operations against std::priority_queue, and every result matched, so the heap logic itself was correct. Two real defects remained: copying a heap object caused a double free (caught by AddressSanitizer), and the extract function did not return the value it removed. Both are fixed below. We also filled in what the 2021 article left as homework, heapsort and O(n) heap construction, with measurements.

This article is for readers who use priority queues and want to know what happens inside them, and for anyone who has wondered whether "just push everything one by one" is a fine way to build a heap. The answers: a binary heap is a complete binary tree stored in a flat array. Insert is one sift-up and extract-min is one sift-down, both O(log n). If you already have all the data, building the heap in one pass (heapify) was never worse in our tests and needed more than ten times fewer comparisons on unlucky input. In production code you will mostly use C#'s PriorityQueue<TElement, TPriority> or C++'s std::priority_queue. They default to opposite orderings, and the C# one is not stable.

What a heap is: a shape rule and an order rule

A binary heap is a binary tree that obeys two rules at once:

1. Shape: it is a complete binary tree. Every level is full except possibly the last, which fills from the left.
2. Order: in a min-heap every parent is less than or equal to its children; in a max-heap, greater than or equal.

The 2021 text said a parent is "always smaller" than its children. Since duplicate values are allowed, "less than or equal" is the correct rule. (It also spelled the term "Heep" in places; fixed.)

In this min-heap the root, 1, is the global minimum. The order rule applies only between parent and child. Siblings and cousins are unordered: 51 on the left branch is larger than 21 on the right, and that is fine. This is the key difference from a binary search tree. A heap can hand you the smallest element quickly, but it cannot find an arbitrary value faster than a linear scan.

The array layout

A complete tree has no holes, so storing it level by level in an array wastes nothing and needs no pointers:

For index i, the parent is (i - 1) / 2, the left child 2i + 1 and the right child 2i + 2. Nodes at depth d occupy indexes 2^d − 1 through 2^(d+1) − 2; the 2021 article had that formula right.

Insert (sift-up) and extract-min (sift-down)

Insert appends the new value at the end of the array (the next free slot in the tree) and swaps it with its parent while it is smaller. Inserting 15 into the heap above places it as the right child of 51, swaps it with 51, then stops because its new parent, 2, is smaller.

Extract-min removes the root, moves the last element into the root slot, and swaps it downward with the smaller of its two children until neither child is smaller. Removing 1 from the original heap moves 68 to the top:

68 swaps with 2 (the smaller of 2 and 5), then with 10 (the smaller of 10 and 51), and stops because both 90 and 95 are larger.

Each operation walks one root-to-leaf path, so both are O(log n). The 2021 code implemented this as Insert and extractMin on a raw int*. Here is the same algorithm on top of std::vector:

#include <cstdio>
#include <utility>
#include <vector>

class MinHeap {
public:
    void push(int v) { a.push_back(v); sift_up(a.size() - 1); }
    bool empty() const { return a.empty(); }
    int top() const { return a[0]; }
    int pop() {                                 // returns the minimum (2021: void extractMin)
        int min = a[0];
        a[0] = a.back();
        a.pop_back();
        if (!a.empty()) sift_down(0, a.size());
        return min;
    }
    void print() const { for (int x : a) std::printf("%d ", x); std::printf("\n"); }
private:
    std::vector<int> a;
    void sift_up(size_t i) {
        while (i > 0 && a[i] < a[(i - 1) / 2]) {
            std::swap(a[i], a[(i - 1) / 2]);
            i = (i - 1) / 2;
        }
    }
    void sift_down(size_t i, size_t n) {
        for (;;) {
            size_t l = 2 * i + 1, r = l + 1, m = i;
            if (l < n && a[l] < a[m]) m = l;
            if (r < n && a[r] < a[m]) m = r;
            if (m == i) return;
            std::swap(a[i], a[m]);
            i = m;
        }
    }
};

int main() {
    MinHeap h;
    for (int x : {1, 7, 10, 9, 5, 6}) h.push(x);
    h.print();
    for (int k = 0; k < 3; ++k) { int m = h.pop(); std::printf("pop %d -> ", m); h.print(); }
}

1 5 6 9 7 10
pop 1 -> 5 7 6 9 10
pop 5 -> 6 7 10 9
pop 6 -> 7 9 10

Every line matches the array states the 2021 program printed for the same input (1 7 10 9 5 6).

What the compiler and sanitizers found in the 2021 code

One warning. The line that "cleared" the root before overwriting it:

data-structure-heap-0.cpp:55:15: warning: implicit conversion of NULL constant to 'int' [-Wnull-conversion]
   55 |     heap[0] = NULL;
      |             ~ ^~~~
      |               0

NULL is a null-pointer constant, not an integer value, and the next statement overwrites the slot anyway. Deleting the line changes nothing.

Double free on copy. The 2021 Heap class allocated with new int[] in its constructor and freed with delete[] in its destructor, but did not define a copy constructor or copy assignment (the rule of three). The sample main never copied a heap, so the bug stayed hidden. Adding one line, Heap b = a;, was enough for ASan:

==64767==ERROR: AddressSanitizer: attempting double-free on 0x603000001c30 in thread T0:
    #0 0x000100e9c644 in _ZdaPv+0x74 (libclang_rt.asan_osx_dynamic.dylib:arm64e+0x50644)
    #1 0x000100518c10 in Heap::~Heap() old_heap.inc:25

Letting std::vector own the memory, as MinHeap does, makes copy, move and destruction correct with no extra code.

An extract that returns nothing. extractMin() was declared void, so the caller had no way to get the minimum it removed, which is the whole point of a priority queue. pop() now returns it.

On leaks: AddressSanitizer on macOS does not include LeakSanitizer (detect_leaks is not supported on this platform), so we checked with leaks --atExit instead. Both the 2021 program and the new one reported 0 leaks.

Building a heap in O(n): measured

When all the elements are available up front, there are two ways to build a heap:

• n inserts: push them one at a time. In the worst case each element bubbles to the root, so O(n log n).
• Floyd's bottom-up heapify: leave the array as it is and call sift_down on every parent from index n/2 − 1 down to 0. Most nodes sit near the bottom and barely move, so the total is O(n).

static void build_floyd(std::vector<int>& v) {      // O(n): sift down from the last parent
    for (size_t i = v.size() / 2; i-- > 0;) sift_down(v, i, v.size());
}

We counted comparisons and timed both on 10 million ints (Apple clang 21, -O2, Apple M1 Pro, best of 5 runs). Our own functions include a comparison counter, which costs some time; std::make_heap has none.

One result surprised us: with random input, n inserts needed only about 2.3 comparisons per element. A random value usually finds its place a level or two above the bottom, so the O(n log n) bound is a worst-case statement. The worst case is easy to trigger, though. Feeding descending data into a min-heap sends every new value all the way to the root, and comparisons jumped 10.7×. Floyd's method stayed at about 2n whatever the input order. The time gap (2.7×) is smaller than the comparison gap, probably because the top levels that every sift-up passes through stay in cache; we did not measure that. The practical rule: if you have the data, build in one pass. It is never worse, and real data is often already sorted or nearly so. The C# PriorityQueue constructor that takes a collection of items and the C++ std::priority_queue constructor that takes an iterator range both build this way.

Heapsort, and how it compares

Once you have a heap, repeatedly swap the root with the last element of the unsorted range, shrink the range by one and sift down. The array ends up sorted in place with no extra memory: descending for a min-heap, ascending for a max-heap.

static void heapsort_desc(std::vector<int>& v) {    // min-heap -> descending order in place
    build_floyd(v);
    for (size_t end = v.size(); end > 1; --end) { std::swap(v[0], v[end - 1]); sift_down(v, 0, end - 1); }
}

Sorting 10 million random ints, same machine, best of 5:

Heapsort guarantees O(n log n) in the worst case and needs no extra memory, but it jumps between distant parts of the array on every step, which is hard on the cache. Even the library version was almost 7× slower than std::sort. In libc++ and libstdc++, std::sort is an introsort that switches to heapsort only when quicksort recursion gets too deep, as a safety net. For the other sorting algorithms, see our sorting comparison. Heaps earn their keep not as a general sort but for "give me the smallest of a stream that keeps changing" and "keep only the top k".

Heaps you actually use: PriorityQueue and std::priority_queue

C++ std::priority_queue is a max-heap by default. Swap in std::greater for a min-heap:

std::vector<int> in{1, 7, 10, 9, 5, 6};
std::priority_queue<int> maxq(in.begin(), in.end());            // max-heap by default, built in O(n)
std::priority_queue<int, std::vector<int>, std::greater<int>> minq(in.begin(), in.end());

max: 10 9 7 6 5 1
min: 1 5 6 7 9 10

C# PriorityQueue<TElement, TPriority> arrived in .NET 6, and Microsoft Learn describes it as an array-backed quaternary min-heap. It stores the element and its priority separately, and it is not stable: elements with equal priority do not come out in insertion order. We checked on .NET 10.0.14:

var pq = new PriorityQueue<string, int>();
string[] jobs = ["a", "b", "c", "d", "e", "f", "g", "h"];
foreach (var j in jobs) pq.Enqueue(j, 1);           // all the same priority
pq.Enqueue("urgent", 0);
while (pq.TryDequeue(out var job, out var pri)) Console.Write($"{job}({pri}) ");

// make it FIFO among equal priorities: add an insertion counter
var fifo = new PriorityQueue<string, (int Priority, long Seq)>();
long seq = 0;
foreach (var j in jobs) fifo.Enqueue(j, (1, seq++));
fifo.Enqueue("urgent", (0, seq++));

same priority, unstable: urgent(0) b(1) h(1) g(1) f(1) e(1) d(1) c(1) a(1)
with sequence number:    urgent a b c d e f g h

We enqueued a through h and got b, h, g, f, …, a. For a job queue where "same priority, first come first served" matters, use a (priority, sequence) tuple as the priority. Tuples compare item by item, so equal priorities fall back to the sequence number.

A few other members worth knowing, all verified on .NET 10:

• Max-heap: new PriorityQueue<int, int>(Comparer<int>.Create((x, y) => y.CompareTo(x))) dequeued 10 9 7 6 5 1.
• Top k: keep a min-heap of size k and call EnqueueDequeue(x, x), which does push-then-pop-min in a single sift. For 42, 7, 99, 13, 58, 3, 77, 21 the top three were 58, 77, 99.
• Bulk build: new PriorityQueue<int, int>([(5, 5), (1, 1), (3, 3)]); Peek() returned 1.
• Removing an arbitrary element: Remove(3, out _, out _) returned True. It has to search linearly, so it is O(n).
• UnorderedItems is exactly what it says: heap-array order, not sorted.

Summary

• A binary heap is a complete binary tree with parent ≤ child (min-heap), stored in an array with parent (i-1)/2 and children 2i+1, 2i+2.
• The 2021 heap logic passed 400,000 randomized checks. We fixed a NULL-to-int warning, a double free on copy and an extract that did not return its value.
• With all the data in hand, heapify in O(n) instead of n inserts: on 10 million descending ints, comparisons dropped from 213 million to 20 million.
• Heapsort is O(n log n) in the worst case but ran nearly 7× slower than std::sort in practice.
• C# PriorityQueue is a min-heap and not stable; C++ std::priority_queue is a max-heap by default.

Tree vocabulary and traversals are covered in trees. When you need sorted order and lookups of arbitrary keys, use a binary search tree instead.