外部排序：多路合併

Question

在多路合併的任務是找到最小的元素從k個元素的

解決辦法：優先級隊列

理念：以來自前k運行的最小元素，並將其存儲到堆樹中的主內存。

然後重複輸出堆中最小的元素。最小的元素將被來自其運行的下一個元素替換。

完成第一組運行後，對下一組運行進行同樣的處理。

假設我的尺寸的主內存（M）小於K，我們如何才能要素，換句話說，路合併算法如何多合併作品進行排序，如果內存大小M是少於k個

例如，如果我的M = 3，我已經以下

TAPE1：8 9 10 TAPE2：11 12 13 Tape3：14 15 16 Tape4：4 5 6

我的問題如何muliway合併將工作，因爲我們將讀8,11,14並建立優先隊列，我們​​放置8輸出磁帶，然後轉發Tape1 ，當Tape4被讀取時，我沒有得到什麼，我們將如何比較已經寫入輸出磁帶？

謝謝！

Answer 1

它不起作用。您必須選擇足夠小的可用內存的k。

在這種情況下，您可以執行前3個磁帶的3路合併，然後在該結果和剩餘磁帶之間進行雙向合併。或者你可以做3個2路合併（兩對磁帶，然後合併結果），這是更容易實現，但更多的磁帶訪問。

理論上你可以放棄優先隊列。然後，您不需要在內存中存儲k元素，但您經常需要查看所有k磁帶上的下一個元素才能找到最小的元素。