there is another way: group n array in two-two pairs of arrays & merge themsecond time you have n/2 array do the same again & again, till you are remaining with the 1 array
it is same like merge sort ,just we are starting from middle of the process instead of at the end
it will give you same complexity as doing it with the mean heap On 25-03-2011 19:21, Dave wrote:
Construct a min-heap comprising the value of first element of each array, a pointer to the array, and the index of the element. Now, while the heap is non-empty, output the value in the root of the heap, replace the root with the next element of the same array, and restore the heap condition. If all elements of the array have been used, then replace the root with the last element of the heap, reduce the size of the heap by 1, and restore the heap condition. Dave On Mar 25, 3:06 am, bittu<shashank7andr...@gmail.com> wrote:Given k sorted arrays each of length n, construct a single merged and sorted array.focus on running time and space complexity my soln. 1st basic soln..simple merge sort all whet we does in merging 2 sorted array it too complex for big K 2nd i have approach using min-heap as well but not able to figure the working code ..dono why? lets c what others think Approach& Exactness of The Solution matters here Thanks Shashank
-- Thanks & Regards Rajesh Patidar -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
<<inline: signature.png>>
