數(shù)據(jù)結構之樹形結構2_堆

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

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

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

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

5、/2+1,n/2+2,.,2,1建堆的時間復雜度為詳細證明見算法導論第77頁，或者算法分析與設計第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號節(jié)點(下標為i)為根的子樹調(diào)整為堆，n為堆最后一個節(jié)點的下標(也就是數(shù)組的長度)/k表示當前節(jié)點孩子的下標/找出值最小的孩子的下標/把值最小的孩子的值賦值

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

8、點移動至頂部，調(diào)整此堆跳轉至2步驟，直至堆為空堆排序選擇與維出堆頂節(jié)點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中學高一年級總共有n(n=500000)個學生。現(xiàn)在你有他們的“星際語”成績單，要從中找出“星際語”成績最好的m(m=1000并且mn)個學生組成宇宙班，請按由高到低的順序打印出加入于周班學生的“星際語”成績。輸入格式：第一行，兩個整數(shù)n和m第二行，n個用空格間隔的整數(shù)，分別表示n個學生的“星際語”成績輸出格式：只有一行，m個空格間隔的整數(shù)，表示加入宇宙班學生的“星際語”成績。樣例輸入：12 5

10、89 87 77 95 68 56 100 80 65 95 99 71樣例輸出：100 99 95 95 89直接對n個數(shù)由大到小排序，然后取最大的m個數(shù)取出來，時間復雜度：普通排序(冒泡、選擇、插入)：O(n2+m) /一定超時快速排序:O(nlog2n+m)有沒有更快的方法？1.把n個數(shù)字建成堆2.把堆頂節(jié)點的打印出來，刪除堆頂元素，調(diào)整堆。 第2步重復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記錄值最大的孩子的編號（大根堆） 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個數(shù)字 for(i=1;i=m;i+) printf(%d ,heap1); /打印堆頂元素的值，即取出最大元素 heap1=heapn; /把最后一個節(jié)點移到堆頂，相

12、當于把原來堆頂節(jié)點刪了 n-; /刪除堆頂節(jié)點后，總節(jié)點數(shù)減1 shift(1,n); /重新調(diào)整堆，把剩余節(jié)點中最大的值調(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) /從編號為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) /從編號為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;特點： 不穩(wěn)定 時間復雜度最壞情況下不超過 o(nlog2n)課后練手：何老板撿鉆石題目描述： “歡迎來安哥拉觀光，運氣好能撿到鉆石，運氣不好就踩中地雷，看了這則旅游廣告，何老板決定去安哥拉碰碰運氣。到了安哥拉才發(fā)現(xiàn)有個坑爹的規(guī)定：游客最多只能帶走n顆鉆石，否則就視為走私。 何老板運氣很好，他很快就搜集齊了n顆鉆石，他把它們編號1到n放進了箱子。在回機場的路上，何老板發(fā)現(xiàn)路邊還可以零星的撿到一些鉆石。沿路何老板總共發(fā)現(xiàn)了m顆鉆石，他把它們編號為n+1到n+m。何老板是個聰明人，他只會帶走較重的鉆石，如果撿起的鉆石比箱子里的都要輕，何老板就

15、直接把它扔掉，否則他就把箱子中最輕的鉆石扔了，把新?lián)斓姆胚M箱子。請問何老板沿途把哪些鉆石從箱子里扔了出去，請按先后順序打印出被扔出的鉆石的編號。（假定每顆鉆石的重量都不同，不超過int范圍）。輸入格式：第一行，兩個空格間隔的整數(shù)n和m，(n=20000,m=100000)第二行，n個空格間隔的整數(shù)，表示已裝到箱子中的n顆鉆石的重量第三行，m個空格間隔的整數(shù)，表示沿途撿到的m顆鉆石的重量輸出格式：只有一行：若干個空格間隔的整數(shù)，表示從箱子里扔出的鉆石的編號樣例輸入：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 對于一給定的素數(shù)集合 S = p1, p2, ., pK,考慮一個正整數(shù)集合，該集合中任一元素的質(zhì)因數(shù)全部屬于S。這個正整數(shù)集合包括，p1、p1*p2、p1*p1、p1*p2*p3.(還有其它)。該集合被稱為S集合的“丑數(shù)集合”。 對于輸入的集合S去尋找“丑數(shù)集合”中的第N小的“丑數(shù)”。樣例：4 19 /求第19個丑數(shù)2 3 5 7 /給定的S集合結果：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）為例：初始：建立一個小根堆，把數(shù)字1放入堆中；每次從堆中取出堆頂元素k，再把2k,3k, 5k, 7k放入堆中；從2開始，取出的第n個元素就是第n小的丑數(shù)；每取出一個數(shù)，插入4個數(shù)，因此任何堆里的元素是O(n)的，時間復雜度為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