Content deleted Content added
Artoria2e5 (talk | contribs) |
Artoria2e5 (talk | contribs) |
||
Line 5:
==Offline problems==
===Heap-based solution===
[[Heap (data structure)|Heaps]] admit a simple single-pass partial sort when {{mvar|k}} is fixed: insert the first {{mvar|k}} elements of the input into a max-heap. Then make one pass over the remaining elements, add each to the heap in turn, and remove the largest element. Each insertion operation takes {{math|''O''(log ''k'')}} time, resulting in {{math|''O''(''n'' log ''k'')}} time overall; this algorithm is practical for small values of {{mvar|k}} and in [[online algorithm|online]] settings.<ref name="aofa04slides"/>
Another option is to build a min-heap for all the values (the build takes {{math|''O''(''n'')}}) and take out the head of the heap K times, each remove operation takes {{math|''O''(log ''n'')}}. In that case the algorithm takes {{math|''O''(''n'' + ''k'' log ''n'')}}. ===Solution by partitioning selection===
| |||