Skip to interview prep
Apexed

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
Why does bottom-up build-heap run in O(n) when each sift-down can cost O(log n) — Data structures & algorithms interview question — Apexed