Άσκηση 1
Give an O(nlogk) time algorithm to merge k sorted lists L1 .. Lk into one sorted list.
n is the total number of elements.
Solution
We will use a min-heap of k pairs of the form (a, La[pa]) for 1 ≤ a ≤ k.
Each element a holds a pointer to it's origin list and the current index of that list.
• First we build the heap with all first elements in each list L1 .. Lk in O(k)
• In each step extract the minimal element of the heap and add it at the end of the output list M (with associated index j)
• Add the next element from the list of the one extracted
for i = 1 to k
A ← (i, Li[1])
pi ← 2
Build-Heap(A, k)
for j = 1 to n
(d, M[j]) ← Extract-Min(A)
j ← j+1
if pd ≤ Ld.length
Heap-Insert(A, (d, Ld[pd]))
[pd] ← [pd] + 1
Worst case time analysis:
Build-Heap : O(k)
Extract-Min : O(log k)
Heap-Insert : O(log k)
Total O(nlogk)
και πραγματικά μου έρχεται να τουν την γράψω στα Αγγλικά!!
