哈夫曼树

#include<stdio.h>
struct tree
{
    int weight;
    int left;
    int right;
    int parent;
    int car;   //1表明该节点要加入计算
};
void insert(int y[],struct tree haf[],int z){
    int a,min1=100000000,min2=100000000,count1,count2;
    for(int i=0;i<2000;i++){
        if(y[i]<min1&&y[i]!=-1){
            min1=y[i];
            count1=i;
        }
    }
    y[count1]=-1;
    for(int i=0;i<2000;i++){
        if(y[i]<min2&&y[i]!=-1){
            min2=y[i];
            count2=i;
        }
    }
    y[count2]=-1;
    a=min1+min2;
    y[z]=a;
    haf[z].weight=a;
    haf[z].left=count1;
    haf[z].right=count2;
    haf[count1].parent=z;
    haf[count2].parent=z;
    return;
}
void cal(int sum1[],struct tree haf[],int head,int e){
    if(haf[head].car==1){
        sum1[0]=sum1[0]+e*haf[head].weight;
    }
    if(haf[head].left!=-1){
        cal(sum1,haf,haf[head].left,e+1);
    }
    if(haf[head].right!=-1){
        cal(sum1,haf,haf[head].right,e+1);
    }
    return;
}
int main(){
    int b,n,m[2000],count,sum[1],k=0,x=0;
    struct tree haff[2000];
    for(int i=0;i<2000;i++){
        haff[i].left=-1;
        haff[i].right=-1;
        haff[i].parent=-1;
        haff[i].car=-1;
        haff[i].weight=-1;
        m[i]=-1;
    }
    scanf("%d",&n);
    for(b=0;b<n;b++){
        int j;
        scanf("%d",&j);
        m[b]=j;
        haff[b].weight=j;
        haff[b].car=1;
    }
    //case1:这个方法和下面的while方法应该都可以的
	/*for(int i=0;i<n-1;i++){
		insert(m,haff,b);
		b++;
	}*/
    while(x!=2){
        x=0;
        for(int i=0;i<2000;i++){
            if(m[i]!=-1) x++;
        }
        insert(m,haff,b);
        b++;
    }
    for(int i=0;i<2000;i++){
        if(m[i]!=-1){
            count=i;
            break;
        }
    }
    sum[0]=0;
    cal(sum,haff,count,k);
    printf("%d",sum[0]);
    return 0;
}

//哈夫曼树理解题意：每次选出最小的，然后重新加入，first可以用vector然后每次都进行排序
//最好的办法是运用priority_queue
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
int main(){
    int n;
    cin>>n;
    priority_queue<int,vector<int>,greater<int>> myq;
    while(n--){
        int x;
        cin>>x;
        myq.push(x);
    }
    int ans=0;
    while(myq.size()>1){
        int a=myq.top();
        myq.pop();
        int b=myq.top();
        myq.pop();
        ans+=a+b;
        myq.push(a+b);
    }
    printf("%d\n",ans);
    return 0;
}

//实际上，可以用数组，然后每次都进行排序
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int cmp(const void* a,const void* b){
    return *(int*)b-*(int*)a;
}
int main(){
    int n;
    scanf("%d",&n);
    int num[1000];
    for(int i=0;i<n;i++){
        scanf("%d",&num[i]);
    }
    qsort(num,n,sizeof(num[0]),cmp);
    int sum=0,i;
    for(i=n-1;i>0;i--){
        int a=num[i];
        int b=num[i-1];
        num[i-1]=a+b;
        sum+=num[i-1];
        qsort(num,i,sizeof(num[0]),cmp);
    }
    printf("%d\n",sum);
    return 0;
}