K方式合併排序陣列實現使用最小堆

Question

我一直在試圖弄清楚如何實現K方式合併以下算法。

Algorithm: 
1)Initialize an array of size n*k. 
2) Initialize a min heap of size k, to hold the smallest element of each array. 
3) Add the smallest element from the minHeap into the output array. 
4)Move the next element from the array from which the min element was derived onto the heap. // How would one implement this? 
5) Repeat step 4 until all the arrays are empty and the minHeap is empty. 

我已經能夠實現所有，但我的算法的第4步。如何跟蹤從中提取最小元素的數組？

Answer 1

嘗試保持元素和數組在pair。元素將是關鍵，數組（指向它的）將是值。配對應該可以通過它的鍵進行排序。
當您從堆中提取最小的對時，您將該對中的鍵作爲您想要的元素，並且該對中的值將是包含該元素的數組。

重要：根據您使用的語言，不要將數組作爲值複製，而只保存指向它們的指針（比如C++）或其引用（即Java）。