Intuition First: The Emergency Room#

A hospital ER doesn't treat patients first-come-first-served. It treats the most urgent one next, no matter when they arrived. Someone who walks in with a far worse injury jumps straight to the front. The moment the most critical patient is wheeled away, the next-most-critical automatically becomes the new front of the line.

A heap is exactly that triage line in data-structure form: it always keeps the highest-priority item ready at the very top, and it quietly re-settles itself in O(log n) every time someone new arrives or the top is taken. That's why heaps power priority queues, task schedulers, and "give me the top 5" problems: anywhere you constantly need the best-of-what's-left.

The Concept#

A binary heap is one of the neatest data-structure tricks in computer science: it achieves O(log n) insert and delete-min (or delete-max) by exploiting a single structural guarantee. The tree is always complete.

A complete binary tree fills its levels left to right, with no gaps. That property lets you store the entire tree in a plain array without any pointers. If a node lives at zero-based index i, its left child sits at 2i + 1, its right child at 2i + 2, and its parent at (i - 1) / 2 (integer division). No next pointers, no memory allocations per node, just index arithmetic on a flat array.

Layered on top of that layout is the heap invariant:

  • Min-heap: every parent is less than or equal to its children. The root is therefore always the global minimum.
  • Max-heap: every parent is greater than or equal to its children. The root is always the global maximum.

Note that a heap is not fully sorted. Siblings have no ordering relationship with each other, and the second-smallest element must be one of the root's two children in level 1. It can never be deeper, because the only element smaller than it is the root, and every non-root node is larger than its parent. The heap only promises that the root beats everyone, and it maintains that promise efficiently.

Core Operations#

push (insert): O(log n)#

Append the new value at the first open slot at the bottom of the tree (the next position in the array). Then sift up: repeatedly compare the new node with its parent and swap if the invariant is violated. Because the tree has height ⌊log₂ n⌋, at most log n swaps are needed.

pop (extract-min / extract-max): O(log n)#

Remove the root (the answer you want). Replace it with the last element in the array, shrink the array by one, then sift down: swap the displaced root with its smaller child (for a min-heap) until the invariant is restored. Again, at most log n swaps.

peek: O(1)#

Read heap[0]. The invariant guarantees it is always the min (or max). No work required.

build_heap from an unsorted array: O(n)#

This one surprises people. Starting from the last internal node (index n//2 - 1) and working backwards to the root, call sift-down on each node. The total cost is O(n), not O(n log n), because most nodes are near the leaves and travel only a short distance. Python's heapq.heapify uses exactly this bottom-up approach.

Code Implementation#

Complexity Analysis#

OperationTimeWhy
pushO(log n)sift-up travels at most tree height
popO(log n)sift-down travels at most tree height
peekO(1)invariant guarantees root is min/max
build_heapO(n)bottom-up; most nodes sift down very little
SpaceO(n)one array slot per element

Interactive Lab#

Let's take the example of the min-heap [2, 5, 4, 9, 7, 6, 8]. Read the array strip and the tree together. They are the same seven values, and 2i+1 / 2i+2 is the only thing linking them. Press Play to run extract-min: 2 leaves the root, the last element 8 is moved up to take its place, and then sift-down repairs the damage: 8 loses to 4 and swaps, then loses to 6 and swaps again, settling at the bottom. The heap ends as [4, 5, 6, 9, 7, 8], still heap-ordered, after two swaps.

The max-heap [20, 15, 18, 10, 12, 14, 9] is the identical machinery with the comparison flipped. Extract-max lifts 20 out, promotes the last element 9 to the root, and sift-down swaps it past 18 and then 14, leaving [18, 15, 14, 10, 12, 9]. Same shape of run, opposite direction.

Heapify takes the unsorted array [5, 3, 8, 1, 9, 2, 7] and works backwards from the last internal node, sifting each one down. Count the swaps per node as it runs: the leaf-adjacent nodes barely move, and only the ones near the root travel any real distance. That lopsidedness is the whole reason the total is O(n) rather than O(n log n).

Heap sort on [5, 2, 8, 1, 9, 3, 10, 4, 6, 7] puts both halves together: build a max-heap in place, then repeatedly swap the root to the end of the array and sift down over the shrinking prefix. Watch the sorted region grow from the right while the heap ahead of it shrinks. No memory is used beyond the array itself.

What to Remember#

  • Array layout, no pointers. The complete-tree structure maps directly to an array via index arithmetic (2i+1, 2i+2, (i-1)//2). This makes heaps cache-friendly and avoids allocation overhead.
  • Heap-ordered, not fully sorted. Siblings are unordered. The only guarantee is parent vs. children. Think of it as a "partially sorted" structure optimised for one thing: fast access to the extreme value.
  • O(1) peek, O(log n) push/pop, O(n) build. These bounds are tight. If you need the minimum (or maximum) repeatedly while also inserting new elements, a heap beats sorting the whole collection every time.
  • Foundation for important algorithms. Heap sort runs in O(n log n) with O(1) extra space by building a max-heap in place. Dijkstra's shortest-path algorithm relies on a min-heap priority queue to always expand the nearest unvisited node next. Any "K largest / K smallest" query in a stream of data uses a heap of size K.
  • Priority queues are heaps. Python's heapq, Java's PriorityQueue, and C++'s priority_queue are all backed by a binary heap. Understanding the heap invariant lets you reason about the performance guarantees those standard library types give you.