證明使用min-heap合併k個排序列表的算法

Question

我正在閱讀CLRS並且在練習6.5-8時遇到了一些問題。

舉一個爲O（n LG K）-time算法來合併ķ排序的列表爲一個 排序的列表，其中n是在所有的輸入 列表元素的總數。 （提示：使用對於k-方式合併一個min0heap。）

將溶液，如大家說，

1）使用k個列表的第一個元素構建的k元件最小堆，

2）提取分鐘（）從堆中獲得最小的元素，並將它附加到結果列表中，

3）選擇下一個元件從同一列表，因爲我們只從提取的一個堆。將它插入堆並轉到2）。

我可以理解時間是O（n lg k），但是我沒有得到步驟3中選擇的正確性）。它似乎明顯，但是有一些正式的證據？

Answer 1

正確性證明的主要推力是剩餘的最少元素始終是要提取的元素。支持這個聲明的關鍵不變量是，對於每個列表，優先級隊列包含從該列表剩餘的最少元素。由此可知，由於剩餘的最小元素也是來自列表的剩餘中的最小元素，所以它由extract-min返回。

我們需要從第3部分中的相同列表中選擇一個元素來維護每個列表在隊列中具有最少元素的不變量。否則，我們可以像

1 2 
3 4 

的情況下，如果我們拉1含1和3的初始隊列和4個取代它，接下來的提取將是3，這是不對的。