当日总结

输入一组整型权值，构建哈夫曼树，实现哈夫曼编码，并输出带权路径长度。

输入格式:
第一行输入叶子结点个数，接着依次输入权值。若叶子数为0或1，则输出error

输出格式:
输出哈夫曼编码，输出带权路径长度。

输入样例:
在这里给出一组输入。例如：

8
5 29 7 8 14 23 3 11
输出样例:
在这里给出相应的输出。例如：

5编码为0001
29编码为10
7编码为1110
8编码为1111
14编码为110
23编码为01
3编码为0000
11编码为001
WPL:271

include

include

include

include

include

using namespace std;
struct huffmanNode{
int value;
int parent;
int left;
int right;
huffmanNode():value(0),parent(-1),left(-1),right(-1){}
huffmanNode(int v):value(v),parent(-1),left(-1),right(-1){}
};
int main()
{
int n;
cin>>n;
if(n<=1)
{
cout<<"error"<<endl;
return 0;
}
vectorvalues(n);
for(int i=0;i<n;i++)
{
cin>>values[i];
}
int l=2n-1;
vectorhuff(l);
for(int i=0;i<n;i++)
{
huff[i]=huffmanNode(values[i]);
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>minHeap;
for(int i=0;i<n;i++)
{
minHeap.push({huff[i].value,i});
}
for(int i=n;i<l;i++)
{
auto min1=minHeap.top();
minHeap.pop();
auto min2=minHeap.top();
minHeap.pop();
huff[i].value=min1.first+min2.first;
huff[i].left=min1.second;
huff[i].right=min2.second;
huff[min1.second].parent=i;
huff[min2.second].parent=i;
minHeap.push({huff[i].value,i});
}
int wpl=0;
vectorcodes(n);
for(int i=0;i<n;i++)
{
int current =i;
string code;
while(huff[current].parent!=-1)
{
int parentId=huff[current].parent;
if(huff[parentId].left==current)code+='0';
else code+='1';
current=parentId;
}
reverse(code.begin(),code.end());
codes[i]=code;
wpl+=huff[i].valuecode.size();
}
for(int i=0;i<n;i++)
{
cout<<values[i]<<"编码为"<<codes[i]<<endl;
}
cout<<"WPL:"<<wpl;
return 0;
}