Intermediate · Module 14 · Lesson 1
Binary heap
Complete-tree layout, heap property, and array indexes.
Lesson 77 of 123
1d streakInteractive Visualization
Trace the algorithm state by state
Change the inputs, run an operation, and connect each visible state change to the explanation below.
Interactive algorithm lab
Binary Max Heap
Complete-tree shape with parent dominance
Phase
insert
Heap size
1
Maximum
7
Extracted
—
Why this step happens
7 enters at the next open leaf to preserve the complete-tree shape.
Only the path from the new leaf to the root can violate the max-heap property.
The Binary Heap: Complete Tree Architecture & Array Indexing
A Binary Heap is a complete binary tree implemented efficiently as a flat array without any pointer nodes. It satisfies the Heap Property: in a Min-Heap, every parent is smaller than or equal to its children (parent.val <= child.val), placing the global minimum at the root. In a Max-Heap, the root holds the maximum.
Tree View (Complete Binary Tree):
[ 10 ] (index 0)
/ \
[ 20 ] [ 30 ] (index 1, 2)
/ \ / \
[ 40 ] [ 50 ] [ 60 ] [ 70 ] (index 3, 4, 5, 6)
Flat Array View:
Index: 0 1 2 3 4 5 6
+------+------+------+------+------+------+------+
Value: | 10 | 20 | 30 | 40 | 50 | 60 | 70 |
+------+------+------+------+------+------+------+
The Zero-Index Arithmetic Formulas:
For any element at index i:
- Parent Index: (i - 1) / 2 (e.g., Parent of idx 4 is (4-1)/2 = 1 -> Value 20)
- Left Child Index: 2 * i + 1 (e.g., Left of idx 1 is 2(1)+1 = 3 -> Value 40)
- Right Child Index: 2 * i + 2 (e.g., Right of idx 1 is 2(1)+2 = 4 -> Value 50)
Zero pointer overhead! All node links are computed by instant CPU bit arithmetic.| Operation | Heap Method | Time Complexity | Mechanism |
|---|---|---|---|
| Peek Min/Max | peek() | O(1) | Read array[0] directly |
| Insert / Push | offer(x) / push(x) | O(log n) | Append at array end; sift-up by swapping with parent |
| Extract Min/Max | poll() / pop() | O(log n) | Replace array[0] with last element; sift-down by swapping with smaller child |
| Build Heap | heapify() | O(n) | Bottom-up sift-down on all non-leaf nodes |
| Arbitrary Search | contains(x) | O(n) | Heaps lack horizontal ordering; requires scanning full array |
INSERT 15 INTO MIN-HEAP:
1. Append 15 at end of array (index 7).
2. Sift-Up: Compare 15 with parent at (7-1)/2 = 3 (val 40).
15 < 40 -> SWAP 15 and 40!
3. Compare 15 with parent at (3-1)/2 = 1 (val 20).
15 < 20 -> SWAP 15 and 20!
4. Compare 15 with parent at (1-1)/2 = 0 (val 10).
15 >= 10 -> STOP! Heap property restored in O(log n) swaps.
EXTRACT-MIN (POLL):
1. Root is 10. Save 10 as return value.
2. Move last element (val 40) to root index 0.
3. Sift-Down: Compare 40 with its children (left 20, right 30).
Smaller child is 20. 40 > 20 -> SWAP 40 and 20!
4. Compare 40 with next children (left 50, right 60).
Both children are larger -> STOP! Restored in O(log n) swaps.Cost Model
Complexity & Trade-offs
When to use it
- Top-k, streaming medians, scheduling, and best-first frontiers.
- Repeated access to an extreme without fully sorting.
- Merging sorted sources.
Common mistakes
- Choosing the wrong heap direction for a bounded top-k set.
- Assuming heap iteration is globally sorted.
- Claiming bottom-up heap construction is O(n log n).
Practice prompts
- Reproduce the worked Binary heap example without looking at the trace.
- Change one input condition and explain whether the Binary heap invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check