數(shù)據(jù)結(jié)構(gòu)與算法-堆與優(yōu)先隊(duì)列

5二叉樹2/985.1二叉樹的概念5.2二叉樹的周游5.3二叉樹的存儲(chǔ)結(jié)構(gòu)5.4二叉搜索樹5.5堆與優(yōu)先隊(duì)列5.6Huffman樹及其應(yīng)用5.7二叉樹知識(shí)點(diǎn)總結(jié)主要內(nèi)容3/985.5.1堆的定義及其實(shí)現(xiàn)最小值堆：最小值堆是一個(gè)關(guān)鍵碼序列{K0，K1，…Kn-1}它具有如下特性：Ki≤K2i+1(i=0，1，…，n/2-1)Ki≤K2i十24/985.5.1堆的定義及其實(shí)現(xiàn)堆的性質(zhì)從邏輯的角度來講，堆是一種樹形結(jié)構(gòu)，而且是一種特殊的完全二叉樹。此完全二叉樹的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于序列中的一個(gè)關(guān)鍵碼，根結(jié)點(diǎn)對(duì)應(yīng)于關(guān)鍵碼K0，按層次從左至右依次類推。說其特殊，主要是因?yàn)槎研蛑皇蔷植坑行?，即最小堆?duì)應(yīng)的完全二叉樹中所有內(nèi)部結(jié)點(diǎn)的值均不大于其左右孩子的關(guān)鍵碼值，而一個(gè)結(jié)點(diǎn)與其兄弟之間沒有必然的聯(lián)系。最小堆不像二叉搜索樹那樣實(shí)現(xiàn)了關(guān)鍵碼的完全排序。相比較而言，只有當(dāng)結(jié)點(diǎn)之間是父子關(guān)系的時(shí)候，才可以確定這兩個(gè)結(jié)點(diǎn)關(guān)鍵碼的大小關(guān)系。5/98堆的另一個(gè)定義最大樹（最小樹）:每個(gè)結(jié)點(diǎn)的值都大于（小于）或等于其子結(jié)點(diǎn)（如果有的話）值的樹。最大堆（最小堆）：最大（最小）的完全二叉樹。6/98哪幾個(gè)是堆？141210876965302527108461020501121最大樹最小樹7/985.5.1堆的定義及其實(shí)現(xiàn)關(guān)鍵碼序列K={12，14，15，19，20，17，18，24，22，26}所對(duì)應(yīng)的最小堆形成的完全二叉樹形式為圖5.14所示：圖5.14最小堆對(duì)應(yīng)的完全二叉樹8/98堆的插入操作圖5.15在最小堆5.14中插入元素131215142019181713242622新元素添加到末尾(保持完全二叉樹的性質(zhì))；為了保持堆的性質(zhì)，沿著其祖先的路徑，自下而上依次比較和交換該節(jié)點(diǎn)與父節(jié)點(diǎn)的位置，直到重新滿足堆的性質(zhì)位置在插入過程中，總是自下而上逐漸上升，最后停留在某個(gè)滿足堆的性質(zhì)的位置，故此過程又稱為“篩選”9/98堆的刪除操作圖5.16在最小堆5.14中刪除元素14

12151420191817242622把最末端節(jié)點(diǎn)填入刪除產(chǎn)生的空位(保持完全二叉樹的性質(zhì))

為了保持堆的性質(zhì)，沿著其后繼節(jié)點(diǎn)的路徑，自上而下依次比較和交換該節(jié)點(diǎn)與字節(jié)點(diǎn)的位置，直到重新滿足堆的性質(zhì)位置10/98堆的建立（初始化）建堆過程：首先將所有關(guān)鍵碼放到一維數(shù)組中，這時(shí)形成的完全二叉樹并不具備最小堆的特性，但是僅包含葉子結(jié)點(diǎn)的子樹已經(jīng)是堆(即在有n個(gè)結(jié)點(diǎn)的完全二叉樹中，當(dāng)i>[n/2]-1時(shí)，以關(guān)鍵碼Ki為根的子樹已經(jīng)是堆)這時(shí)從含有內(nèi)部結(jié)點(diǎn)數(shù)最少的子樹（這種子樹在完全二叉樹的倒數(shù)第二層，此時(shí)i=[n/2]-1）開始，從右至左依次調(diào)整對(duì)這一層調(diào)整完成之后，繼續(xù)對(duì)上一層進(jìn)行同樣的工作，直到整個(gè)過程到達(dá)樹根時(shí)，整棵完全二叉樹就成為一個(gè)堆了11/98例子：最小堆的建立對(duì)于關(guān)鍵碼集合K={19，8，35，65，40，3，7，45}，用篩選法建堆的過程。其中n=8，n/2-1=3，所以從K3=65開始調(diào)整。1983573406545以k3為根的子樹65>45調(diào)整以k2為根的子樹35>3調(diào)整以k1為根的子樹8<40,8<45無需調(diào)整以k0為根的子樹19>3調(diào)整19>7調(diào)整圖5.17建堆過程示例12/98根據(jù)inta[10]={20,12,35,15,10,80,30,17,2,1}建立最大堆20123515108030172112345678910例子：最大堆的建立13/98最大堆的建立step1已知n=10;i=n/2=5;20123515108030172112345678910i2012351510803017211234567891014/98最大堆的建立step2i=420123515108030172112345678910201235151080301721i2i2i+11234567891015/98最大堆的建立step3i=320123517108030152112345678910201235171080301521i2i2i+11234567891016/98最大堆的建立step4_0i=220128017103530152112345678910201280171035301521i2i2i+11234567891017/98最大堆的建立step4_1i=2,j=2i=420178012103530152112345678910201780121035301521j2j2j+11234567891018/98最大堆的建立step5_0i=120178015103530122112345678910201780151035301221i2i2i+11234567891019/98最大堆的建立step5_1i=1,j=2i+1=380172015103530122112345678910801720151035301221j2j2j+11234567891020/98最大堆的建立step5_2801735151020301221123456789108017351510203012211234567891021/98堆的類定義和篩選法(1)[代碼5.11]堆的類定義和篩選法template<classT>classMinHeap{ //最小堆類定義private: T*heapArray; //存放堆數(shù)據(jù)的數(shù)組

int

CurrentSize; //當(dāng)前堆中元素?cái)?shù)目

int

MaxSize; //堆所能容納的最大元素?cái)?shù)目

voidswap(int

pos_x,int

pos_y); //交換位置x和y的元素

voidBuildHeap(); //建堆22/98堆的類定義和篩選法(2)public:

MinHeap(const

intn); //構(gòu)造函數(shù)，n表示堆的最大元素?cái)?shù)目

virtual~MinHeap(){delete[]heapArray;}; //析構(gòu)函數(shù)

bool

isEmpty(); //如果堆空，則返回真

bool

isLeaf(intpos)const; //如果是葉結(jié)點(diǎn)，返回TRUE

int

leftchild(intpos)const; //返回左孩子位置

int

rightchild(intpos)const; //返回右孩子位置

int

parent(intpos)const; //返回父結(jié)點(diǎn)位置

bool

Remove(intpos,T&node); //刪除給定下標(biāo)的元素

bool

Insert(constT&newNode); //向堆中插入新元素newNode T&RemoveMin(); //從堆頂刪除最小值 voidSiftUp(intposition); //從position向上開始調(diào)整，使序列成為堆 voidSiftDown(intleft); //向下篩選，參數(shù)left表示開始處理的數(shù)組下標(biāo)};23/98堆的類定義和篩選法(3)template<classT>MinHeap<T>::MinHeap(const

intn){ if(n<=0)return;

CurrentSize=0;

MaxSize=n; //初始化堆容量為n

heapArray=newT[MaxSize]; //創(chuàng)建堆空間

BuildHeap();//此處進(jìn)行堆元素的賦值工作}template<classT>bool

MinHeap<T>::isLeaf(intpos)const{ return(pos>=CurrentSize/2)&&(pos<CurrentSize);}template<classT>//建堆voidMinHeap<T>::BuildHeap(){ for(inti=CurrentSize/2-1;i>=0;i--)//反復(fù)調(diào)用篩選函數(shù)

SiftDown(i);}24/98堆的類定義和篩選法(4)template<classT>int

MinHeap<T>::leftchild(intpos)const{ return2*pos+1; //返回左孩子位置}template<classT>int

MinHeap<T>::rightchild(intpos)const{ return2*pos+2; //返回右孩子位置}template<classT>int

MinHeap<T>::parent(intpos)const{ return(pos-1)/2; //返回父結(jié)點(diǎn)位置}template<classT>bool

MinHeap<T>::Insert(constT&newNode){ //向堆中插入新元素newNode if(CurrentSize==MaxSize) returnFALSE;//堆空間已經(jīng)滿

heapArray[CurrentSize]=newNode;

SiftUp(CurrentSize); //向上調(diào)整

CurrentSize++; returnTRUE;}25/98堆的類定義和篩選法(5)template<classT>T&MinHeap<T>::RemoveMin() { //從堆頂刪除最小值

if(CurrentSize==0){

cout<<"Can'tDelete"; //調(diào)用RemoveMin之前，需要判斷堆非空

exit(1); } else{ swap(0,--CurrentSize); //交換堆頂和最后一個(gè)元素

if(CurrentSize>1)SiftDown(0);//從堆頂開始篩選

returnheapArray[CurrentSize]; }}template<classT>bool

MinHeap<T>::Remove(intpos,T&node){ //刪除給定下標(biāo)的元素

if((pos<0)||(pos>=CurrentSize))returnfalse; node=heapArray[pos];

heapArray[pos]=heapArray[--CurrentSize]; //用最后的元素值替代刪除位置的元素

if(heapArray[parent(pos)]>heapArray[pos])

SiftUp(pos); //當(dāng)前元素小于父結(jié)點(diǎn)，需要上升調(diào)整

elseSiftDown(pos); //當(dāng)前元素大于父結(jié)點(diǎn)，向下篩

returntrue;}26/98堆的類定義和篩選法(6)template<classT>voidMinHeap<T>::SiftUp(intposition){ //從position向上開始調(diào)整

int

temppos=position; Ttemp=heapArray[temppos]; while((temppos>0)&&(heapArray[parent(temppos)]>temp)){

heapArray[temppos]=heapArray[parent(temppos)];

temppos=parent(temppos); }

heapArray[temppos]=temp;}27/98堆的類定義和篩選法(7)template<classT>voidMinHeap<T>::SiftDown(intleft){

inti=left; //標(biāo)識(shí)父結(jié)點(diǎn)

intj=leftchild(i); //標(biāo)識(shí)關(guān)鍵值較小的子結(jié)點(diǎn)

Ttemp=heapArray[i]; //保存父結(jié)點(diǎn)

while(j<CurrentSize){ //過篩

if((j<CurrentSize-1)&&(heapArray[j]>heapArray[j+1]))//若有右子節(jié)點(diǎn)，且小于左子節(jié)點(diǎn) j++; //j指向右子結(jié)點(diǎn)

if(temp>heapArray[j]){//若父節(jié)點(diǎn)大于子節(jié)點(diǎn)的值則交換位置

heapArray[i]=heapArray[j]; i=j; j=leftchild(j);

} elsebreak;//堆序滿足，跳出 }

heapArray[i]=temp; }28/98建堆效率對(duì)于n個(gè)結(jié)點(diǎn)的堆，其對(duì)應(yīng)的完全二叉樹的層數(shù)為logn。設(shè)i表示二叉樹的層編號(hào)，則第i層上的結(jié)點(diǎn)數(shù)最