假設你給了一個合併函數，它將在O（s1 + s2）時間內合併（找到兩個大小爲s1和s2的列表L1和L2）。合併大小爲s1，s2，...，sk的k個列表的最佳方法是什麼？什麼是合併k列表的最佳方式？
我在想，我們應該首先對s1，...，sk進行排序，並對前兩個對應於最低兩個尺寸的列表進行排序。合併這些數據時，我們會在已排序的大小列表中找到它們大小的位置，並繼續這個過程，直到最終列出一個列表。
我遇到了兩件事情：1.這是否確實是最佳的（是否有另一種方法會在更快的時間內返回）？ 2.當我們合併時，我們如何分析列表大小變化時的運行時間？
這是恰恰同樣的問題找到位編碼的最佳可變長度用於從k符號的字母表與已知的頻率s1, s2, … sk形成的字符串。你的算法恰恰是Huffman algorithm，你會在任何關於算法（和許多在線資源）的教科書中找到最優性的證明，因爲它是具有簡單正確性證明的貪婪算法的經典案例。
雙向合併的重複應用會導致一個二叉樹，其中每個節點都是合併。給定該樹，任何葉對整體合併總成本的貢獻是該葉的權重乘以樹中的深度。 （每個節點是一個合併，並且葉中的值完全參與從葉到根的路徑中的合併;這種合併的數量是樹中葉的深度。）同樣 - 或者相同 - - ，霍夫曼編碼比特串的總長度是符號的權重（頻率）與構造樹中對應於該符號的葉的深度的乘積之和。
算法的一個小改進（人們常常錯過編寫霍夫曼樹建設者）：有必要對權重進行排序s1, s2, … sk，但這是唯一需要的排序。從那裏算法總是選擇兩個最低節點並添加它們。得到的和的大小必須是單調不減的（如果總和小於前一個和，則前一個和不可能是兩個最小元素的和）。所以你可以把這些錢放在一個隊列中;在每一步中，您可以從排序的樹葉陣列或節點的（隱式）排序隊列中選擇兩個最小的元素。
這可以通過用節點隊列覆蓋樹葉陣列來進一步優化。 （隊列從陣列底部向頂部增長;證明隊列頂部永遠不會超過陣列底部，這相當簡單）。
優秀的答案！謝謝。您能否詳細說明爲什麼我們只需要對權重進行一次排序？假設權重的排序列表是s1，s2，...，sk。然後，該算法將合併對應於s1和s2的列表以生成s12，並且「已排序」列表現在將看起來像s12，s3，...，sk。但s12 + s3可能大於s3 + s4。 – 2014-10-05 10:50:47
或者是：如果我們的排序大小是對應於列表L1，L2，... Lk的s1，s2，...，sk，那麼我們首先將L1和L2合併到L12中，然後將L3和L4合併到L34中以獲得L12 ，L34，...，Lk-1Lk，並繼續這個過程，直到我們剩下一個列表？如果是這樣，當清單數量很奇怪時我們該怎麼辦？例如，如果我們有L1，L2，L3，L4，L5，迭代看起來如下：L12，L34，L5 - > L1234，L5 - > L12345？ – 2014-10-05 10:58:31
@BobJonas：有兩個列表：葉子列表（不斷變小）和化合物列表（正在增長）。最初，化合物是空的。我們從s1，s2，s3，s4開始; - 。第一步之後，我們有'（s1，s2），s3，s4，...; s12'。 （s1，s2，s3，s4），s5，s6，...; s12（s12，s3，s4）如果s3和s4現在是最小的（s12> s4） ，s34'。否則's3'和's12'是兩個最小的，並且我們會有'（s1，s2，s3），s4，s5，...;（s12），s123'。我們還必須查看三個元素以選擇最小的兩個：每個列表中最小的一個，並且... – rici 2014-10-05 12:25:28