Talk:TADM2E 4.12

From Algorithm Wiki
Jump to: navigation, search

It seems to me the first option (find smallest, move to top, extract k-1) wouldn't work, because using heapify assumes the heaps below the current are well-formed. That's why using heapify from the bottom up works, because the leaves are valid heaps. This first approach attempts to build the heap from the top down without having a valid heap to start.