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'')}}.
Common in C++ STL implementations is a pass of [[Heap (data structure)#Applications|heapselect]] for an ''unsorted'' list of ''k'' elements, followed by a [[heapsort]] for the final result.<ref>{{cite web |title=std::partial_sort |url=https://en.cppreference.com/w/cpp/algorithm/partial_sort |website=en.cppreference.com}}</ref>
===Solution by partitioning selection===
| |||