Partial sorting: Difference between revisions

Revision as of 09:00, 15 April 2017

Revision as of 09:04, 15 April 2017

Line 7:

[[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 options 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+klog ''n'')}}.

One of the fastest Heap-based solution is to use 2 min heaps. the first one with all the elements (size n) and the secand one with max size of k. At start you build the big heap with all elements, takes {{math|''O''(''n'')}}. Then you incertinsert  the root of the big heap with his index to the small heap (without taking it out). After that, each time you take out the root of the small heap and insert the small heap his 2 children that in the big heap. Because the size of the small heap maximum increased by 1 each time, k times, the size of the small heap is blocked by k. That is why it takes only {{math|''O''(log ''k'')}} to arrange the small heap after taking out the root. The algorithm takes {{math|''O''(n+klog ''k'')}}, but it requires {{math|''O''(''k'')}} space in addition.

===Solution by partitioning selection===