第八章堆积【PPT课件】

2020-11-17 12:22:35 本页面

【导读】堆積是樹結構的第三種型態。其左右子樹節點的值均較其父母節點的值小。值保證是該樹最大值。這中堆績稱為最大堆績。樹俱有相同的性質。堆積還有一個有趣的特性,就是以陣列實作較以連結串列實。當以陣列實作堆積時,已知父母節點的註標。為2*i+1,右子樹節點的註標為2*i+2。一棵堆積是一棵二元樹,俱備下列的特性:。完整的二元樹指其葉節點相差在一個層次以內。在上圖的兄弟節點裡,左節點有大於右節點者,節說明過的二元搜尋樹是不允許的。對於堆積有兩個基本的操作:插入一個節。點以及移除一個節點。假想我們有一個N個元素的接近完整二元樹,其。位置,使整個結構成為一個堆積。上圖新元素26插入原來已成堆積的樹。元素規定要擺在最右邊的。雖然堆積可以透過動態樹結構建立起來,但最常見的還是。以陣列實作為宜。右子女節點註標為k,左子女節點註標為k-1。這種結構就命名為heapTag結構。需要提供兩個引數,第一個是最大容量之元

文章介绍图

  

【正文】 第八章堆積
•堆積(heap)是樹結構的第三種型態。堆積是一棵二元樹,
其左右子樹節點的值均較其父母節點的值小。堆積的根節點
值保證是該樹最大值。這中堆績稱為最大堆績。堆積的子樹
可擺在左邊當左子樹,也可擺在右邊當右子樹,因此左右子
樹俱有相同的性質。
•堆積還有一個有趣的特性,就是以陣列實作較以連結串列實
作佳。當以陣列實作堆積時,已知父母節點的註標
(subscript)就可算出其左右子樹節點的註標,反之亦然。
•若父母節點的註標i從0開始計數時,則左子樹節點的註標
為2*i+1,右子樹節點的註標為2*i+2。
•若父母節點的註標i從1開始計數時,則左子樹節點的註標
為2*i,右子樹節點的註標為2*i+1。
•已知子女節點的註標也可算出其父母節點的註標,因此處理
的效率相當高。
基本觀念
•一棵堆積是一棵二元樹,俱備下列的特性:
•1.這棵樹是一棵完整或接近完整的二元樹。
•2.每一節點的鍵值大於或等於其子樹節點鍵值。
•一棵完整的二元樹是每一層次(level)都佔滿,一棵接近
完整的二元樹指其葉節點相差在一個層次以內。堆積如下
圖所示。
三種堆積舉例
•在上圖的兄弟節點裡,左節點有大於右節點者(13>9),
左節點有小於右節點者(7<11,19<24),這對於前面章
節說明過的二元搜尋樹是不允許的。注意上圖(c)是一
棵接近完整的二元樹,第二層次是從左而右填滿的,這也
是堆積的要求。
堆積有兩個基本的操作
•對於堆積有兩個基本的操作:插入一個節
點以及移除一個節點。雖然堆積是一棵樹,
但對它執行遍訪、搜尋、列印的操作並無
意義。要實作堆積的插入及移除節點操作,
我們需要兩個演算法,再堆上(reheapup)
以及再堆下(reheapdown)。
再堆上作業
•假想我們有一個N個元素的接近完整二元樹,其
前面的N-1個元素均已滿足堆積的要求,但最後
一個元素N卻不滿足堆積,換句話說只要第N個
元素滿足堆積的要求,整個結構就是一個堆積了。
再堆上作業將第N個元素往上堆,定位於正確的
位置,使整個結構成為一個堆積。
26往上移動
•上圖新元素26插入原來已成堆積的樹。最後的
元素規定要擺在最右邊的。26比它的父母節點
13還大,違反堆積的規定,必須互換,因此就往
上移動,如下圖所示。
26再往上移動
•26比它的父母節點43還小,就不必再移
動,已經定到正確的位置了。這種再堆上
使成堆積的作業稱為再堆上操作。
再堆下
作業
•再堆下
作業事
實上是
再堆上
的相反
操作。
舉例如
下圖。
堆積實作
•雖然堆積可以透過動態樹結構建立起來,但最常見的還是
以陣列實作為宜。一個節點與其子女節點的關係可以計算
出來,如下所述:
•1.若節點註標為i(從0算起),則其子女節點的註標計算
•如下:
•a).左子女節點註標為2*i+1
•b).右子女節點註標為2*i+2
•2.若節點註標為i(從0算起),則其父母節點的註標計算
•如下:取(i-1)/2之整數部份。
•3.左子女節點註標為j,右子女節點註標為j+1。
•右子女節點註標為k,左子女節點註標為k-1。
•4.設完整堆積元素數為n,第一個葉節點為(n/2)之整數
部份。最後的枝節點註標為(n/2)-1之整數部份。
堆積以樹及陣列表示
•1.33的註標為2(從0算
起),左子女節點24註標
為2*2+1=5,右子女節點
20註標為2*2+2=6。
•2.9的註標為4(從0算
起),其父母節點57的註
標為(4-1)/2整數部份為
1。
•3.總共有7個元素
(n=7),第一個葉節點為
7/2整數部份為3。
•4.最後的枝節點33註標
為(n/2)-1=(7/2)-1=2。
堆積結構
•structheapTag
•{
•void**data;
•intlast;
•intsize;
•int(*pare)(void*arg1,void*arg2);
•intmaxsize;
•};
data指標變數的含意
•這種結構就命名為heapTag結構。請注意data
是void不定型態指標的指標,也就是說傳給此結
構的資料本身是一個位址,此位址存於指標變數
*data裡頭,此*data欄的位址卻存於**data指
標變數裡頭,如下圖所示。
•structheapTag*heapCreate(intmaxsize,
•int(*pare)(void*arg1,void*arg2))
•{
•structheapTag*heap;
•heap=malloc(sizeof(structheapTag));
•if(heap==NULL)
•returnNULL;
•heap->last=-1;
•heap->size=0;
•heap->pare=pare;
•heap->maxsize=(int)pow(2,ceil(log2(maxsize)))-1;
•heap->data=(void*)calloc(
•heap->maxsize,sizeof(void*));
•returnheap;
•}
建立
堆積結構
建立堆積結構
•需要提供兩個引數,第一個是最大容量之元
素個數maxsize,第二個是比較的函式名稱
pare。首先取得一塊heapTag結構的
heap記憶體,設定heap->last為-1,heap-
>size為0,heap->mazsize最大容量為2的
log10(maxsize)/log10(2)次方值再減一,例
如mazsize引數值為16,那麼heap-
>maxsize的值為2的4次方再減一,為7。
建立堆積結構
•intheapInsert(structheapTag*heap,void*dataptr)
•{
•if(heap->size==0)
•{
•heap->size=1;
•heap->last=0;
•heap->data[heap->last]=dataptr;
•return1;
•}
•if(heap->last==heap->maxsize-1)
•return0;
•++(heap->last);
•++(heap->size);
•heap->data[heap->last]=dataptr;
•ReheapUp(heap,heap->last);
•return1;
•}插入堆積
•voidReheapUp(structheapTag*heap,intchild)
•{
•intparent;
•void**data,**temp;
•if(child!=0)
•{
•data=heap->data;
•parent=(child-1)/2;
•if(heap->pare(data[child],data[parent])>0)
•{
•temp=data[parent];data[parent]=data[child];
•data[child]=temp;ReheapUp(heap,parent);
•}
•}
•return;
•}
從堆積移除節點
•intheapRemove(structheapTag*heap,void**dataptr)
•{
•if(heap->size==0)
•return0;
•*dataptr=heap->data[0];
•heap->data[0]=heap->data[heap->last];
•(heap->last)--;
•(heap->size)--;
•ReheapDown(heap,0);
•return1;
•}
從堆積移除節點
•從堆積heap裡移除資料*dataptr所指的節點,
該指標為資料陣列第零個元素的位址,即heap-
>data[0],它是堆積裡最大值者,然後將最後的元
素移到陣列第零個元素的位址,進行
ReheapDown()再堆下作業,使滿足堆積的要求。
ReheapDown()再堆下函式屬於遞迴函式,一層
一層往下堆積,直到最後一個元素那一層時才停
止。最後將last及size成員值均減一。傳回1值。
若size成員值已達0值則傳回0值。
測試程式
•上面說明的堆積結構宣告以及相關的函式存入
表頭檔備用。
•下列的程式用於測試表頭檔的函
式是否正確無誤。首先建立一個heap堆積,最
大元素個數為16,資料比較函式名稱為
pareInt。
•structheapTag*heap;
•heap=heapCreate(16,pareInt);
•執行時從整數陣列k[]依序輸入下列的數字。
•924451321531519
依序插入9,24,45,13,21時之堆積
依序插入53,15時之堆積
依序插入19時之堆積及陣列
根節點為第0個元素,其值為
53最大,它的左子樹在第1個
位置,其值為21,它的右子樹
在第2個位置,其值為45。
節點21在第1個位置,左子
樹在第2*1+1=3個位置,其值
為19,右子樹在第2*1+2=4
個位置,其值為13。
節點45在第2個位置,左子
樹在第2*2+1=5個位置,其值
為24,右子樹在第2*2+2=6
個位置,其值為15。
節點19在第3個位置,左子
樹在第2*3+1=7個位置,其值
為9,沒有右子樹。
優先佇列
•許多出國旅遊的人在機場登機時,常看到
機組員最先登機,然後持有貴賓卡的人登
機,然後孕婦或帶嬰兒的人登機,最後才
是一般乘客登機,很顯然因為身份的不同,
處理的方式也不同,某些人要優先處理。
•就以這四類的人員說明。設機組員的優先
碼為4,貴賓優先碼為3,孕婦優先碼為2,
一般乘客優先碼為1。登機時機組員佇列在
最前面,然後為貴賓佇列,其後為孕婦佇
列,最後才是一般乘客佇列。
優先佇列
•我們使用電腦來模擬,
若每一個人有一個識
別碼,一般是護照號
碼或身份證字號,還
有一個優先碼,這四
類的人有先來後到的,
若輸入檔案的內容如
下:
1011
1033
1044
2044
2022
2033
2011
3011
3044
3022
3033
第一個欄位為識
別碼,為了簡單
起見識別碼採用
三位數字,第二
欄為優先碼,一
位數字1~4,
優先碼4最優先。
優先佇列
•現在我們要從中選出各類人員,各自獨立一個佇
列如下:

•機組員貴賓孕婦一般乘客
•------------------------
•1044103320221011
•2044203330222011
•304430333011
優先佇列
•第一個登機的給順號
999,第二個登機的
給順號998,逐次遞
減,此順號配合優先
碼,構成一個序號
serial,由「優先碼.
順號」組成,因此輸
入檔讀
入的資料經電腦編成
序號如下:
序號
10111999
10333998
10444997
20444996
20222995
20333994
20111993
30111992
30444991
30222990
30333989
就以此序號當堆
積資料比較的基
礎。每一類別人
員建立一個如下
的資料結構
custNodeTag。
優先佇列
•就以此序號當堆積資料比較的基礎。每一類別人
員建立一個如下的資料結構custNodeTag。
•structcustNodeTag
•{
•intid;
•intpriority;
•intserial;
•};
•其中id成員為人員識別碼,priority為優先碼,
serial為序號。所建立的堆積如下圖所示。
登機人員所建立的堆積
登機人員所建立的heap堆積
•登機人員所建立的heap堆積,在根節點序
號4997是堆積裡頭最大的,他的優先碼為
4,屬於最優先的一群。移除4997節點後,
4996次大值變成新的根節點,接著移除,
第三大值的4991變成新的根節點,如此循
序移除,直到沒有節點為止,移除的節點
資料除了顯示在螢幕之外,還輸出至
本文檔。
登機人員所建立的heap堆積輸出如下
•idpriorityserial
•10444997
•20444996
•30444991
•10333998
•20333994
•30333989
•20222995
•30222990
•10111999
•20111993
•30111992
最小堆積
•前面所處理的堆積為內定的最大堆積,若
要建立最小堆積又如何?只要修改再堆上
ReheapUp()及再堆下ReheapDown()這
兩個函式就行,修改如下:
•voidReheapUp(structheapTag*heap,intchild)
•{
•intparent;
•void**data,*temp;
•if(child!=0)
•{
•data=heap->data;
•parent=(child-1)/2;
•if(heap->pare(data[child],data[parent])<0)
•{
•temp=data[parent];data[parent]=data[child];
•data[child]=temp;ReheapUp(heap,parent);
•}
•}
•return;
•}
/*exchange*/
/*whenchild*/
/*<parent*/
最小堆積
•修改成子女節點之較小者,比父母節點小時,互
換其值,小者往上升或往下降。
•修改後的檔案改名為表頭檔
備用。
•下列程式用於測試是否正
確。執行時依序從整數k[]陣列取得下列資料建立
heap最小堆積,輸入資料如下:
•924451321531519
•所建立的堆積如下圖所示。
最小堆積
•執行時依序從整數k[]陣列取得下列資料建立heap最小
堆積,輸入資料如下:
•924451321531519
点击复制文档内容
教学课件相关推荐
文库吧 www.wenkub.com
备案图鄂ICP备17016276号-1