數(shù)據(jù)結構與算法-堆與優(yōu)先隊列

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

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

為了保持堆的性質(zhì)，沿著其后繼節(jié)點的路徑，自上而下依次比較和交換該節(jié)點與字節(jié)點的位置，直到重新滿足堆的性質(zhì)位置10/98堆的建立（初始化）建堆過程：首先將所有關鍵碼放到一維數(shù)組中，這時形成的完全二叉樹并不具備最小堆的特性，但是僅包含葉子結點的子樹已經(jīng)是堆(即在有n個結點的完全二叉樹中，當i>[n/2]-1時，以關鍵碼Ki為根的子樹已經(jīng)是堆)這時從含有內(nèi)部結點數(shù)最少的子樹（這種子樹在完全二叉樹的倒數(shù)第二層，此時i=[n/2]-1）開始，從右至左依次調(diào)整對這一層調(diào)整完成之后，繼續(xù)對上一層進行同樣的工作，直到整個過程到達樹根時，整棵完全二叉樹就成為一個堆了11/98例子：最小堆的建立對于關鍵碼集合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; //當前堆中元素數(shù)目

int

MaxSize; //堆所能容納的最大元素數(shù)目

voidswap(int

pos_x,int

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

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

MinHeap(const

intn); //構造函數(shù)，n表示堆的最大元素數(shù)目

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

bool

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

bool

isLeaf(intpos)const; //如果是葉結點，返回TRUE

int

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

int

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

int

parent(intpos)const; //返回父結點位置

bool

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

bool

Insert(constT&newNode); //向堆中插入新元素newNode T&RemoveMin(); //從堆頂刪除最小值 voidSiftUp(intposition); //從position向上開始調(diào)整，使序列成為堆 voidSiftDown(intleft); //向下篩選，參數(shù)left表示開始處理的數(shù)組下標};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();//此處進行堆元素的賦值工作}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--)//反復調(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; //返回父結點位置}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); //交換堆頂和最后一個元素

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

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

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

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

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

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

SiftUp(pos); //當前元素小于父結點，需要上升調(diào)整

elseSiftDown(pos); //當前元素大于父結點，向下篩

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; //標識父結點

intj=leftchild(i); //標識關鍵值較小的子結點

Ttemp=heapArray[i]; //保存父結點

while(j<CurrentSize){ //過篩

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

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

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

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

heapArray[i]=temp; }28/98建堆效率對于n個結點的堆，其對應的完全二叉樹的層數(shù)為logn。設i表示二叉樹的層編號，則第i層上的結點數(shù)最