第3章第3節(jié) 堆及其應(yīng)用(C++版)

1、第三節(jié)第三節(jié) 堆及其應(yīng)用堆及其應(yīng)用一、預(yù)備知識一、預(yù)備知識 完全二叉樹完全二叉樹： 如果一棵深度為K二叉樹，1至k-1層的結(jié)點都是滿的，即滿足2i-1，只有最下面的一層的結(jié)點數(shù)小于2i-1，并且最下面一層的結(jié)點都集中在該層最左邊的若干位置，則此二叉樹稱為完全二叉樹。二、堆的定義二、堆的定義 堆結(jié)構(gòu)是一種數(shù)組對象，它可以被視為一棵完全二叉樹。樹中每個結(jié)點與數(shù)組中存放該結(jié)點中值的那個元素相對應(yīng)，如下圖：三、堆的性質(zhì)三、堆的性質(zhì) 設(shè)數(shù)組A的長度為len，二叉樹的結(jié)點個數(shù)為size，sizelen，則Ai存儲二叉樹中編號為i的結(jié)點值（1isize），而Asize以后的元素并不屬于相應(yīng)的堆，樹的根為A1

2、，并且利用完全二叉樹的性質(zhì)，我們很容易求第i個結(jié)點的父結(jié)點（parent(i)）、左孩子結(jié)點(left(i)、右孩子結(jié)點(right(i)的下標(biāo)了,分別為：i/2、2i、2i+1； 更重要的是，堆具有這樣一個性質(zhì)，對除根以外的每個結(jié)點i，Aparent(i)Ai。即除根結(jié)點以外，所有結(jié)點的值都不得超過其父結(jié)點的值，這樣就推出，堆中的最大元素存放在根結(jié)點中，且每一結(jié)點的子樹中的結(jié)點值都小于等于該結(jié)點的值，這種堆又稱為“大根堆”；反之，對除根以外的每個結(jié)點i，Aparent(i)Ai的堆，稱為“小根堆”。四、堆的操作四、堆的操作用堆的關(guān)鍵部分是兩個操作：put操作，即往堆中加入一個元素；get操作

3、，即從堆中取出并刪除一個元素。 1、往堆中加入一個元素的算法(put)如下：（1）在堆尾加入一個元素，并把這個結(jié)點置為當(dāng)前結(jié)點。（2）比較當(dāng)前結(jié)點和它父結(jié)點的大小 如果當(dāng)前結(jié)點小于父結(jié)點，則交換它們的值，并把父結(jié)點置為當(dāng) 前結(jié)點。轉(zhuǎn)（2）。 如果當(dāng)前結(jié)點大于等于父結(jié)點，則轉(zhuǎn)（3）。（3）結(jié)束。 重復(fù)n次put操作，即可建立一個小根堆。我們舉一個例子看看具體過程：設(shè)n=10，10堆的數(shù)量分別為：3 5 1 7 6 4 2 5 4 1。 設(shè)一個堆結(jié)構(gòu)heap11,現(xiàn)在先考慮用put操作建一個小根堆，具體方法是每次讀入一個數(shù)插入到堆尾，再通過調(diào)整使得滿足堆的性質(zhì)(從堆尾son=len開始，判斷它與父

4、結(jié)點son/2的大小，若heapson=heapson/2為止)。開始時堆的長度len=0。 實際上，我們也可以直接用完全二叉樹的形式描述出這個過程，得到如下的一棵完全二叉樹（堆）：void put(int d) /heap1為堆頂int now, next;heap+heap_size = d;now = heap_size;while(now 1)next = now 1;if(heapnow = heapnext) break;swap(heapnow, heapnext);now = next;使用C+標(biāo)準(zhǔn)模板庫STL（需要頭文件algorithm）：void put(int d)he

5、ap+heap_size = d;/push_heap(heap + 1, heap + heap_size + 1); /大根堆push_heap(heap + 1, heap + heap_size + 1, greater(); /小根堆 2、從堆中取出并刪除一個元素的算法(get)如下：（1）取出堆的根結(jié)點的值。（2）把堆的最后一個結(jié)點（len）放到根的位置上，把根覆蓋掉。把堆 的長度減一。（3）把根結(jié)點置為當(dāng)前父結(jié)點pa。（4）如果pa無兒子（palen/2），則轉(zhuǎn)（6）；否則，把pa的兩（或一） 個兒子中值最小的那個置為當(dāng)前的子結(jié)點son。（5）比較pa與son的值，如果fa的值小

6、于或等于son，則轉(zhuǎn)（6）； 否則，交換這兩個結(jié)點的值，把pa指向son，轉(zhuǎn)（4）。（6）結(jié)束。int get() /heap1為堆頂int now=1, next, res= heap1;heap1 = heapheap_size-;while(now * 2 = heap_size)next = now * 2;if (next heap_size & heapnext + 1 heapnext) next+;if (heapnow = heapnext) break;swap(heapnow, heapnext);now = next;return res;使用C+標(biāo)準(zhǔn)模板庫ST

7、L（需要頭文件algorithm）：int get()/pop_heap(heap + 1, heap + heap_size + 1); /大根堆pop_heap(heap + 1, heap + heap_size + 1, greater(); /小根堆return heapheap_size-;五、堆的應(yīng)用五、堆的應(yīng)用 例1、合并果子(fruit)【問題描述】 在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。 每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和?？梢钥闯?，所有的果子經(jīng)過n-1次合并之后

8、，就只剩下一堆了。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。 因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節(jié)省體力。假定每個果子重量都為1，并且已知果子的種類數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計出合并的次序方案，使多多耗費的體力最少，并輸出這個最小的體力耗費值。 例如有3種果子，數(shù)目依次為1，2，9?？梢韵葘?1、2堆合并，新堆數(shù)目為3，耗費體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為12，耗費體力為 12。所以多多總共耗費體力=3+12=15?？梢宰C明15為最小的體力耗費值?！据斎胛募枯斎胛募ruit.in包括兩行，第一行是一個整數(shù)n（1

9、 = n = 30000），表示果子的種類數(shù)。第二行包含n個整數(shù)，用空格分隔，第i個整數(shù)ai（1 = ai = 20000）是第i種果子的數(shù)目?！据敵鑫募枯敵鑫募ruit.out包括一行，這一行只包含一個整數(shù)，也就是最小的體力耗費值。輸入數(shù)據(jù)保證這個值小于231?！緲永惠斎搿?1 2 9【樣例一輸入】103 5 1 7 6 4 2 5 4 1【樣例一輸出】15【樣例一輸出】120【數(shù)據(jù)規(guī)模】對于30%的數(shù)據(jù)，保證有n = 1000；對于50%的數(shù)據(jù)，保證有n = 5000；對于全部的數(shù)據(jù)，保證有n = 30000?！締栴}分析】 1、算法分析 將這個問題換一個角度描述：給定n個葉結(jié)點，每個

10、結(jié)點有一個權(quán)值Wi，將它們中兩個、兩個合并為樹，假設(shè)每個結(jié)點從根到它的距離是Di，使得最終(wi * di)最小。 于是，這個問題就變?yōu)榱私?jīng)典的Huffman樹問題。Huffman樹的構(gòu)造方法如下：（1）從森林里取兩個權(quán)和最小的結(jié)點；（2）將它們的權(quán)和相加，得到新的結(jié)點，并且把原結(jié)點刪除，將新結(jié)點插入到森林中；（3）重復(fù)(1)(2)，直到整個森林里只有一棵樹。 2、數(shù)據(jù)結(jié)構(gòu) 很顯然，問題當(dāng)中需要執(zhí)行的操作是：(1) 從一個表中取出最小的數(shù) (2) 插入一個數(shù)字到這個表中。支持動態(tài)查找最小數(shù)和動態(tài)插入操作的數(shù)據(jù)結(jié)構(gòu)，我們可以選擇用堆來實現(xiàn)。因為取的是最小元素，所以我們要用小根堆實現(xiàn)。 用堆的關(guān)鍵

11、部分是兩個操作：put操作，即往堆中加入一個元素；get操作，即從堆中取出并刪除一個元素。 3、操作實現(xiàn) 整個程序開始時通過n次put操作建立一個小根堆，然后不斷重復(fù)如下操作：兩次get操作取出兩個最小數(shù)累加起來，并且形成一個新的結(jié)點，再插入到堆中。如1+1=2，再把2插入到堆的后面一個位置，然后從下往上調(diào)整，使得包括2在內(nèi)的數(shù)組滿足堆的性質(zhì)即： get和put操作的復(fù)雜度均為log2n。所以建堆復(fù)雜度為nlog2n。合并果子時，每次需要從堆中取出兩個數(shù)，然后再加入一個數(shù)，因此一次合并的復(fù)雜度為3log2n，共n-1次。所以整道題目的復(fù)雜度是nlog2n。【參考程序】#include #inc

12、lude using namespace std;int heap_size, n;int heap30001;void swap(int &a, int &b) /加&后變量可修改int t = a;a = b;b = t;void put(int d)int now, next;heap+heap_size = d;now = heap_size;while(now 1)next = now 1;if(heapnow = heapnext)return;swap(heapnow, heapnext);now = next;int get()int now, next

13、, res;res = heap1;heap1 = heapheap_size-;now = 1;while(now * 2 = heap_size)next = now * 2;if(next heap_size & heapnext + 1 heapnext)next+;if(heapnow n;for(i = 1 ; i x;put(x);for(i = 1 ; i n ; i+) /取、統(tǒng)計、插入x = get();y = get(); /也可省去這一步，而直接將x累加到heap1然后調(diào)整ans += x + y;put(x + y);cout ans endl;int mai

14、n()freopen(fruit.in, r, stdin);freopen(fruit.out, w, stdout);ios:sync_with_stdio(false); /優(yōu)化。打消iostream的輸入輸出緩存，使得cin cout 時間和printf scanf 相差無幾work();return 0; 使用C+標(biāo)準(zhǔn)模板庫STL：#include #include #include using namespace std;int n;priority_queueint,vector,greater h; /優(yōu)先隊列 void work()int i, x, y, ans = 0;c

15、in n;for(i = 1 ; i x;h.push(x);for(i = 1 ; i n ; i+) /取、統(tǒng)計、插入x = h.top();h.pop();y = h.top();h.pop();ans += x + y;h.push(x + y);cout ans endl;int main()freopen(fruit.in, r, stdin);freopen(fruit.out, w, stdout);work();return 0; 例2、堆排序(heapsort)【問題描述】 假設(shè)n個數(shù)存放在A1.n中，我們可以利用堆將它們從小到大進(jìn)行排序，這種排序方法，稱為“堆排序”。輸入

16、兩行，第1行為n，第2行為n個整數(shù)，每個數(shù)之間用1個空格隔開。輸出1行，為從小到大排好序的n個數(shù)，每個數(shù)之間也用1個空格隔開。【問題分析】 一種思路是完全按照上一個例題的方法去做?！緟⒖汲绦?】#include #include using namespace std;int heap_size, n;int heap100001;void swap(int &a, int &b)int t = a;a = b;b = t;void put(int d)int now, next;heap+heap_size = d;now = heap_size;while(now 1)ne

17、xt = now 1;if(heapnow = heapnext)return;swap(heapnow, heapnext);now = next;int get()int now, next, res;res = heap1;heap1 = heapheap_size-;now = 1;while(now * 2 = heap_size)next = now * 2;if(next heap_size & heapnext + 1 heapnext)next+;if(heapnow n;for(i = 1 ; i x;put(x);for(i = 1 ; i n ; i+) cou

18、t get() ;cout get() endl;int main()freopen(heapsort.in, r, stdin);freopen(heapsort.out, w, stdout);work();return 0; 另一種思路是考慮這樣兩個問題，一是如何構(gòu)建一個初始（大根）堆？二是確定了最大值后（堆頂元素A1即為最大值），如何在剩下的n-1個數(shù)中，調(diào)整堆結(jié)構(gòu)產(chǎn)生次大值？ 對于第一個問題，我們可以這樣理解，首先所有葉結(jié)點（編號為N/2+1到N）都各自成堆，我們只要從最后一個分支結(jié)點（編號為N/2）開始，不斷“調(diào)整”每個分支結(jié)點與孩子結(jié)點的值，使它們滿足堆的要求，直到根結(jié)點為止，這

19、樣一定能確保根（堆頂元素）的值最大。“調(diào)整”的思想如下：即如果當(dāng)前結(jié)點編號為i, 則它的左孩子為2*i, 右孩子2*i+1,首先比較Ai與MAX（A2*i，A2*i+1）；如果Ai大，說明以結(jié)點i為根的子樹已經(jīng)是堆，不用再調(diào)整。否則將結(jié)點i和左右孩子中值大的那個結(jié)點j互換位置，互換后可能破壞以j為根的堆所以必須再比較Aj 與MAX（A2*j，A2*j+1）,依此類推，直到父結(jié)點的值大于等于兩個孩子或出現(xiàn)葉結(jié)點為止。這樣，以i為根的子樹就被調(diào)整成為一個堆。 編寫的子程序如下：void heap(int r, int nn, int ii)/一次操作，使r滿足堆的性質(zhì)，得到1個最大數(shù)在rii中 i

20、nt x, i=ii, j; x = rii; /把待調(diào)整的結(jié)點值暫存起來 j = 2 * i; /j存放i的孩子中值大的結(jié)點編號，開始時為i的左孩子編號 while(j = nn) /不斷調(diào)整，使以i為根的二叉樹滿足堆的性質(zhì) if(j nn & rj rj + 1) j+; /若i有右孩子且值比左孩子大，則把j設(shè)為右孩子的編號 if(x = 1 , i-) heap(a,n,i)； /建立初始堆，且產(chǎn)生最大值A(chǔ)1 for(i=n ; i = 2 ; i-) /將當(dāng)前最大值交換到最終位置上，再對前i-1個數(shù)調(diào)整 swap(a1,ai); heap(a,i-1,1)； 輸出； retur

21、n 0;【小結(jié)】 堆排序在數(shù)據(jù)較少時并不值得提倡，但數(shù)據(jù)量很大時，效率就會很高。因為其運算的時間主要消耗在建立初始堆和調(diào)整過程中，堆排序的時間復(fù)雜度為O（nlog2n），而且堆排序只需一個供交換用的輔助單元空間，是一種不穩(wěn)定的排序方法。 例3、魚塘釣魚（fishing）【問題描述】 有N個魚塘排成一排（N100），每個魚塘中有一定數(shù)量的魚，例如：N=5時，如下表： 即：在第1個魚塘中釣魚第1分鐘內(nèi)可釣到10條魚，第2分鐘內(nèi)只能釣到8條魚，第5分鐘以后再也釣不到魚了。從第1個魚塘到第2個魚塘需要3分鐘，從第2個魚塘到第3個魚塘需要5分鐘， 【編程任務(wù)】給出一個截止時間T(T1000)，設(shè)計一個釣

22、魚方案，從第1個魚塘出發(fā)，希望能釣到最多的魚。假設(shè)能釣到魚的數(shù)量僅和已釣魚的次數(shù)有關(guān)，且每次釣魚的時間都是整數(shù)分鐘?！据斎敫袷健枯斎胛募?行，分別表示：第1行為N；第2行為第1分鐘各個魚塘能釣到的魚的數(shù)量，每個數(shù)據(jù)之間用一空格隔開；第3行為每過1分鐘各個魚塘釣魚數(shù)的減少量，每個數(shù)據(jù)之間用一空格隔開；第4行為當(dāng)前魚塘到下一個相鄰魚塘需要的時間；第5行為截止時間T；【輸出格式】輸出文件僅一個整數(shù)（不超過231-1），表示你的方案能釣到的最多的魚。【知識準(zhǔn)備】 最優(yōu)化原理、貪心法、動態(tài)規(guī)劃、用堆結(jié)構(gòu)實現(xiàn)貪心?！締栴}分析】算法一： 我們可以這樣想：如果知道了取到最大值的情況下，人最后在第i個魚塘里釣

23、魚，那么用在路上的時間是固定的，因為我們不會先跑到第i個魚塘里釣一分鐘后再返回前面的魚塘釣魚，這樣把時間浪費在路上顯然不劃算，再說在你沒到某個魚塘里去釣魚之前，這個塘里的魚也不會跑掉（即數(shù)量不會減少）。所以這時我們是按照從左往右的順序釣魚的，也可以看成路上是不需要時間的，即人可以自由在1i個魚塘之間來回走，只要盡可能選取釣到的魚多的地方就可以了，這就是我們的貪心思想。其實，這個貪心思想并不是模擬釣魚的過程，只是統(tǒng)計出在各個魚塘釣魚的次數(shù)。程序?qū)崿F(xiàn)時，只要分別枚舉釣魚的終【輸入樣例】510 14 20 16 92 4 6 5 33 5 4 414【輸出樣例】76 點魚塘（從魚塘1到魚塘n），每次

24、按照上述貪心思想確定在哪些魚塘里釣魚，經(jīng)過n次后確定后最終得到的一定是最優(yōu)方案。算法二：其實，這道題是考慮最優(yōu)性問題的，所以我們也可以用動態(tài)規(guī)劃來解決，假設(shè)用Opttn來表示第t分鐘時，人在第n個魚塘里釣魚，最多所能釣到的魚數(shù)。則：Opttn =MaxinumOptt-kn-1+S；窮舉k，S為t-k+1到t之間，除去從第n-1的魚塘走到第n個魚塘的時間，在第n個魚塘中可以釣到的魚數(shù)。算法三：建立以fish為關(guān)鍵字的大根堆，包括能釣到魚的數(shù)量和池塘的編號。然后借助枚舉創(chuàng)造條件，實現(xiàn)復(fù)雜度為O（m*nlogn）的算法?！緟⒖汲绦颉?include #include using namespace

25、 std;struct Data int fish, lake; /堆中結(jié)點的信息;Data heap101;int t101, f101, d101; int Max, k, t1;void maintain(int i) /維護(hù)堆 Data a; int next; a = heapi; next = i * 2; while(next = k) if(next k & heapnext.fish heapnext + 1.fish)next+; if(a.fish n; for(i = 1 ; i fi; for(i = 1 ; i di; for(i = 1 ; i ti; c

26、in m; for(k = 1 ; k = n ; k+) /枚舉最遠(yuǎn)走到的池塘的編號 int Time = m - t1; /計算剩余時間 int ans = 0; for(i = 1 ; i = k ; i+) /收集能夠釣魚的池塘的資料 heapi.fish = fi; heapi.lake = i; for(i = 1 ; i 0 & heap1.fish 0) ans += heap1.fish; /貪心選取魚最多的池塘 heap1.fish -= dheap1.lake; /修改魚的數(shù)量 maintain(1); /堆維護(hù) Time-; /剩余時間變少 if(ans Max

27、) Max = ans; /刷新最優(yōu)解 t1 += tk; /累計走路需要的時間 cout Max endl;int main() freopen(fishing.in, r, stdin); freopen(fishing.out, w, stdout); work(); return 0;使用STL的版本：#include #include #include #define fish first#define lake secondusing namespace std;priority_queue pair heap;int t101, f101, d101; int ans, m, M

28、ax, n, k, t1, Time;void work()int i, j;cin n;for(i = 1 ; i fi;for(i = 1 ; i di;for(i = 1 ; i ti;cin m;for(k = 1 ; k = n ; k+) /枚舉最遠(yuǎn)走到的池塘的編號 Time = m - t1; /計算剩余時間 ans = 0; for(i = 1 ; i 0 & heap.top().fish 0) pair a = heap.top(); heap.pop(); ans += a.fish; /貪心選取魚最多的池塘 a.fish -= da.lake; /修改魚的數(shù)量

29、heap.push(a); /堆維護(hù) Time-; /剩余時間變少 if(ans Max) Max = ans; /刷新最優(yōu)解t1 += tk; /累計走路需要的時間cout Max endl;int main()freopen(fishing.in, r, stdin);freopen(fishing.out, w, stdout);work();return 0;【上機練習(xí)上機練習(xí)】 1、合并果子(fruit)【問題描述】 在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。 每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于

30、兩堆果子的重量之和?？梢钥闯?，所有的果子經(jīng)過n-1次合并之后，就只剩下一堆了。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。 因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節(jié)省體力。假定每個果子重量都為1，并且已知果子的種類數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計出合并的次序方案，使多多耗費的體力最少，并輸出這個最小的體力耗費值。例如有3種果子，數(shù)目依次為1，2，9?？梢韵葘?1、2堆合并，新堆數(shù)目為3，耗費體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為12，耗費體力為 12。所以多多總共耗費體力=3+12=15?？梢宰C明15為最小的體力耗費值?！据斎胛募?輸入文件fru