Medium
Bottom-up heapify vs. n successive heap inserts
There are two ways to turn an array of n arbitrary keys into a binary min-heap. The first starts from an empty heap and inserts the keys one at a time, each insert appending at the end and sifting the new key up. The second (Floyd's bottom-up heapify) treats the array as an already-shaped complete tree and calls sift-down on every internal node, from index n/2 - 1 down to 0. What are their worst-case running times?
39 of 46 in Data Structures & Algorithms