Skip to content
Get started

Worst case of bottom-up heap construction

Floyd's bottom-up build-heap turns an array of n=255n = 255 keys into a max-heap: for each internal node from the last one back to the root, it sifts the key down (swapping with its larger child) until heap order holds. Over all inputs, what is the maximum total number of swaps?

Show hints (3)+
  1. A key sifted down from a node can move at most that node's height.
  2. Count how many nodes sit at each height in a perfect tree with 255 nodes.
  3. Is there an input that makes every key sink all the way?

Answer

Reveal answer →

247

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading

Related questions