Binary heaps · swim, sink, and bottom-up construction
Small screen: the drawing scrolls sideways; switch to the tree drawing for the most compact view.
The code and the analysis are below the drawing.
Show
Order
Drawing
Detail
Leave the field empty for a random key. New operations are added right after the one on screen. Click a node to change its key.
n
— / —Delay650ms
The heapzoom100%
What happens
Cost
Returned by delMax()
Java code
Analysis
Each node may sink at most down to the last level, i.e.,
steps. Summed over the levels:
The sum, to scale
How does it scale?
Comparisons per key, bottom-up construction vs. inserting the keys one
by one. Worst case: keys sorted against the heap order. Random: average of 5 random permutations.