A tree that only promises one thing: the smallest item is at the top. That weaker guarantee is what makes insert and extract cost O(log n) — and it is the engine inside Dijkstra and A*.
Controls
Tree and Array Are the Same Thing
step 0
Backing array — no pointers needed
Insight
A heap is a complete binary tree where every parent beats its children. Siblings are unordered — that is the weakness which buys the speed.
Weaker ordering than a BST, and that is exactly the point.
Quick Context
A heap is a complete binary tree obeying one rule: every parent is smaller than both its children (a min-heap) or larger than both (a max-heap). It says nothing about siblings — the tree is only partially ordered.
Why Partial Ordering Is Better Here
A BST fully sorts its data, which costs effort to maintain. A heap only guarantees the extreme value sits at the root. If all you ever ask is "what is the smallest item?", full sorting is wasted work.
That weaker promise makes the structure cheap to maintain: O(1) to read the root, O(log n) to insert or remove it. Note that heaps are terrible at searching for an arbitrary value — that is O(n), because the ordering gives you no guidance below the root.
An Array Pretending to Be a Tree
Heaps need no pointers at all. Because the tree is complete — every level full except possibly the last, filled left to right — positions can be computed with arithmetic:
parent of i = (i - 1) / 2
left of i = 2i + 1
right of i = 2i + 2
Watch the tree and the array update together as you insert. They are the same structure drawn two ways. This makes heaps compact and cache-friendly — a real advantage over pointer-based trees.
Sift Up and Sift Down
Insert — place the new value at the end of the array (the only spot that keeps the tree complete), then sift up: repeatedly swap with the parent while it is out of order. At most one swap per level, so O(log n).
Extract root — take the root, move the last element into its place, then sift down: repeatedly swap with the smaller child until order is restored. Again O(log n).
The swap counter shows this: even with 15 elements, no operation needs more than about 4 swaps.
Priority Queues Everywhere
A priority queue serves the highest-priority item rather than the oldest, and a heap is how it is almost always implemented. That makes heaps quietly essential:
Dijkstra and A* repeatedly need "the unvisited node with the smallest distance" — exactly a min-heap extract. Both of your existing pathfinding apps depend on this.
Heap sort builds a heap and extracts repeatedly: O(n log n) with O(1) extra space.
Top-k problems — keep a size-k heap and you find the largest k items in O(n log k) without sorting everything.
Schedulers and event simulations — always process the next-earliest event.
Interactive Exploration Guide
Insert a value smaller than the root. Watch it bubble all the way to the top — one swap per level, never more.
Insert a large value. It stays near the bottom with no swaps at all — the average insert is far cheaper than the worst case.
Extract the root repeatedly. The last element jumps to the top and sinks back down. Values come out in sorted order — that is heap sort.
Compare the array with the tree as you go. Index 0 is the root; index i's children are at 2i+1 and 2i+2, always.
Switch to a max-heap. The same machinery runs with the comparison flipped — that is the only difference between the two.
Key Takeaway
A heap keeps only the extreme value ordered, and that weaker guarantee is what makes it fast: O(1) peek, O(log n) insert and extract, in a pointer-free array. Whenever an algorithm repeatedly asks for the smallest or largest remaining item, a heap is the answer.
Cheat sheet
Heaps and Priority Queues
A tree that only promises one thing: the smallest item is at the top. That weaker guarantee is what makes insert and extract cost O(log n) — and it is the engine inside Dijkstra and A*.