知识点
哈夫曼树,贪心算法;
方法:
选择最小的2个节点a,b合并, heap中删除a和b节点,增加a+b节点。不断重复,直到全部合并。
证明:
调整法。
这是一个哈夫曼树,果子在叶子节点,每个叶子节点会被计算path次。
例如节点b,wb=5,pb=2,cost_b=5*2=10
每个果子的cost在path确定的情况下,不受其他节点swap影响,为 wx*px;
所以在调整的时候,我们只用考虑调整的两个点,其他节点的总cost不变。
我们假设存在 wx>wy 且 px>py;
此时对这些果子的合并,消耗 cost=wx*px + wy*py;
假设我们调整x和y节点,swap交换
cost2=wx*py + wy*px
==>
cost2-cost = wx*py + wy*px - (wx*px + wy*py)
= wx(py-px)-wy(py-px)=(wx-wy)(py-px)<0
==>
cost2<cost
说明调整后,消耗减少,即权重越大,距离root节点越近。
C++ 代码
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int main(){
int n;
scanf("%d", &n);
priority_queue<int, vector<int>, greater<int>> heap;
while(n--){
int a;
scanf("%d", &a);
heap.push(a);
}
int res=0;
while(heap.size()>1){
int a=heap.top(); heap.pop();
int b=heap.top(); heap.pop();
res += a+b;
heap.push(a+b);
}
printf("%d\n", res);
return 0;
}