4.17
Revision as of 18:25, 20 September 2020 by Algowikiadmin (talk | contribs) (Created page with "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 ex...")
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).
Other solution: Create a heap using bubble down per 4.3.4 in the book. This takes O(n) time. Then, extract from the heap in k times to get the smallest k elements. This takes O(k*logn) time. Therefore, total time is O(n + k*logn)
Back to Chapter 4
