1,484 views

1 Answer

Best answer
7 votes
7 votes
$k$ sorted lists, total $n$ elements.
Construct a min heap  by taking the first element from all the arrays.
Extract the min element and print. Take the next element from the array in which the min element was present (the heap entry should store the origin array information), and insert to min heap. Continue till min heap becomes empty.

Time Complexity =  $O(k)$ {min heap construction} $+ O(n\log k)$ {n time extract min from heap} $= O(n\log k).$
selected by

Related questions

4 votes
4 votes
2 answers
1
Shreya Kapoor asked Jun 16, 2016
8,377 views
$k$ sorted arrays, each with $n$ elements, you want to combine those arrays into a single sorted array of $kn$ elements. Time Complexity?a.$O(kn)$b.$O(knlogk)$ c.$O(nk^{...
8 votes
8 votes
2 answers
3
1 votes
1 votes
1 answer
4
radha gogia asked Apr 10, 2016
2,044 views
According to me first we sort the array in O(nlogn) time and then in O(k) time , find the product , so total time complexity is O(nlogn) , so am I right or can it be done...