Difference between revisions of "TADM2E 4.12"
From Algorithm Wiki
(Recovering wiki) 
(No difference)

Revision as of 18:13, 11 September 2014
Scan through the array to build an outoforder heap, that is, the first element is indeed the smallest, but necessarily any of the other elements. This takes us O(n). Then extract from the heap k times to get the smallest k elements using O(klogn). Thus the total time is O(n+klogn).