Consider the following, O( nlgk )-time algorithm to merge k sorted list into one
ID: 3774537 • Letter: C
Question
Consider the following,O(nlgk)-time algorithm to merge k sorted list into one sort list where n is the total number of elements in all the input lists. Below is the algorithm for this; however how this can be implemented in python v2.7 using heapq module.
Algorithm: 1. Build a min-heap by choosing the first element from each of the k sorted lists. The heap size is k, so BUILD-MIN-HEAP will take O(k)time to build the min-heap. In this heap, list id of the list (or from which list it has been taken) will also be stored along with the heap elements At this stage, the root contains the minimum of the min-heap. 2. Now, put the root into the final sorted list. Then, the root will be replaced with the next elements of the same list. It will take a time complexity of O(1) time. At this stage. the min-heap property may be violated by the root. 3. Now, run the MIN-HEAPIFY root). The time taken in this is O(logk) 4. When the list is empty then repeat step (2) for non-empty list.Explanation / Answer
list[k] ; k sorted lists
heap[k] ; an auxiliary array to hold the min-heap
result[n] ; array to store the sorted list
for i := 1 to k ; O(k)
do
heap[i] := GET-MIN(list[i]) ; pick the first element
; and keeps track of the current index - O(1)
done
BUILD-MIN-HEAP(heap) ; build the min-heap - O(k)
for i := 1 to n
do
array[i] := EXTRACT-MIN(heap) ; store the min - O(logk)
nextMin := GET-MIN(list[1]) ; get the next element from the list 1 - O(1)
; find the minimum value from the top of k lists - O(k)
for j := 2 to k
do
if GET-MIN(list[j]) < nextMin
nextMin := GET-MIN(list[j])
done
; insert the next minimum into the heap - O(logk)
MIN-HEAP-INSERT(heap, nextMin)
done
this code is clearly explain in below
lists[k][?] // input lists
c = 0 // index in result
result[n] // output
heap[k] // stores index and applicable list and uses list value for comparison
// if i is the index and k is the list
// it has functions - insert(i, k) and deleteMin() which returns i,k
// the reason we use the index and the list, rather than just the value
// is so that we can get the successor of any value
where n is the total no of elements in inputlist,k is sorted list.
heapq.merge(*iterables)
Merge multiple sorted inputs into a single sorted output (for example, merge timestamped entries from multiple log files). Returns an iterator over the sorted values.
Similar to sorted(itertools.chain(*iterables)) but returns an iterable, does not pull the data into memory all at once, and assumes that each of the input streams is already sorted (smallest to largest).
You can also, instead of deleteMin and insert, have a getMin (O(1)O(1)) and an incrementIndex(O(logk)O(logk)), which will reduce the constant factor, but not the complexity.