Given m sorted lists, each containing n elements, print them efficiently in sorted order.
For example,
[10, 20, 30, 40]
[15, 25, 35, 45]
[27, 29, 37, 48]
[32, 33, 39, 50]
[16, 18, 22, 28]
Output:
[10, 15, 16, 18, 20, 22, 25, 27, 28, 29, 30, 32, 33, 35, 37, 39, 40, 45, 48, 50]
A simple solution would be to create an auxiliary array containing all lists elements [order doesnt matter]. Then use an efficient sorting algorithm to sort the array in ascending order and print the elements. The worst-case time complexity of this approach will be O[m.n.log[m.n]]. Also, this approach does not take advantage of the fact that each list is already sorted.
We can easily solve this problem in O[m.n.log[m]] time by using a min-heap. The idea is to construct a min-heap of size m and insert the first element of each list in it. Then, pop the root element [minimum element] from the heap and insert the next element from the same list as the popped element. Repeat this process till the heap is exhausted. Depending upon the requirement, either print the popped element or store it in an auxiliary array.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | #include #include #include using namespace std; // Data structure to store a heap node struct Node { // `val` stores the element, // `i` stores the list number of the element // `index` stores the column number of the i'th list from which element was taken int val, i, index; }; // Comparison object to be used to order the min-heap struct comp { bool operator[][const Node &lhs, const Node &rhs] const { return lhs.val > rhs.val; } }; // Function to merge `M` sorted lists each of size `N` and // print them in ascending order void printSorted[vector lists] { // create an empty min-heap priority_queue pq; // push the first element of each list into the min-heap // along with the list number and their index in the list for [int i = 0; i
Chủ Đề |