信息學(xué)奧賽一本通第3章第3節(jié)堆及其應(yīng)用(C++版).ppt

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

2、點（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操作，即從堆中取出并刪除一個元素。 1、往堆中加入一個元素的算法(p

3、ut)如下： （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開始，判斷它與父結(jié)點son/2的大小，若heapson=heapson/2

4、為止)。開始時堆的長度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（需要頭文件）： void put(int d) heap+heap_size = d; /push_h

5、eap(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的值小于或等于son，則轉(zhuǎn)（6）； 否則

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 ,使用C+標(biāo)準(zhǔn)模板庫STL（需要頭文件）： int get() /pop_heap(heap + 1, heap + heap_size + 1); /大根堆 pop_heap(heap + 1, heap + heap_size + 1, greater();

7、/小根堆 return heapheap_size-; ,五、堆的應(yīng)用,例1、合并果子(fruit) 【問題描述】 在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。 每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。可以看出，所有的果子經(jīng)過n-1次合并之后，就只剩下一堆了。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。 因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節(jié)省體力。假定每個果子重量都為1，并且已知果子的種類數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計出合并的次序方案，使多多耗費的

8、體力最少，并輸出這個最小的體力耗費值。 例如有3種果子，數(shù)目依次為1，2，9?？梢韵葘?1、2堆合并，新堆數(shù)目為3，耗費體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為12，耗費體力為 12。所以多多總共耗費體力=3+12=15。可以證明15為最小的體力耗費值。,【輸入文件】 輸入文件fruit.in包括兩行，第一行是一個整數(shù)n（1 = n = 30000），表示果子的種類數(shù)。第二行包含n個整數(shù)，用空格分隔，第i個整數(shù)ai（1 = ai = 20000）是第i種果子的數(shù)目。 【輸出文件】 輸出文件fruit.out包括一行，這一行只包含一個整數(shù)，也就是最小的體力耗費值。輸入數(shù)據(jù)保

9、證這個值小于231。,【樣例一輸入】 3 1 2 9 【樣例一輸入】 10 3 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é)點，每個結(jié)點有一個權(quán)值Wi，將它們中兩個、兩個合并為樹，假設(shè)每個結(jié)點從根到它的距離是Di，使得最終(wi * di)最小。 于是，這個問題就變?yōu)榱私?jīng)典的Huffman樹問題。Huffman樹的構(gòu)造方法如下： （1）從森林里取兩

10、個權(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)鍵部分是兩個操作：put操作，即往堆中加入一個元素；get操作，即從堆中取出并刪除一個元素。 3、操作實現(xiàn) 整個程序開始時通過n次put操作建立一個小根堆，然后不斷重復(fù)如下操作：兩次get操作取出兩個最小數(shù)累加起來

11、，并且形成一個新的結(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 #include using namespace std; int heap_size, n; int heap30001; void swap(int ,now = next; int get() int now

12、, next, res; res = heap1; heap1 = heapheap_size-; now = 1; while(now * 2 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 main() freopen(fruit.in, r, stdin); freopen(fruit.out, w, stdout); ios:syn

13、c_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_queue,greater h; /優(yōu)先隊列 void work() int i, x, y, ans = 0; cin n; for(i = 1 ; i x; h.push(x); ,for(i = 1 ; i n ; i+) /取、統(tǒng)計、插入 x =

14、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)行排序，這種排序方法，稱為“堆排序”。輸入兩行，第1行為n，第2行為n個整數(shù)，每個數(shù)之間用1個空格隔開。輸出1行，為從小到大排好序的n個數(shù)，每個數(shù)之間

15、也用1個空格隔開。 【問題分析】 一種思路是完全按照上一個例題的方法去做。 【參考程序1】 #include #include using namespace std; int heap_size, n; int heap100001;,void swap(int ,heap1 = heapheap_size-; now = 1; while(now * 2 n; for(i = 1 ; i x; put(x); ,for(i = 1 ; i n ; i+) cout get() ; cout get() endl; int main() freopen(heapsort.in, r, std

16、in); 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é)點為止，這樣一定能確保根（堆頂元素）的值最大?！罢{(diào)整”的思想如下：即如果當(dāng)前結(jié)點編號為i, 則它的左孩子為2*i, 右孩子2*i

17、+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中 int x, i=ii, j; x = rii; /把待調(diào)整的結(jié)點值暫存起來 j = 2 * i; /j存放i的孩子

18、中值大的結(jié)點編號，開始時為i的左孩子編號 while(j = nn) /不斷調(diào)整，使以i為根的二叉樹滿足堆的性質(zhì) if(j nn /故意讓j超出范圍，終止循環(huán), ri = x; /調(diào)整到最終位置 經(jīng)過第一步驟建立好一個初始堆后，可以確定堆頂元素值最大，我們就把它A1與最后一個元素AN交換，然后再對A1.N-1進(jìn)行調(diào)整，得到次大值與AN-1交換，如此下去，所有元素便有序存放了。 主程序的框架如下： 【參考程序2】 int a100001; int i,temp,n; int main() 輸入n和n個元素； for(i=n / 2 ; i = 1 , i-) heap(a,n,i)； /建立初始

19、堆，且產(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)； 輸出； return 0; 【小結(jié)】 堆排序在數(shù)據(jù)較少時并不值得提倡，但數(shù)據(jù)量很大時，效率就會很高。因為其運算的時間主要消耗在建立初始堆和調(diào)整過程中，堆排序的時間復(fù)雜度為O（nlog2n），而且堆排序只需一個供交換用的輔助單元空間，是一種不穩(wěn)定的排序方法。,例3、魚塘釣魚（fishing） 【問題描述】 有N個魚塘排成一排（N100），每個魚塘中有一定數(shù)量的魚，例如：N=5時，如下表： 即：在第1個魚塘中釣魚第1分鐘內(nèi)可

20、釣到10條魚，第2分鐘內(nèi)只能釣到8條魚，第5分鐘以后再也釣不到魚了。從第1個魚塘到第2個魚塘需要3分鐘，從第2個魚塘到第3個魚塘需要5分鐘，,【編程任務(wù)】 給出一個截止時間T(T1000)，設(shè)計一個釣魚方案，從第1個魚塘出發(fā)，希望能釣到最多的魚。 假設(shè)能釣到魚的數(shù)量僅和已釣魚的次數(shù)有關(guān)，且每次釣魚的時間都是整數(shù)分鐘。 【輸入格式】 輸入文件共5行，分別表示： 第1行為N； 第2行為第1分鐘各個魚塘能釣到的魚的數(shù)量，每個數(shù)據(jù)之間用一空格隔開； 第3行為每過1分鐘各個魚塘釣魚數(shù)的減少量，每個數(shù)據(jù)之間用一空格隔開； 第4行為當(dāng)前魚塘到下一個相鄰魚塘需要的時間； 第5行為截止時間T； 【輸出格式】 輸

21、出文件僅一個整數(shù)（不超過231-1），表示你的方案能釣到的最多的魚。,【知識準(zhǔn)備】 最優(yōu)化原理、貪心法、動態(tài)規(guī)劃、用堆結(jié)構(gòu)實現(xiàn)貪心。 【問題分析】 算法一： 我們可以這樣想：如果知道了取到最大值的情況下，人最后在第i個魚塘里釣魚，那么用在路上的時間是固定的，因為我們不會先跑到第i個魚塘里釣一分鐘后再返回前面的魚塘釣魚，這樣把時間浪費在路上顯然不劃算，再說在你沒到某個魚塘里去釣魚之前，這個塘里的魚也不會跑掉（即數(shù)量不會減少）。所以這時我們是按照從左往右的順序釣魚的，也可以看成路上是不需要時間的，即人可以自由在1i個魚塘之間來回走，只要盡可能選取釣到的魚多的地方就可以了，這就是我們的貪心思想。其實

22、，這個貪心思想并不是模擬釣魚的過程，只是統(tǒng)計出在各個魚塘釣魚的次數(shù)。程序?qū)崿F(xiàn)時，只要分別枚舉釣魚的終,【輸入樣例】 5 10 14 20 16 9 2 4 6 5 3 3 5 4 4 14,【輸出樣例】 76,點魚塘（從魚塘1到魚塘n），每次按照上述貪心思想確定在哪些魚塘里釣魚，經(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個魚塘

23、的時間，在第n個魚塘中可以釣到的魚數(shù)。 算法三： 建立以fish為關(guān)鍵字的大根堆，包括能釣到魚的數(shù)量和池塘的編號。然后借助枚舉創(chuàng)造條件，實現(xiàn)復(fù)雜度為O（m*nlogn）的算法。 【參考程序】 #include #include using namespace 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

24、(next = k) if(next k ,void work() int i, j, m, n; cin n; for(i = 1 ; i fi; for(i = 1 ; i di; for(i = 1 ; i ti; cin m; for(k = 1 ; k 0 /剩余時間變少 ,if(ans Max) Max = ans; /刷新最優(yōu)解 t1 += tk; /累計走路需要的時間 cout #include #include #define fish first #define lake second using namespace std; priority_queue heap;,in

25、t t101, f101, d101; int ans, m, Max, 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 0 /剩余時間變少 ,if(ans Max) Max = ans; /刷新最優(yōu)解 t1 += tk; /累計走路需要的時間 cout Max endl; int main() freopen(fishing.in, r, stdin); freopen(fishing.out, w,

26、stdout); work(); return 0; ,【上機練習(xí)】,1、合并果子(fruit) 【問題描述】 在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。 每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和?？梢钥闯?，所有的果子經(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。,可以證明15為最小的體力耗費值。 【輸入文件】 輸入文件fruit.in包括兩行，第一行是一個整數(shù)n（1 = n = 30000），表示果子的種類數(shù)。第二行包含n個整數(shù)，用空格分隔，第i個整數(shù)ai（1 = ai = 20000）是第i種果子的數(shù)目。 【輸出文件】 輸出文件fruit.out包括一行，這一行只包含一個整數(shù)，也就是最小的體力耗費