數(shù)據(jù)結(jié)構(gòu)之樹形結(jié)構(gòu)2_堆

1、數(shù)據(jù)結(jié)構(gòu)之樹形結(jié)構(gòu)1.什么是樹？復(fù)習(xí)樹 樹是由n(n=0)個(gè)節(jié)點(diǎn)構(gòu)成集合。特點(diǎn)是任何兩個(gè)節(jié)點(diǎn)間有且僅有一條路徑。ABCDEGHFLJK根節(jié)點(diǎn)：沒有父親的節(jié)點(diǎn)。 一棵樹只有一個(gè)根節(jié)點(diǎn)。EKJA每個(gè)節(jié)點(diǎn)可有0個(gè)或多個(gè)兒子節(jié)點(diǎn)除根節(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且只有一個(gè)父親節(jié)點(diǎn)J和K是E的兒子節(jié)點(diǎn)E是J和K的父親節(jié)點(diǎn)A是E的父節(jié)點(diǎn)沒有兒子的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)，比如 F G H L J K 都是葉節(jié)點(diǎn)父親相同的節(jié)點(diǎn)稱為兄弟節(jié)點(diǎn)，比如 F G H 是兄弟節(jié)點(diǎn)的兒子的個(gè)數(shù)稱為節(jié)點(diǎn)的度，比如 A 的度數(shù)為4祖先、子孫包含一個(gè)節(jié)點(diǎn)的所有子孫和該節(jié)點(diǎn)本身的集合，稱為子樹復(fù)習(xí)1.什么是樹？2.什么是二叉樹？復(fù)習(xí)1.什么是樹？2.

2、什么是二叉樹？3.二叉樹第i層最多有多少個(gè)節(jié)點(diǎn)？復(fù)習(xí)1.什么是樹？2.什么是二叉樹？3.二叉樹第i層最多有多少個(gè)節(jié)點(diǎn)？4.高度為h的二叉樹最多有多少個(gè)節(jié)點(diǎn)？復(fù)習(xí)1.什么是樹？2.什么是二叉樹？3.二叉樹第i層最多有多少個(gè)節(jié)點(diǎn)？4.高度為h的二叉樹最多有多少個(gè)節(jié)點(diǎn)？5.二叉樹葉節(jié)點(diǎn)和度為2的節(jié)點(diǎn)的關(guān)系是？復(fù)習(xí)二叉樹（Binary tree）二叉樹就是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)子節(jié)點(diǎn)的樹。二叉樹的特點(diǎn)：1.第i層上最多有 個(gè)節(jié)點(diǎn)2.高度為h的二叉樹最多有 個(gè)節(jié)點(diǎn)2 2i-1i-12 2h h-1-13.在非空二叉樹中，葉節(jié)點(diǎn)的個(gè)數(shù)等于度為2的節(jié)點(diǎn)個(gè)數(shù)加1ABCGFJKLM復(fù)習(xí)6.什么是完全二叉樹？什么是

3、滿二叉樹？復(fù)習(xí)二叉樹每層節(jié)點(diǎn)數(shù)都達(dá)到最大的二叉樹樹叫滿二叉樹ABCGFJK滿二叉樹除最底層外，其余各層節(jié)點(diǎn)都達(dá)到最大值，且最底層的節(jié)點(diǎn)集中在左側(cè)的連續(xù)位置上的二叉樹叫完全二叉樹。ABCGFK完全二叉樹復(fù)習(xí)1835627寫出前序，中序，后續(xù)遍歷序列前順：1,8,5,3,6,7,2中序：8,5,1,7,6,2,3后續(xù)：5,8,7,2,6,3,1復(fù)習(xí)二叉堆(heap)二叉堆是完全二叉樹任何一個(gè)節(jié)點(diǎn)都大于他的兒子節(jié)點(diǎn)的值(大根堆) 或者任何一個(gè)節(jié)點(diǎn)都小于他的兒子節(jié)點(diǎn)的值(小根堆)父子，則堆頂元素值一定最大父1）/比如5號(hào)節(jié)點(diǎn)的父親是2號(hào)節(jié)點(diǎn)結(jié)點(diǎn)heapi左孩子是heap2*i，右孩子是heap2*i+

4、1 i=n/2根據(jù)堆的定義可以知道：對(duì)于大根堆：heap1最大heapih2*i且heapiheap2*i（1in / 2）大根堆heap數(shù)組下標(biāo)堆用一維數(shù)組來存儲(chǔ)，父子關(guān)系可通過數(shù)組下標(biāo)快速計(jì)算出來已知下列數(shù)組表示一個(gè)堆，請(qǐng)畫出這個(gè)堆！1238277266 4945下標(biāo) 1 2 3 4 5 6 7 81234567998定理：堆的高度最大為log2(n+1)因?yàn)楦叨葹閔的二叉樹最多有2h-1個(gè)節(jié)點(diǎn)。2h-1=n那么h=log2(n+1)怎樣建堆？(小根)3建堆開始6574231387715216 3613建堆完畢數(shù)組heap初始時(shí)n=11 數(shù)組下標(biāo)從第下標(biāo)為n/2的節(jié)點(diǎn)開始，依次討論下標(biāo)為n

5、/2+1,n/2+2,.,2,1建堆的時(shí)間復(fù)雜度為詳細(xì)證明見算法導(dǎo)論第77頁，或者算法分析與設(shè)計(jì)第74頁數(shù)組heap建堆完畢后1234567891011堆的向下調(diào)整(小根)void shift(int i,int n) int k,t; t=heapi; k=2*i; while(k=n) if(kheapk+1)k+; if(theapk) heapi=heapk; i=k; k=2*i; else break; heapi=t;/把以i號(hào)節(jié)點(diǎn)(下標(biāo)為i)為根的子樹調(diào)整為堆，n為堆最后一個(gè)節(jié)點(diǎn)的下標(biāo)(也就是數(shù)組的長(zhǎng)度)/k表示當(dāng)前節(jié)點(diǎn)孩子的下標(biāo)/找出值最小的孩子的下標(biāo)/把值最小的孩子的值賦值

6、給根/結(jié)束循環(huán)/把根的值賦值交換給孩子#define maxn 1000int heapmaxn;void shift(int i,int n) int k,t; t=heapi; k=2*i; while(k=n) if(kheapk+1)k+; if(theapk) heapi=heapk; i=k; k=2*i; else break; heapi=t;3655231387715216 36131234567891011堆的向下調(diào)整(小根)void shift(int i,int n) int k,t; t=heapi; k=2*i; while(k=n) if(kheapk+1)k+;

7、 if(theapk) heapi=heapk; i=k; k=2*i; else break; heapi=t;/把以i號(hào)節(jié)點(diǎn)(下標(biāo)為i)為根的子樹調(diào)整為堆，n為堆最后一個(gè)節(jié)點(diǎn)的下標(biāo)(也就是數(shù)組的長(zhǎng)度)/k表示當(dāng)前節(jié)點(diǎn)孩子的下標(biāo)/找出值最小的孩子的下標(biāo)/把值最小的孩子的值賦值給根/結(jié)束循環(huán)/把根的值賦值交換給孩子#define maxn 1000int heapmaxn;建堆： for(i=n/2;i=1;i-)shift(i,n);調(diào)整一次堆的時(shí)間復(fù)雜度在最壞情況下是堆排序堆排序的基礎(chǔ)選擇排序堆排序的實(shí)質(zhì)是利用二叉堆優(yōu)化選擇排序堆排序步驟：建堆。將所有節(jié)點(diǎn)布置成堆結(jié)構(gòu)取出堆頂節(jié)點(diǎn)把堆尾的節(jié)

8、點(diǎn)移動(dòng)至頂部，調(diào)整此堆跳轉(zhuǎn)至2步驟，直至堆為空堆排序選擇與維出堆頂節(jié)點(diǎn)7127 37288338 68一、取出 cout0) coutheap1; heap1=heapn-; shift(1,n);排序int heap100,t,j,n;void shift(int i,int n) int k,t; t=heapi; k=2*i; while(k=n) if(kheapk+1)k+; if(theapk) heapi=heapk;i=k; k=2*i; else break; heapi=t; int main() cinn; for(j=1;jheap j; fo

9、r(j=n/2; j=1;j-)shift(j,n); while(n0) coutheap1; heap1=heapn-; shift(1,n); return 0;例：NK宇宙班題目描述： CQNK中學(xué)高一年級(jí)總共有n(n=500000)個(gè)學(xué)生?，F(xiàn)在你有他們的“星際語”成績(jī)單，要從中找出“星際語”成績(jī)最好的m(m=1000并且mn)個(gè)學(xué)生組成宇宙班，請(qǐng)按由高到低的順序打印出加入于周班學(xué)生的“星際語”成績(jī)。輸入格式：第一行，兩個(gè)整數(shù)n和m第二行，n個(gè)用空格間隔的整數(shù)，分別表示n個(gè)學(xué)生的“星際語”成績(jī)輸出格式：只有一行，m個(gè)空格間隔的整數(shù)，表示加入宇宙班學(xué)生的“星際語”成績(jī)。樣例輸入：12 5

10、89 87 77 95 68 56 100 80 65 95 99 71樣例輸出：100 99 95 95 89直接對(duì)n個(gè)數(shù)由大到小排序，然后取最大的m個(gè)數(shù)取出來，時(shí)間復(fù)雜度：普通排序(冒泡、選擇、插入)：O(n2+m) /一定超時(shí)快速排序:O(nlog2n+m)有沒有更快的方法？1.把n個(gè)數(shù)字建成堆2.把堆頂節(jié)點(diǎn)的打印出來，刪除堆頂元素，調(diào)整堆。 第2步重復(fù)m次。n最大為500000，219=524288,也就是log2n的值不超過19#define maxn 500001using namespace std;int heapmaxn,n,m;void shift(int i,int le

11、n) /調(diào)整成大根堆 int t=heapi,k=2*i; while(k=len) if(klen)&(heapkheapk+1)k+; /k記錄值最大的孩子的編號(hào)（大根堆） if(theapk) heapi=heapk; i=k; k=2*i; else break; heapi=t;int main() int i; scanf(%d%d,&n,&m); for(i=1;i=1;i-)shift(i,n); /選出最大的m個(gè)數(shù)字 for(i=1;i=m;i+) printf(%d ,heap1); /打印堆頂元素的值，即取出最大元素 heap1=heapn; /把最后一個(gè)節(jié)點(diǎn)移到堆頂，相

12、當(dāng)于把原來堆頂節(jié)點(diǎn)刪了 n-; /刪除堆頂節(jié)點(diǎn)后，總節(jié)點(diǎn)數(shù)減1 shift(1,n); /重新調(diào)整堆，把剩余節(jié)點(diǎn)中最大的值調(diào)到堆頂 return 0;堆的操作/堆的向下調(diào)整void ShiftDown(int i,int n) int k,t; t=heapi; k=2*i; while(k=n) if(kheapk+1)k+; if(theapk) heapi=heapk;i=k; k=2*i; else break; heapi=t;/刪除堆頂元素void Del( ) Heap1=Heapn; n-; if(n0)ShiftDown(1,n);/添加值為x的元素void Insert(

13、int x ) n+; Heapn=x; /將新元素添加在末尾 /向上調(diào)整堆/堆的向下調(diào)整void ShiftDown(int x,int n) /從編號(hào)為x的元素往下調(diào)整為小根堆 int k,t; t=heapx; k=2*x; while(k=n) if(kheapk+1)k+; if(theapk) heapx=heapk;x=k; k=2*x; else break; heapx=t;/堆的向上調(diào)整void ShiftUp(int x) /從編號(hào)為x的元素往上調(diào)整為小根堆 int t=Heapx,k=x/2; while(k0) if(tHeapk) Heapx=Heapk; x=k;

14、 k=k/2; else break; Heapx=t;特點(diǎn)： 不穩(wěn)定 時(shí)間復(fù)雜度最壞情況下不超過 o(nlog2n)課后練手：何老板撿鉆石題目描述： “歡迎來安哥拉觀光，運(yùn)氣好能撿到鉆石，運(yùn)氣不好就踩中地雷，看了這則旅游廣告，何老板決定去安哥拉碰碰運(yùn)氣。到了安哥拉才發(fā)現(xiàn)有個(gè)坑爹的規(guī)定：游客最多只能帶走n顆鉆石，否則就視為走私。 何老板運(yùn)氣很好，他很快就搜集齊了n顆鉆石，他把它們編號(hào)1到n放進(jìn)了箱子。在回機(jī)場(chǎng)的路上，何老板發(fā)現(xiàn)路邊還可以零星的撿到一些鉆石。沿路何老板總共發(fā)現(xiàn)了m顆鉆石，他把它們編號(hào)為n+1到n+m。何老板是個(gè)聰明人，他只會(huì)帶走較重的鉆石，如果撿起的鉆石比箱子里的都要輕，何老板就

15、直接把它扔掉，否則他就把箱子中最輕的鉆石扔了，把新?lián)斓姆胚M(jìn)箱子。請(qǐng)問何老板沿途把哪些鉆石從箱子里扔了出去，請(qǐng)按先后順序打印出被扔出的鉆石的編號(hào)。（假定每顆鉆石的重量都不同，不超過int范圍）。輸入格式：第一行，兩個(gè)空格間隔的整數(shù)n和m，(n=20000,m=100000)第二行，n個(gè)空格間隔的整數(shù)，表示已裝到箱子中的n顆鉆石的重量第三行，m個(gè)空格間隔的整數(shù)，表示沿途撿到的m顆鉆石的重量輸出格式：只有一行：若干個(gè)空格間隔的整數(shù)，表示從箱子里扔出的鉆石的編號(hào)樣例輸入：5 58 5 9 3 74 2 1 15 8樣例輸出：4 6 2int main() . scanf(%d%d,&n,&m); fo

16、r(i=1;i=1;i-) ShiftDown(i,n); x=n+m; for(i=n+1;iheap1) printf(%d ,number1); heap1=heapi; number1=numberi; ShiftDown(1,n); .void ShiftDown(int i,int n) . t=heapi; y=numberi; k=i*2; while(k=n) if(kheapk+1)k+; if(theapk) heapi=heapk; numberi=numberk; i=k; k=2*i; else break; heapi=t; numberi=y; .課后作業(yè)：18

17、21 對(duì)于一給定的素?cái)?shù)集合 S = p1, p2, ., pK,考慮一個(gè)正整數(shù)集合，該集合中任一元素的質(zhì)因數(shù)全部屬于S。這個(gè)正整數(shù)集合包括，p1、p1*p2、p1*p1、p1*p2*p3.(還有其它)。該集合被稱為S集合的“丑數(shù)集合”。 對(duì)于輸入的集合S去尋找“丑數(shù)集合”中的第N小的“丑數(shù)”。樣例：4 19 /求第19個(gè)丑數(shù)2 3 5 7 /給定的S集合結(jié)果：2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27以樣例數(shù)據(jù)（2 3 5 7）為例：初始：建立一個(gè)小根堆，把數(shù)字1放入堆中；每次從堆中取出堆頂元素k，再把2k,3k, 5k, 7k放入堆中；從2開始，取出的第n個(gè)元素就是第n小的丑數(shù)；每取出一個(gè)數(shù)，插入4個(gè)數(shù)，因此任何堆里的元素是O(n)的，時(shí)間復(fù)雜度為O(4nlogn)上述解法有沒有問題呢？產(chǎn)生了相同的數(shù)字怎么處理？比如2*3,和3*2 main( ). long long i,k,x,m,tmp,cnt=0; scanf(%I64d%I64d,&k,&m); for(i