[编程题]哈夫曼树

##### 输入描述:
```输入有多组数据。

`输出权值。`

```5
1 2 2 5 9
```

## 输出

```37
```

```#include<iostream>
#include<queue>
using namespace std;
int main(){
int n,temp,a,b;
int weight;
priority_queue<int,vector<int>,greater<int>> minheap;
while(cin>>n)
{
weight = 0;
for(int i= 0;i < n;i++)
{
cin>>temp;
minheap.push(temp);
}
while(minheap.size()!= 1)
{
a = minheap.top();
minheap.pop();
b = minheap.top();
minheap.pop();
weight = weight + a +b;
minheap.push(a+b);

}
cout<<weight<<endl;
minheap.pop();
}
return 0;
}
```

```import java.util.Scanner;
import java.util.PriorityQueue;

public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int n = in.nextInt();
PriorityQueue<Integer> q = new PriorityQueue<Integer>();
for(int i=0;i<n;i++)
int ans = 0;
while(q.size()>1){
int first = q.poll();
int sec = q.poll();
ans += (first + sec);
}
System.out.println(ans);
}
}
}
```

#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())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=Q.top();
Q.pop();
int b=Q.top();
Q.pop();
ans+=a+b;
Q.push(a+b);
}
printf("%d\n",ans);
}
return 0;
}

```#include<iostream>
#include<limits.h>
using namespace std;```
```typedef struct HuffmanNode{
long int weight;
int parent;
int lchild;
int rchild;
}HuffmanNode,*HuffmanTree;```
`void select(int& s1,int& s2,HuffmanTree T, int n);`
```int main()
{
int n;
HuffmanTree Tree;
while(cin>>n)
{
int m=2*n-1;
Tree=(HuffmanTree)malloc(sizeof(HuffmanNode)*(m+1));
int i;
for(i=1;i<=n;i++)
{
int weight;
cin>>weight;
Tree[i].weight=weight;
Tree[i].parent=0;
Tree[i].lchild=0;
Tree[i].rchild=0;
}
for(;i<=m;i++)
{
Tree[i].weight=0;
Tree[i].lchild=0;
Tree[i].rchild=0;
Tree[i].parent=0;
}
for(i=n+1;i<=m;i++)
{
int s1,s2;
select(s1,s2,Tree,i-1);
Tree[i].lchild=s1;
Tree[i].rchild=s2;
Tree[s1].parent=i;
Tree[s2].parent=i;
Tree[i].weight=Tree[s1].weight+Tree[s2].weight;
}
long int sum=0;
for(i=1;i<=n;i++)
{
int p,f,j=0;
for(p=i,f=Tree[p].parent;f!=0;p=f,f=Tree[p].parent)
{
j++;
}
sum=sum+(Tree[i].weight*j);
}
cout<<sum<<endl;
free(Tree);
}

return 0;
}```
```void select(int& s1,int& s2,HuffmanTree T,int n)
{
int i;
long int min=LONG_MAX,secMin=LONG_MAX;
for(i=1;i<=n;i++)
{
if(T[i].parent==0)
{
if(T[i].weight<=min)
{
s2=s1;
secMin=min;
s1=i;
min=T[i].weight;
}
else if(T[i].weight<=secMin)
{
s2=i;
secMin=T[i].weight;
}
}
}
}
```

#include<stdlib.h>  //储存malloc的文件
#include <stdio.h>

void sort(int *array, int begin, int num);
int main(){
int num;
int height = 0;
int *array = NULL;
while (scanf("%d", &num) != EOF){

//创建动态数组；注意使用之后要释放内存
array = (int *)malloc(num * sizeof(int));

for (int k = 0; k < num; k++){
scanf("%d", &array[k]);
}
sort(array, 0, num);

int i = 1, sum = 0;
while (i<num)
{
sort(array, i - 1, num);//每次都要重新排序,因为生成了新的节点
sum += array[i] + array[i - 1];//计算父亲
array[i] = array[i] + array[i - 1];//将小树生成新的节点
i++;
}
printf("%d\n", sum);

}
//释放内存
free(array);
return 0;
}
//传地址进行排序
void sort(int *array, int begin, int num){
//现将数组进行排序；从小到大，冒泡虽然慢，但是比较容易实现
for (int i = begin; i < num; i++){
for (int j = i + 1; j < num; j++){
if (array[j] < array[i]){
int tmp = array[j];
array[j] = array[i];
array[i] = tmp;
}
}
}
}

```#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
int n, sum, temp;
vector<int> s;
while(cin >> n)
{
sum = 0;
for(int i = 0; i!= n; ++i)
{
cin >> temp;
s.push_back(temp);
}
int bg = 0, ed = n;
while(ed-bg != 1)
{
sort(&s[bg], &s[ed]);
temp = s[bg++] + s[bg++];
sum += temp;
s.push_back(temp);
ed++;
}
cout << sum << endl;
s.clear();
}
}```

``````#include <iostream>
#include <queue>
using namespace std;
int main()
{
int n,ans,i;
priority_queue<int, vector<int>, greater<int>> tmp;
cin>>n;
for(i=0;i<n;++i)
{
cin>>ans;
tmp.push(ans);
}
int sum=0;
while(tmp.size()>1)
{
int min1,min2;
min1=tmp.top();
tmp.pop();
min2=tmp.top();
tmp.pop();
sum+=min1+min2;
tmp.push(min1+min2);
}
cout<<sum<<endl;
return 0;
}``````

#include<iostream>
#include<queue>

using namespace std;

int main()
{
//输入多少个数据
int n;
cin>>n;
//优先队列
//vector:盛放队列中的数据的容器
//greater:队列中的数据从小到大
priority_queue<int, vector<int>, greater<int> > q;
//要输入的结点数据
int nodeData;
for(int i=0; i<n; i++)
{
cin>>nodeData;
//把数据放到队列中并自动从小到大排列
q.push(nodeData);
}

//计算哈夫曼值,a,b分别为每次取出的头两个结点（最小的两个）
int sum=0;
int a, b;
while(q.size()>1)
{
a=q.top();
q.pop();
b=q.top();
q.pop();
q.push(a+b);
sum=sum+a+b;
}
cout<<sum<<endl;

return 0;
}

```#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef struct HuffmanTree{
int data;
int weight;
HuffmanTree *lchild,*rchild;
} HT;
int n;
vector<HT> seq;
bool cmp(HT a,HT b){
return a.data<b.data;
}
void insert_node(HT* node){
if(seq.empty()){
seq.push_back(*node);
return;
}
vector<HT>::iterator it = seq.begin();
for(it;it != seq.end();it++){
if(node->data <= it->data){
seq.insert(it,*node);
return;
}
}
seq.push_back(*node);
}
HT* buildHT(){
while(1){
HT *fnode = (HT*) malloc(sizeof(HT));
HT *node_l = (HT*) malloc(sizeof(HT));
HT *node_r = (HT*) malloc(sizeof(HT));
*node_l = seq[0];
*node_r = seq[1];
fnode->data = node_l->data + node_r->data;
fnode->lchild = node_l;
fnode->rchild = node_r;
seq.erase(seq.begin());
seq.erase(seq.begin());
insert_node(fnode);
if(seq.size() == 1){
return fnode;
}
}
}
void cal_weight(int &ans,HT* node,int level){
if(node == NULL) return;
if(node->lchild == NULL && node->rchild == NULL){
ans = ans + node->data * level;
return;
}
cal_weight(ans,node->lchild,level+1);
cal_weight(ans,node->rchild,level+1);
}
int main(){
int ans=0;
scanf("%d",&n);
for(int i=0;i<n;i++){
HT *node = (HT*) malloc(sizeof(HT));
scanf("%d",&node->data);
node->lchild = NULL;
node->rchild = NULL;
seq.push_back(*node);
}
sort(seq.begin(),seq.end(),cmp);
HT* root = buildHT();
cal_weight(ans,root,0);
printf("%d",ans);
return 0;
}
```

```import java.util.PriorityQueue;
import java.util.Scanner;

/**
* Created by fhqplzj on 17-2-19 at 下午8:03.
*/
public class Huff {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextInt()) {
int n = scanner.nextInt();
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(n);
for (int i = 0; i < n; i++) {
}
int result = 0;
while (priorityQueue.size() > 1) {
int a = priorityQueue.poll();
int b = priorityQueue.poll();
result += a + b;
}
System.out.println(result);
}
}
}```

```#include <iostream>
#include <queue>
using namespace std;

struct cmp {
bool operator() (const int & a, const int & b) {
return a > b;
}
};

int main() {
//freopen("t.txt", "r", stdin);

int n;
while(cin>>n) {
priority_queue<int, vector<int>, cmp> pq;
for(int i = 0; i<n; i++) {
int t;
cin>>t;
pq.push(t);
}
int res = 0;
while(pq.size() > 1) {
int a = pq.top(); pq.pop();
int b = pq.top(); pq.pop();
int c = a + b;
res += c;
pq.push(c);
}
cout<<res<<endl;
}
}```

```#include <iostream>
#include <queue>
#include <functional>
using namespace std;
int main() {
int n;
priority_queue<int, vector<int>, greater<int> > Q;
while (cin >> n) {
while (Q.empty() == false) Q.pop();
for (int i = 0; i < n; i++) {
int x;
cin >> x;
Q.push(x);
}
int ans = 0;
while (Q.size() > 1) {
int a = Q.top();
Q.pop();
int b = Q.top();
Q.pop();
ans = ans + a + b;
Q.push(a + b);
}
cout << ans << endl;
}
return 0;
}```

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
int number[1000];
int n,result;
while (cin >> n) {
result = 0;
for (int i = 0; i < n; i++)cin >> number[i];
for (int i = 0; i < n-1; i++) {
sort(number+i, number + n);
number[i + 1] = number[i] + number[i + 1];
result += number[i + 1];
}
cout << result << endl;
}
}

#include<stdio.h>
#include<queue>
#include<stdlib.h>
using namespace std;
int main() {
int number;
scanf("%d", &number);
priority_queue< int, vector<int>, greater<int> > Q;
while (Q.empty() == false) Q.pop();
int element;
do {
scanf("%d", &element);
Q.push(element);
} while (getchar() != '\n');
int a, b, ans = 0;
while (Q.size() > 1) {
a = Q.top();
Q.pop();
b = Q.top();
Q.pop();
ans += a + b;
Q.push(a + b);
}
printf("%d", ans);
}

import heapq
class Solution:
def getWPL(self, List):
if List is None:
return None
wpl = 0
while len(List) >  1:
heapq.heapify(List)
tmp1 = heapq.heappop(List)
heapq.heapify(List)
tmp2 = heapq.heappop(List)
Sum = tmp1 + tmp2
heapq.heappush(List, Sum)
wpl += Sum

return wpl

num = int(input())
List = [int(i) for i in input().split(' ')]

//答案结果为非叶子节点数值之和
//直到最后只剩两个元素
#include <stdio.h>
#include <stdlib.h>

void sort(int *a, int start, int end);

int main() {
int n;
int result = 0;
while(scanf("%d",&n) != EOF) {
int nums[n];
for(int i = 0; i < n; i++)
scanf("%d",&nums[i]);
for(int i = 0; i < n - 1; i++) {
sort(nums, i, n);
nums[i+1] = nums[i] + nums[i+1];
result = result + nums[i+1];
}
printf("%d\n",result);
result = 0;
}
return 0;
}

void sort(int *a, int start, int end) {
for(int i = start; i < end; i++) {
for(int j = i; j < end; j++) {
if(a[i] > a[j]){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}

```#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
while(cin>>n)
{
int temp;
//优先级队列  小顶堆
priority_queue<int,vector<int>,greater<int>>q;
while(n--)
{
cin>>temp;
q.push(temp);
}
int sum = 0;
while(q.size()>1)
{
int a =  q.top();
q.pop();
int b =  q.top();
q.pop();
q.push(a+b);
sum  = sum+a+b;
}
cout<<sum<<endl;

}
return 0;
}
```

#include<stdio.h>
#include<queue>//使用优先队列标准模板
using namespace std;

//定义小顶锥
priority_queue<int,vector<int>,greater<int>> Q;

int main(){
int n;
while(scanf("%d",&n)!=EOF){
int x;
for(int i=0;i<n;i++){
scanf("%d",&x);
Q.push(x);
}

int ans = 0;//必须初始化
while(Q.size() > 1){
//取出权值最小的两个结点
int a = Q.top();
Q.pop();
int b = Q.top();
Q.pop();

ans += a+b;
Q.push(a+b);
}

printf("%d\n",ans);
}
return 0;
}

#include<stdio.h>
#include<stdlib.h>
typedef struct node{
struct node *lchild,*rchild;
int weight;
}BTNode;
BTNode *createHufftree(BTNode **f,int n)
{
int loop,i,k1,k2;
BTNode *pa;
for(loop=1;loop<n;loop++){
for(k1=0;k1<n&&!f[k1];k1++);
for(k2=k1+1;k2<n&&!f[k2];k2++);
for(i=k2;i<n;i++){
if(f[i]){
if(f[i]->weight<f[k1]->weight){
k2=k1;
k1=i;
}
else if(f[i]->weight<f[k2]->weight)
k2=i;
}
}
pa=(BTNode *)malloc(sizeof(BTNode));
pa->lchild=f[k1];
pa->rchild=f[k2];
pa->weight=f[k1]->weight+f[k2]->weight;
f[k1]=pa;
f[k2]=NULL;
}
return f[k1];
}
int  Print(BTNode *root,int n){
int count=0;
BTNode *p=root;
if(!p->lchild&&!p->rchild)
{
return p->weight*n;

}
else{
count=Print(p->lchild,n+1)+Print(p->rchild,n+1);
return count;

}
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
BTNode **f;
int w,sum;
f=(BTNode **)malloc(n*sizeof(BTNode *));
for(int i=0;i<n;i++)
{
f[i]=(BTNode *)malloc(sizeof(BTNode));
f[i]->lchild=f[i]->rchild=NULL;
scanf("%d",&w);
f[i]->weight=w;
}
//创建haffmantree
BTNode *root=createHufftree(f,n);
//输出权值
sum=Print(root,0);
printf("%d\n",sum);
}
}

72条回答 5937浏览

# 通过挑战的用户

• 2019-09-18 23:08:41
• 2019-09-18 18:08:33
• 2019-09-17 23:21:28
• 2019-09-17 22:12:43
• 2019-09-17 20:08:44

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题