为啥用哈夫曼做法代价最少?
首先,赫夫曼做法得到的树,最小的两个深度一定最深。
如果哈夫曼做法代价不是最少的,即有其他方法比哈夫曼代价更少,这里,其他方法并不能保证
最小的两个在最深层,也就是有某一个点a是最小的但是不在最深处(设深度是h1),有一个点b不是最小的
但却在最深处(设深度是h2)。则交换两点代价一定会降低,即把最小的放到最深处代价会变低
理由:交换之前代价是a * h1 + b * h2,交换之后代价是b * h1 + a * h2
于是(a * h1 + b * h2)- (b * h1 + a * h2)= a(h1 - h2) + b(h2 - h1)
= (h2 - h1)* (b - a)
由于h1 < h2, b > a, 故上式大于0
故交换前的代价更大,交换后的代价更小。
所以哈夫曼树的做法代价是最小的
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int N = 1e4 + 11;
int main(){
priority_queue<int, vector<int>, greater<int>> h;
int res = 0;
int n;
cin >> n;
for(int i = 0;i < n; i++) {
int x;
cin >> x;
h.push(x);
}
while(h.size() > 1){
int a = h.top(); h.pop();
int b = h.top(); h.pop();
res += a + b;
h.push(a + b);
}
cout << res << endl;
return 0;
}