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

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

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

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