哈夫曼树

it2025-03-24 22

哈夫曼树

题目描述

哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。

输入

输入有多组数据。每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。

输出

输出权值。

样例输入

2 2 8 3 5 11 30

样例输出

10 62建立优先队列 priority_queue<int> Q;

　建立小顶堆

priority_queue<int,vector<int>,greater<int> > Q; 插入 Q.push(x);

取堆顶元素

int a=Q.top(); 弹出堆顶元素，弹出后会自动调整为一个新的小顶堆。 Q.pop();

#include<queue> #include<stdio.h> using namespace std; priority_queue<int,vector<int>,greater<int> > Q; int main() { int n; while(scanf("%d",&n)!=EOF) { while(Q.empty()==false) Q.pop(); for(int i=0;i<n;i++) { int x; scanf("%d",&x); Q.push(x); } int ans=0; while(Q.size()>1) { int a,b; a=Q.top(); Q.pop(); b=Q.top(); Q.pop(); ans+=a+b; Q.push(a+b); } printf("%d\n",ans); } return 0; } View Code

#include<bits/stdc++.h> using namespace std; int main() { int n,t,sum; while(cin>>n&&n!=0) { priority_queue<int,vector<int>,greater<int> > q; for(int i=0;i<n;i++) { cin>>t; q.push(t); } sum=0; while(q.size()>1) { t=q.top(); q.pop(); t+=q.top(); q.pop(); q.push(t); sum+=t; } cout<<sum<<endl; } return 0; }

转载于:https://www.cnblogs.com/qing123tian/p/11107547.html