最小-最大堆枚舉算法的研究.pdf

1、堆是最基本的數據結構之一，對堆進行枚舉，可以作為堆上算法復雜性分析的有力工具，有著重要的意義。堆的枚舉有兩種含義，一種是計數，即計算出具有某種特性的堆的總數目；另一種是生成，即一個一個地產生所有的具體堆。
　　 最小-最大堆是一種完全二叉樹形狀的堆結構，現已被廣泛應用在數據排序、最短路求解、任務調度、最小生成樹等諸多領域。在最小一最大堆上以O(1)的復雜度即可取得最小元與最大元：插入元素、刪除最小元、刪除最大元的復雜度都是O(l

2、og n)。對這些運算的高效支持使得最小一最大堆成為雙端優(yōu)先隊列的優(yōu)秀實現方法。由于其完全二叉樹形狀的特點，可以使用操作簡便的隱式存儲結構進行存儲，避免了復雜的指針操作，它從而得到廣泛應用。
　　 首先，在已有計數公式的基礎上，結合對堆中各子樹結點數的研究，本文得出了含n結點的堆的直接計數公式。不同于以往基于遞推的計數公式，本文公式僅與結點數n有關，是一個直觀的計數公式，由它得到的求解算法時間復雜度是O(n)；較之已有的計數算法

3、，此計數算法避免了以往O(n)的存儲空間。
　　 接著，本文先給出了一個基礎的最小一最大堆生成算法LBG，它采用了“單個數判斷法”和“層次判斷法”兩個基本方法以減少冗余步驟的生成。該基礎算法可以完備地枚舉出所有含n個結點的最小一最大堆。
　　 最后，考慮到滿堆在枚舉集合上具有對偶特性，在進行堆的生成時，可以僅生成每對對偶堆中的一個，通過交換根結點的左右子樹得到另一個堆：另外，將一個最小一最大堆的生成分解成對其兩個子堆的生