Worst case of bottom-up heap construction
Floyd's bottom-up build-heap turns an array of 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)+
- A key sifted down from a node can move at most that node's height.
- Count how many nodes sit at each height in a perfect tree with 255 nodes.
- Is there an input that makes every key sink all the way?
Answer
Reveal answer →Final answer
247
Create a free account to see the full worked solution and track your progress.
Interview format: Prop Trading