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

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

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

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