Difference between revisions of "TADM2E 4.12"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
(No difference)

Revision as of 18:13, 11 September 2014

Scan through the array to build an out-of-order 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).