TADM2E 4.14

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