Heaps

A heap is a complete binary tree that keeps exactly one promise, the heap property: every parent outranks its children — smaller in a min-heap, larger in a max-heap. That single rule pins the extremum to the root, so peek costs O(1) while insert and extract_top cost O(log n), and the whole tree lives inside a plain array.

Think of it as a corporate org chart with one hiring rule: nobody may outrank their boss. The CEO at the root is guaranteed to be the top of the company, but walk along any row of peers and you'll find them in no particular order — the chart only ranks vertically. Everything a heap does is maintain that one rule with the least possible paperwork.

How a Heap Works

The tree is implicit. The node at array index i keeps its children at 2i + 1 and 2i + 2, and its parent at (i − 1) // 2. No node objects, no pointers — completeness (every level full except possibly the last, filled left to right) guarantees the array has no holes, so index arithmetic alone reconstructs the hierarchy. The array IS the tree.

Three operations, all org-chart moves:

peek reads data[0] and touches nothing. The root is the answer by construction.

insert appends the new value at the end of the array — the next free slot in the bottom row — then sifts up: while the newcomer beats its parent (smaller, in a min-heap), the two swap and the newcomer climbs one level. The loop ends two ways: the newcomer reaches index 0 (it's the new CEO), or it meets a parent it doesn't beat and breaks.

extract_top is the interesting one. You can't just delete the root — that tears a hole in the top of a structure that must stay complete. So the implementation reads the root (that's the return value), pops the last element off the array (the one node a complete tree can lose for free), drops it into slot 0, and sifts down: at each level, find the better of the two children — the smaller, in a min-heap — and if that child beats the current node, swap and descend into that subtree. Stop when neither child wins, or when there are no children left. It's the intern suddenly seated in the CEO chair, demoted one floor at a time until the rule holds again.

A direction note that bites people: sift-down compares against the best child only. Both children are checked first — left, then right, and on a tie the left keeps the job, since the right only wins a strict comparison — before any swap happens.

The visualization runs the same code as a min-heap or a max-heap — the only difference is the comparator, < versus > — and shows the structure twice at once: tree above, array below, both moved by the same swaps, so index arithmetic and tree shape stay visibly in lockstep.

Heaps Step by Step

The default heap is an empty min-heap with the capacity slider at 10. Build one yourself: type each value and click Insert, in the order 5, 3, 8, 1, 9, 2, then click Extract top.

insert(5) lands at index 0. The sift-up loop never runs — i > 0 is already false — so the heap is [5] and the root settles immediately.

insert(3) is appended at index 1, then compared with its parent at index 0: 3 < 5 violates the heap property, so they swap — arr[1] ↔ arr[0]. Heap: [3, 5].

insert(8) is appended at index 2, whose parent is index 0. The compare reads 8 ≥ 3 — the rule already holds — so the loop breaks with no swap. Heap: [3, 5, 8].

insert(1) is the full climb. Appended at index 3, parent at index 1: 1 < 5, swap arr[3] ↔ arr[1], giving [3, 1, 8, 5]. Now at index 1, parent at index 0: 1 < 3, swap arr[1] ↔ arr[0], giving [1, 3, 8, 5]. The newcomer reached index 0 — new CEO — and the loop exits. Two comparisons, two promotions.

insert(9) and insert(2) repeat the pattern. 9 lands at index 4, loses its one compare against parent 3, and settles: [1, 3, 8, 5, 9]. 2 lands at index 5, beats parent 8 (swap arr[5] ↔ arr[2]), then loses to root 1 and settles at index 2: [1, 3, 2, 5, 9, 8]. As a tree: root 1, children 3 and 2; under 3 sit 5 and 9; under 2 sits 8 alone.

extract_top() now returns 1. The root lifts out, and the last element — 8 at index 5 — moves into slot 0, shrinking the array to [8, 3, 2, 5, 9]. Sift-down at index 0: children are 3 (left) and 2 (right), the smaller is 2, and 2 < 8, so swap arr[0] ↔ arr[2] — [2, 3, 8, 5, 9]. Descend to index 2: its left child would sit at index 5, past the end, so 8 is a leaf and the sift settles. The new top is 2, exactly the second-smallest value, found for free.

In the animation the tree view leads and the array row mirrors it underneath. Each compare beat draws a dashed arc between the two contestants, labeled with the actual comparison; on a sift-down the chosen child gets its own color before any motion happens. Swapping nodes glide past each other in both views at once, the inserted node flashes green when it settles, and an extracted root ghost-lifts off the top.

Time and Space Complexity

The logarithm is the tree's height: a complete binary tree with n nodes is ⌈log₂(n+1)⌉ levels tall, and a sift moves one level per swap, so the time complexity of both mutating operations is bounded by the height — about 20 levels for a million elements. Space is the bare array, zero pointer overhead. Bonus fact: building a heap from n existing items by sifting down from the last internal node runs in O(n), not O(n log n), because most nodes sit near the bottom with almost nothing below them.

Edge Cases

• Empty heap. peek returns None; extract_top raises an underflow. The buttons stay enabled on an empty heap precisely so you can watch the error path execute.
• Single element. extract_top pops the only entry and the if self.data: guard fails afterward — the move-last-to-root body and the sift-down never run. The code highlight shows the guard alone.
• Duplicates and ties. Heaps allow equal values; the property is ≤, not <. In this implementation a tied right child never displaces the left, so equal siblings leave the left as the swap target.
• The capacity slider (4–15, default 10) is a visualization limit, not a heap property. Real heaps grow without bound; the cap only keeps the tree legible on the canvas. Insert past it and the status line says exactly that: over the view cap, no real limit.

Common Mistakes

• Treating the array as sorted. It isn't — the number-one heap misconception. After the trace above the array reads [2, 3, 8, 5, 9]: 8 before 5. Left to right is the org chart row by row, not by rank; sorted output comes from extracting repeatedly, which is exactly heap sort.
• Sifting down toward the wrong child. Swap with the larger child of a min-heap and you've planted a violation directly beneath the node you just "fixed." Best child first, then compare, then swap.
• Botching the index math. Children at 2i + 1 and 2i + 2, parent at (i − 1) // 2. The 1-indexed variant (2i, 2i + 1, i // 2) is also common, and mixing the two conventions produces a heap that is subtly, miserably wrong.
• Expecting search. A heap can't find an arbitrary value faster than O(n) — the property says nothing about where a non-extremal element lives. For "find this key" or "list in order," you want a balanced BST; reach for a heap only when the question is always "give me the extremum."
• Flipping the comparator casually. Min versus max is one < versus >. Flip it and every caller expecting the other ordering breaks silently — the heap stays internally valid, just upside down.