1、NOIP普與講座堆與其應用NOIP普與講座堆與其應用01020304Table of Contents內容大綱內容大綱NOIP普與講座堆與其應用預備知識 完全二叉樹：完全二叉樹：如果一棵深度為如果一棵深度為K K的二叉樹，的二叉樹，1 1至至K-1K-1層層的結點都是滿的，即滿足的結點都是滿的，即滿足2 2i-1i-1(1=i=k-1),(1=i=k-1),只有最下面的一層的結點數小于等于只有最下面的一層的結點數小于等于2 2k-1k-1，并且最下面一層的結點都集中在該層最左并且最下面一層的結點都集中在該層最左邊的若干位置，則此二叉樹稱為完全二叉邊的若干位置，則此二叉樹稱為完全二叉樹。樹。NO

2、IP普與講座堆與其應用預備知識1 12 23 34 45 56 67 7滿二叉樹滿二叉樹1 12 23 34 45 5完全二叉樹完全二叉樹NOIP普與講座堆與其應用堆的定義 堆也稱二叉堆，結構上是一種數組，本質堆也稱二叉堆，結構上是一種數組，本質上是一棵完全二叉樹。樹中每個結點與數上是一棵完全二叉樹。樹中每個結點與數組中存放該結點中值的那個元素相對應。組中存放該結點中值的那個元素相對應。NOIP普與講座堆與其應用堆的性質 樹根為樹根為A1A1，利用完全二叉樹的性質，可，利用完全二叉樹的性質，可以求出第以求出第i i個結點的父結點、左孩子結點、個結點的父結點、左孩子結點、右孩子結點的下標分別為：

3、右孩子結點的下標分別為：trunc(i/2)trunc(i/2)、2i2i、2i+12i+1。NOIP普與講座堆與其應用堆的性質 二叉堆還具有這樣一個重要的性質：對除根以外二叉堆還具有這樣一個重要的性質：對除根以外的每個結點的每個結點i i，Aparent(i)AiAparent(i)Ai，即所有結，即所有結點的值都不得超過其父結點的值，稱為大根堆。點的值都不得超過其父結點的值，稱為大根堆。小根堆就是要求：小根堆就是要求：Aparent(i)Ai Aparent(i)Ai 。NOIP普與講座堆與其應用堆的基本操作 使用堆的關鍵部分是兩個基本操作：使用堆的關鍵部分是兩個基本操作：PutPut操作

4、：即往堆中加入一個結點。操作：即往堆中加入一個結點。方法是往堆尾加入一個結點，并通過從下往方法是往堆尾加入一個結點，并通過從下往上的調整法，使其繼續保持堆的性質；上的調整法，使其繼續保持堆的性質；GetGet操作：即從堆中取出根結點。操作：即從堆中取出根結點。方法是從堆中取出堆頭結點，并刪除該結點方法是從堆中取出堆頭結點，并刪除該結點( (堆尾覆蓋堆尾覆蓋) )，再通過從上往下的調整法，使其繼，再通過從上往下的調整法，使其繼續保持堆的性質；續保持堆的性質； NOIP普與講座堆與其應用Put操作575644321142564375heapheapNOIP普與講座堆與其應用Put操作1425643

5、7557561443211425643751heapheapNOIP普與講座堆與其應用Put操作14256437515756144321heapheap1425143756sonsonNOIP普與講座堆與其應用Put操作14251437565751644321heapheap1125443756sonsonNOIP普與講座堆與其應用Put操作11254437565754614321heapheapsonsonNOIP普與講座堆與其應用Put操作procedure put(x:longint);procedure put(x:longint);var fa,son,tmp:longint;var

6、 fa,son,tmp:longint;beginbegin len:=len+1; heaplen:=x; son:=len; len:=len+1; heaplen:=x; son:=len; while (son1) and (heapson div 2heapson) do while (son1) and (heapson div 2heapson) do begin begin temp:=heapson div 2; temp:=heapson div 2; heapson div 2:=heapson; heapson div 2:=heapson; heapson:=temp

7、; heapson:=temp; son:=son div 2; son:=son div 2; end; end;end;end;NOIP普與講座堆與其應用Put操作void put(int x)void put(int x) int fa,son,tmp;int fa,son,tmp;len+;len+;heaplen=x;heaplen=x;son=len;son=len;while (son!=1 & heapson/2heapson)while (son!=1 & heapson/2heapson) tmp=heapson/2;tmp=heapson/2;heapson/2=heap

8、son;heapson/2=heapson;heapson=tmp;heapson=tmp;son=son/2;son=son/2; NOIP普與講座堆與其應用Get操作11254437565754614321heapheapNOIP普與講座堆與其應用Get操作11254437565754614321heapheap612544375NOIP普與講座堆與其應用Get操作612544375575414326heapheap162544375papaNOIP普與講座堆與其應用Get操作162544375575464321heapheap142564375papaNOIP普與講座堆與其應用Get操作

9、142564375575644321heapheappapafunction get:longint;function get:longint;var pa,son,tmp:longint;var pa,son,tmp:longint;beginbegin get:=heap1; heap1:=heaplen; len:=len-1; pa:=1; get:=heap1; heap1:=heaplen; len:=len-1; pa:=1; while pa while pa* *2=len do2len) or (heappa2+1len) or (heappa* *2heappa2heap

10、son if heappaheapson then begin then begin tmp:=heappa; heappa:=heapson; tmp:=heappa; heappa:=heapson; heapson:=tmp; pa:=son; heapson:=tmp; pa:=son; end end else break; else break; end; end;end;end;int get()int get() int p=heap1,pa=1,son,tmp;int p=heap1,pa=1,son,tmp;heap1=heaplen;heap1=heaplen;len-;

11、len-;while (pawhile (pa* *2=len)2len | heappa2+1len | heappa* *2heappa2heapson)if (heappaheapson) tmp=heappa;tmp=heappa;heappa=heapson;heappa=heapson;heapson=tmp;heapson=tmp;pa=son;pa=son; else return p;else return p; return p;return p; NOIP普與講座堆與其應用建立堆 方法一：對數組中的每個數依次進行插入操作方法一：對數組中的每個數依次進行插入操作; ; Pa

12、scal: Pascal:for i:=1 to n do read(ai);for i:=1 to n do read(ai); for i:=1 to n do put(ai);for i:=1 to n do put(ai); C+: C+:for (int i=1;iai;for (int i=1;iai; for (int i=1;i=n;i+) put(ai);for (int i=1;i=n;i+) put(ai); 方法二：直接對數組方法二：直接對數組a a進行調整，從進行調整，從an div 2an div 2開始向下調整成堆，然后對開始向下調整成堆，然后對an div 2-

13、1an div 2-1調整調整, ,直至直至a1a1。NOIP普與講座堆與其應用堆的應用例例1 1、堆排序、堆排序 假設假設n n個隨機整數存放在個隨機整數存放在A1.nA1.n中，我們可以利用堆將中，我們可以利用堆將它們從小到大進行排序，這種排序方法，稱為它們從小到大進行排序，這種排序方法，稱為“堆排序堆排序”。【問題分析問題分析】(1) (1) 建立小根堆建立小根堆(2) (2) 取出根結點并調整堆：將根結點輸出，并與小根堆的最取出根結點并調整堆：將根結點輸出，并與小根堆的最后一個結點交換，再從上到下進行調整，使其仍為小根堆，后一個結點交換，再從上到下進行調整，使其仍為小根堆，重復重復(2

14、)(2)操作，最后輸出數組。操作，最后輸出數組。Pascal:Pascal:for i:=1 to n do writeln(get);for i:=1 to n do writeln(get);C+:C+:for (int i=1;i=n;i+) coutget()endl;for (int i=1;i=n;i+) coutget()endl;NOIP普與講座堆與其應用堆的應用【小結小結】 堆排序在數據較少時并不值得提倡，但數據堆排序在數據較少時并不值得提倡，但數據量很大時，效率就會很高。因為其運算的時間主量很大時，效率就會很高。因為其運算的時間主要消耗在建立初始堆和調整過程中，堆排序的時要

15、消耗在建立初始堆和調整過程中，堆排序的時間復雜度為間復雜度為O O（nlognlog2 2n n），而且堆排序只需一個供），而且堆排序只需一個供交換用的輔助單元空間，是一種不穩定的排序方交換用的輔助單元空間，是一種不穩定的排序方法。法。NOIP普與講座堆與其應用堆的應用例例2 2、丑數（、丑數（H H數）數） 丑數是指素因子都在集合丑數是指素因子都在集合22，3 3，5 5，77的數，的數，求第求第n n大的丑數大的丑數(n6000) (n6000) ，第一個丑數是，第一個丑數是1 1。【問題分析問題分析】窮舉顯然不行，嘗試用窮舉顯然不行，嘗試用“構造法構造法”不斷生成丑數；不斷生成丑數；構造

16、的基本思想：構造的基本思想：5 5個線性表，時間復雜度個線性表，時間復雜度O(n2)O(n2)其中的關鍵操作：取最小結點、插入新結點；其中的關鍵操作：取最小結點、插入新結點；可以利用二叉堆可以利用二叉堆( (小根堆小根堆) )的基本操作。的基本操作。NOIP普與講座堆與其應用堆的應用readln(n);readln(n);heap1:=1; len:=1;heap1:=1; len:=1;i:=0; k1:=0; k2:=0;i:=0; k1:=0; k2:=0;while in dowhile in dobeginbegin k1:=k2; k2:=get; k1:=k2; k2:=get;

17、 if k1k2 if k1k2 then begin then begin i:=i+1; i:=i+1; put(k2 put(k2* *2); put(k22); put(k2* *3);3); put(k2 put(k2* *5); put(k25); put(k2* *7);7); end; end;end;end;writeln(k2);writeln(k2);判斷前后兩次取出的數是否一樣把生成的新數加入到堆中NOIP普與講座堆與其應用堆的應用cinn;cinn;heap1=1; len=1;heap1=1; len=1;while (in)while (in) k1=k2; k2

18、=get();k1=k2; k2=get();if (k1!=k2)if (k1!=k2) i+;i+;put(k2put(k2* *2);2);put(k2put(k2* *3);3);put(k2put(k2* *5);5);put(k2put(k2* *7);7); coutk2endl;coutk2endl;判斷前后兩次取出的數是否一樣把生成的新數加入到堆中NOIP普與講座堆與其應用堆的應用例例3 3、合并果子（、合并果子（NOIP2004NOIP2004高中組第高中組第2 2題）題）【問題描述問題描述】fruit.?(pas,c,c+)fruit.?(pas,c,c+) 在一個果園里

19、，多多已經將所有的果子打了在一個果園里，多多已經將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。多多決定把所有的果子合成一堆。 每一次合并，多多可以把兩堆果子合并到一每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。可以起，消耗的體力等于兩堆果子的重量之和。可以看出，所有的果子經過看出，所有的果子經過n-1n-1次合并之后，就只剩下次合并之后，就只剩下一堆了。多多在合并果子時總共消耗的體力等于一堆了。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。每次合并所耗體力之和。NOIP普與講座堆與其應用堆的應用因為還要花大力氣把這些果子搬回家，所以多因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節省體力。假定每個多在合并果子時要盡可能地節省體力。假定每個果子重量都為果子重量都為1 1，并且已知果子的種類數和每種果，并且已知果子的種類數和每種果子的數目，你的任務是設計出合并的次序方案，子的數目，你的任務是設計出合并的次序方案，使多多耗費的體力最少，并輸出這個最小的體力使多多耗費的體力最少，