Introduction to Heaps

A heap is a special kind of binary tree with one rule: the parent of every node is “smaller than” (or “larger than”) all of its children. That single rule — applied recursively all the way down — gives us instant access to the smallest (or largest) element in the entire structure.

The two flavors

There are exactly two kinds of binary heap:

• Min-heap — every parent is ≤ both of its children. The smallest element sits at the root.
• Max-heap — every parent is ≥ both of its children. The largest element sits at the root.

That’s the heap property, and it’s the only invariant we maintain.

The shape rule: a complete binary tree

A heap is always a complete binary tree — every level is fully filled except possibly the last, and the last level is filled from left to right. No gaps in the middle.

       1                      1                       1
      / \                    / \                     / \
     3   5                  3   5                   3   5
    / \                    / \  /                  / \   \
   7   9                  7   9 8                 7   9   6   ← gap! NOT valid
   ✓ complete            ✓ complete              ✗ not a heap shape

That shape rule is crucial. It’s what makes the array storage trick work.

The array trick

Here’s the part that makes heaps fast and beautiful. Even though a heap is conceptually a tree, we store it in a plain array — no pointers, no node objects.

For a node at index i:

That’s it. No allocations. No pointers to chase. Just integer arithmetic.

The tree and the array represent exactly the same data. Index 0 is the root. Indices 1–2 are the next level. Indices 3–6 are the level after that. Doubling capacity gives you another level.

What heaps are good at — and what they’re not

Heaps are an incredibly specialized structure. They’re not a replacement for arrays, lists, or BSTs. They have exactly one trick:

If your problem starts with the words “find the K largest” or “what’s the next event by time” or “give me the smallest unprocessed item”, a heap is almost certainly the right tool. If you need to look up arbitrary elements or maintain a fully sorted view, use something else (BST, sorted array, hash map).

When you’d reach for a heap

A few real applications, just to plant the pattern:

• Dijkstra’s shortest-path algorithm — always process the closest unvisited node next. Pop from a min-heap.
• A* pathfinding — same as Dijkstra, but the priority is g + h.
• Huffman coding — repeatedly merge the two least-frequent symbols. Pop, pop, push.
• Top-K problems — keep a heap of size K; everything bigger (or smaller) than the root gets in.
• Event-driven simulation — process events in chronological order. Push events as they’re scheduled; pop to handle.
• Scheduling and task queues — execute the highest-priority job next.
• Median maintenance — keep two heaps (max-heap below, min-heap above) and the median sits at one of the tops.

That list is most of competitive programming. Heaps earn their keep.

Try it

Push values, pop them, switch between min and max — watch how the tree rearranges to keep the heap property. Hit Shuffle to get a random array, then Heapify to see the O(n) build in action.

Quick check

Got the mental model? Next: how to actually implement the four core operations.