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

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

2、關(guān)系，將二叉樹(shù)的枚舉生成問(wèn)題轉(zhuǎn)化為編碼的枚舉生成問(wèn)題。
　　 最大值堆在結(jié)構(gòu)上是一棵完全二叉樹(shù)。最大值堆的枚舉生成是將數(shù)值映射到結(jié)構(gòu)固定的完全二叉樹(shù)上。目前最大值堆的枚舉生成[10-14]大都是基于回溯法，并采用單個(gè)數(shù)判斷法和層次判斷法來(lái)減少回溯的次數(shù)。
　　 左傾堆是具有堆序性質(zhì)和左傾性質(zhì)的特殊二叉堆。它可以作為優(yōu)先隊(duì)列的一種實(shí)現(xiàn)方式，跟普通的二叉堆相比，有著更加高效的合并操作[16]。左傾堆的枚舉對(duì)于研究左傾堆的性質(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元排列的一一對(duì)應(yīng)關(guān)系?；谂帕械淖髢A堆枚舉生成算法通過(guò)生成n元排列，將排列看成是二叉堆的中序序列，通過(guò)中序序列來(lái)構(gòu)造二叉堆，再?gòu)亩娑阎泻Y選出左傾堆，該算法簡(jiǎn)化了左傾堆的枚舉過(guò)程，相對(duì)比基于構(gòu)造的左傾堆的枚舉生成算法，左傾堆的枚舉生成效率提高了35％以上。同時(shí)本文進(jìn)一步改進(jìn)了基于排列的左傾堆枚舉生成算法，使得左傾堆的枚舉生成效率進(jìn)一步提高了40％左右。
　　 本文最后對(duì)三種結(jié)構(gòu)的枚舉進(jìn)行了總結(jié)，對(duì)左