d-堆

  • 2019 年 10 月 7 日
  • 筆記

二叉堆因為實現簡單,因此在需要優先隊列的時候幾乎總是使用二叉堆。d-堆是二叉堆的簡單推廣,它恰像一個二叉堆,只是所有的節點都有d個兒子(因此,二叉堆又叫2-堆)。下圖表示的是一個3-堆。注意,d-堆要比二叉堆淺得多,它將Insert操作的運行時間改進為。然而,對於大的d,DeleteMin操作費時得多,因為雖然樹淺了,但是d個兒子中的最小者是必須找到的,如果使用標準算法,將使用d-1次比較,於是將此操作的時間提高到 。如果d是常數,那麼當然兩種操作的運行時間都為 O(logN)。雖然仍可以使用一個數組,但是,現在找齣兒子和父親的乘法和除法都有個因子d,除非d是2的冪,否則會大大增加運行時間,因為我們不能再通過二進制移位來實現除法和乘法了。D-堆在理論上很有趣,因為存在許多算法,其插入次數比刪除次數多得多,而且,當優先隊列太大不能完全裝入內存的時候,d-堆也是很有用的,在這種情況下,d-堆能夠以與B-樹大致相同的方式發揮作用。

除了不能執行Find操作外(指以對數執行),堆的實現最明顯的兩個缺點是:將兩個堆合併成一個堆是很困難的。這種附加的操作叫做Merge。存在許多實現堆的方法使得Merge操作的運行時間為O(logN),如下篇介紹的左式堆。