數據結構頹廢計劃VI-堆

2019-11-14 12:12:42

字體：大中小

來源：轉載

供稿：網友

定義

優先隊列：

三種基本操作：插入節點(Insert)、取最小節點(Get_Min)和刪除最小節點(Delete_Min)。

二叉堆

是一種最常見的優先隊列，支持優先隊列的三種基本操作，且插入節點和刪除最小節點的時間復雜度為O(logn),取最小節點的時間復雜度為O(1)，效率高，過程簡單。

用途：維護貪心/DP/Dijkstra/構造…..

堆-優先隊列在STL和pb_ds庫中都有。

例題1 NOip2004 合并果子

問題描述

在一個果園里，多多已經將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。可以看出，所有的果子經過n-1次合并之后，就只剩下一堆了。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節省體力。假定每個果子重量都為1，并且已知果子的種類數和每種果子的數目，你的任務是設計出合并的次序方案，使多多耗費的體力最少，并輸出這個最小的體力耗費值。例如有3種果子，數目依次為1，2，9。可以先將1、2堆合并，新堆數目為3，耗費體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數目為12，耗費體力為12。所以多多總共耗費體力=3+12=15。可以證明15為最小的體力耗費值。

輸入文件

輸入文件fruit.in包括兩行，第一行是一個整數n，表示果子的種類數。第二行包含n個整數，用空格分隔，第i個整數ai是第i種果子的數目。

輸出文件

輸出文件fruit.out包括一行，這一行只包含一個整數，也就是最小的體力耗費值。輸入數據保證這個值小于231。

樣例輸入

3 1 2 9

樣例輸出

數據規模

對于30%的數據，保證有n≤1000 $n /leq 1000$ ：對于50%的數據，保證有n≤5000 $n /leq 5000$ ；對于全部的數據，保證有n≤10000 $n /leq 10000$ 。

題解

每次取出序列中最小的兩個數，合并后放回，對合并的體力耗費值進行計數即可。這是最適合堆的場合。

代碼

#include <iostream>#include <utility>#include <queue>using namespace std;PRiority_queue < int > Q;int main() { int N; cin >> N; int T; for ( int i=1;i<=N;i++) { cin >> T; Q.push(-T); } int T1,T2,Ans=0; for ( int i=1;i<=N-1;i++) { T1=Q.top(); Q.pop(); T2=Q.top(); Q.pop(); Q.push(T1+T2); Ans+=-(T1+T2); } cout << Ans << endl; return 0; }