Algowikiadmin: Recovering wiki

2014-09-11T18:22:48Z

Recovering wiki

Algowikiadmin: Recovering wiki

2014-09-11T18:13:30Z

Recovering wiki

New page

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

@@ Line 2: / Line 2: @@
 The elementary algorithm compares the heads of each of
-the &lt;math&gt;k&lt;/math&gt; sorted lists to find the minimum element, puts this in the sorted
+the <math>k</math> sorted lists to find the minimum element, puts this in the sorted
 list and repeats.
-The total time is &lt;math&gt;O(k n)&lt;/math&gt;.
+The total time is <math>O(k n)</math>.
 Suppose instead that we build a heap on the head elements of each
-of the &lt;math&gt;k&lt;/math&gt; lists, with each element labeled as to which list it is from.
+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 &lt;math&gt;O(\log k)&lt;/math&gt; time.
+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 &lt;math&gt;O(\log k)&lt;/math&gt;
+Further, we can insert the new head of this list in the heap in <math>O(\log k)</math>
 time.
-An alternate &lt;math&gt;O(n \log k)&lt;/math&gt; approach would be to
+An alternate <math>O(n \log k)</math> approach would be to
 merge the lists from as in mergesort,
-using a binary tree on &lt;math&gt;k&lt;/math&gt; leaves (one for each list).
+using a binary tree on <math>k</math> leaves (one for each list).
 problem

TADM2E 4.14 - Revision history

Algowikiadmin: Recovering wiki

Algowikiadmin: Recovering wiki