Difference between revisions of "TADM2E 4.12"
From Algorithm Wiki
(Recovering wiki) |
(Added a solution which was more clear) |
||
| Line 2: | Line 2: | ||
Then extract from the heap k times to get the smallest k elements using O(klogn). | Then extract from the heap k times to get the smallest k elements using O(klogn). | ||
Thus the total time is O(n+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) | ||
Latest revision as of 02:36, 24 February 2019
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)
