左傾堆枚舉算法的研究.pdf

1、枚舉有兩層含義：一是計(jì)數(shù)，即計(jì)算具有某種特性的所有對象的個(gè)數(shù)；二是生成，即產(chǎn)生具有某特性的所有對象。本文主要介紹了二叉樹的枚舉，最大值堆的枚舉和自己所研究的左傾堆的枚舉。
　　 二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)。二叉樹枚舉的研究無論在算法理論上還是在實(shí)際應(yīng)用中都具有重要的意義。與二叉樹枚舉計(jì)數(shù)相關(guān)的最有名的就是Catalan數(shù)。目前二叉樹的枚舉生成主要是基于編碼的二叉樹生成算法[3-8]，這些算法建立了二叉樹集合和編碼集合間的一一對應(yīng)

2、關(guān)系，將二叉樹的枚舉生成問題轉(zhuǎn)化為編碼的枚舉生成問題。
　　 最大值堆在結(jié)構(gòu)上是一棵完全二叉樹。最大值堆的枚舉生成是將數(shù)值映射到結(jié)構(gòu)固定的完全二叉樹上。目前最大值堆的枚舉生成[10-14]大都是基于回溯法，并采用單個(gè)數(shù)判斷法和層次判斷法來減少回溯的次數(shù)。
　　 左傾堆是具有堆序性質(zhì)和左傾性質(zhì)的特殊二叉堆。它可以作為優(yōu)先隊(duì)列的一種實(shí)現(xiàn)方式，跟普通的二叉堆相比，有著更加高效的合并操作[16]。左傾堆的枚舉對于研究左傾堆的性質(zhì)

3、、分析其相關(guān)算法的平均復(fù)雜性有著重要意義，并為左傾堆的隨機(jī)生成提供了基礎(chǔ)。本文首先根據(jù)左傾堆的距離和結(jié)點(diǎn)數(shù)的關(guān)系，用組合方法推導(dǎo)出了左傾堆枚舉計(jì)數(shù)的遞推公式，然后提出了基于構(gòu)造的左傾堆枚舉生成算法和基于排列的左傾堆枚舉生成算法?；跇?gòu)造的左傾堆的枚舉生成算法是在含n-1個(gè)結(jié)點(diǎn)的左傾堆中插入一個(gè)結(jié)點(diǎn)構(gòu)造所有含n個(gè)結(jié)點(diǎn)的左傾堆；基于排列的左傾堆枚舉生成算法的依據(jù)是本文提出的一個(gè)定理，即一個(gè)二叉堆的中序序列能夠唯一的確定該二叉堆。該定理確立了

4、一個(gè)含n個(gè)結(jié)點(diǎn)的二叉堆與一個(gè)n元排列的一一對應(yīng)關(guān)系。基于排列的左傾堆枚舉生成算法通過生成n元排列，將排列看成是二叉堆的中序序列，通過中序序列來構(gòu)造二叉堆，再從二叉堆中篩選出左傾堆，該算法簡化了左傾堆的枚舉過程，相對比基于構(gòu)造的左傾堆的枚舉生成算法，左傾堆的枚舉生成效率提高了35％以上。同時(shí)本文進(jìn)一步改進(jìn)了基于排列的左傾堆枚舉生成算法，使得左傾堆的枚舉生成效率進(jìn)一步提高了40％左右。
　　 本文最后對三種結(jié)構(gòu)的枚舉進(jìn)行了總結(jié)，對左