题目描述
给定 N 个权值作为 N 个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。
现在,给定 N 个叶子结点的信息,请你构造哈夫曼树,并输出该树的带权路径长度。
相关知识:
1、路径和路径长度
在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为 1,则从根结点到第 L 层结点的路径长度为 L−1。
2、结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积。
3、树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为 WPL。
输入格式
第一行包含整数 N,表示叶子结点数量。
第二行包含 N 个整数,表示每个叶子结点的权值。
输出格式
输出一个整数,表示生成哈夫曼树的带权路径长度。
数据范围
2≤N≤1000,
叶子结点的权值范围 [1,100]。
输入样例:
5
1 2 2 5 9
输出样例:
37
思路:
每次找到两个最小值加到我们的答案里,可以用小根堆
代码如下:
#include<iostream>
#include<queue>
using namespace std;
int main()
{
int n;
cin>>n;
priority_queue<int,vector<int>,greater<int>> heap;//定义小根堆
while(n--)
{
int x;
cin>>x;
heap.push(x);
}
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);
}
cout<<res<<endl;
return 0;
}