Content deleted Content added
Corrected to show that n + k log k = Theta(n + k log n). When k dominates, k is Omega(n / log n), which implies log k = Theta(log n). |
Privychick (talk | contribs) m →Heap-based solution: typo fix |
||
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
===Solution by partitioning selection===
| |||