196. Why does bottom-up build-heap run in O(n) when each sift-down can cost O(log n)?
HardPriority queues & heaps
Technical
Show model answer
Bottom-up construction calls sift-down on every internal node from the last parent back to the root. A node's sift-down costs at most its height, and most nodes are near the bottom: about n/2 leaves have height 0, n/4 nodes have height 1, n/8 have height 2, and so on.
So the total work is at most the sum of node heights, about n·(1/4 + 2/8 + 3/16 + ...) = n·Σ k/2^(k+1) = n. More precisely a perfect tree of height h has total height 2^(h+1) − h − 2 = O(n). Repeated insertion instead is O(n log n) because inserts sift up from the deep levels where most nodes live.
What interviewers listen for
- Sum of heights in a complete tree is O(n)
- Sift-down from the bottom, not sift-up from the top