CODEWITHSUNDEEP
c++arraysdata-structuresmin-heap
Anonymous User
Anonymous User

Reputation: 21

Can i use the normal min heap method for solving "Merge k sorted array"

we have been given k sorted arrays. Lets say k =3 a1={1,4,7} a2={3,5} a3={2,6,7} now we are supposed to merge these 3 arrays in sorted order. Hence the output will be {1,2,3,4,5,6,7,7}. Now in the tutorial that i am following they have maintained an index and used pairs to solve this question using min heaps. But my question is that since min heaps stores the elements in sorted order so can we just simply use the push function of min heap for all the elements from k arrays and then at the end printing the min heap?? instead of keeping index and making pairs? in c++?

Upvotes: 1

Views: 527

Answers (3)

Evgen Buiko
Evgen Buiko

Reputation: 27

But my question is that since min heaps stores the elements in sorted order so can we just simply use the push function of min heap for all the elements from k arrays and then at the end printing the min heap??

The main recursive rule for min-heap: left and right child should be less than parent. It does not mean that left child should be less than parent of right side of tree. Attached image show min-heap. But this min-heap is not finally sorted array

image

Upvotes: 0

Projekat Pr
Projekat Pr

Reputation: 37

I think this Algorithm is what you are looking for Algorithm:

Create a min Heap and insert the first element of all k arrays. Run a loop until the size of MinHeap is greater than zero. Remove the top element of the MinHeap and print the element. Now insert the next element from the same array in which the removed element belonged. If the array doesn’t have any more elements, then replace root with infinite.After replacing the root, heapify the tree.

And about time needed: O( n * k * log k), Insertion and deletion in a Min Heap requires log k time. So the Overall time compelxity is O( n * k * log k)

Upvotes: 0

HTNW
HTNW

Reputation: 29193

Sure, but that's slow. You are throwing away the work that has already gone into the input arrays (that they are already sorted) and basically making the sorted array from the unsorted collection of all the elements. Concretely, if all the input arrays have average length n, then you perform k*n inserts into the heap, and then you extract the minimum k*n times. The heap operations have complexity O(log(k*n)). So the entire algorithm takes O(k*n*log(k*n)) time, which you may recognize as the time it takes to sort an unsorted array of size k*n. Surely there's a better way, because you know the input arrays are sorted.

I presume the given solution is to construct k "iterators" into the arrays, place them into a heap sorted by the value at each iterator, and then repeatedly remove the least iterator, consume its value, increment it, and place it back in the heap. The key is that the heap (which is where all the work is happening) is smaller: it contains only k elements instead of k*n. This makes every operation on the heap faster: now the heap operations in this algorithm are O(log k). The overall algorithm is now O(k*n*log k), an improvement.

Upvotes: 1

Related Questions