Difference between revisions of "TADM2E 4.14"

Revision as of 18:13, 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 <math>k</math> sorted lists to find the minimum element, puts this in the sorted list and repeats. The total time is <math>O(k n)</math>. Suppose instead that we build a heap on the head elements of each 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 <math>O(\log k)</math> time. Further, we can insert the new head of this list in the heap in <math>O(\log k)</math> time. An alternate <math>O(n \log k)</math> approach would be to merge the lists from as in mergesort, using a binary tree on <math>k</math> leaves (one for each list). problem