Difference between revisions of "TADM2E 4.14"
(Recovering wiki) |
(Recovering wiki) |
||
| Line 2: | Line 2: | ||
The elementary algorithm compares the heads of each of | The elementary algorithm compares the heads of each of | ||
| − | the | + | the <math>k</math> sorted lists to find the minimum element, puts this in the sorted |
list and repeats. | list and repeats. | ||
| − | The total time is | + | The total time is <math>O(k n)</math>. |
Suppose instead that we build a heap on the head elements of each | Suppose instead that we build a heap on the head elements of each | ||
| − | of the | + | of the <math>k</math> lists, with each element labeled as to which list it is from. |
| − | The minimum element can be found and deleted in | + | The minimum element can be found and deleted in <math>O(\log k)</math> time. |
| − | Further, we can insert the new head of this list in the heap in | + | Further, we can insert the new head of this list in the heap in <math>O(\log k)</math> |
time. | time. | ||
| − | An alternate | + | An alternate <math>O(n \log k)</math> approach would be to |
merge the lists from as in mergesort, | merge the lists from as in mergesort, | ||
| − | using a binary tree on | + | using a binary tree on <math>k</math> leaves (one for each list). |
problem | problem | ||
Latest revision as of 18:22, 11 September 2014
Scan through all k lists in any order and use the stream of elements to build a heap of k elements. Since bubble_down works in O(logk) for a heap of k elements, we thus solve the problem in O(nlogk).
The elementary algorithm compares the heads of each of the $ k $ sorted lists to find the minimum element, puts this in the sorted list and repeats. The total time is $ O(k n) $. Suppose instead that we build a heap on the head elements of each of the $ k $ lists, with each element labeled as to which list it is from. The minimum element can be found and deleted in $ O(\log k) $ time. Further, we can insert the new head of this list in the heap in $ O(\log k) $ time. An alternate $ O(n \log k) $ approach would be to merge the lists from as in mergesort, using a binary tree on $ k $ leaves (one for each list). problem
