//构建哈夫曼树

#include<iostream>

using namespace std;
#define N 5
#define M 2*N-1
typedef struct{
    int parent;
    int lchild;
    int rchild;
    int weight;
}hfmnode;

void select(hfmnode hfm[],int &t1,int &t2,int n){
    hfm[0].weight=100;
    for(int i=1;i<=n;i++){
        if(hfm[i].parent==0)
        {
            if(hfm[i].weight<hfm[t1].weight)
            t1=i;
        }
    }
    for(int i=1;i<=n;i++){
        if(hfm[i].parent==0&&i!=t1)
        {
            if(hfm[i].weight<hfm[t2].weight)
            t2=i;
        }
    }
}

void hfm_create(hfmnode hfm[],int w[],int n){
    for(int i=1;i<=n;i++){
        hfm[i]={0,0,0,w[i-1]};
    }
    int m=2*n-1;
    for(int i=n+1;i<=m;i++) hfm[i]={0,0,0,0};

    for(int i=n+1;i<=m;i++){
        int tree1=0,tree2=0;
        int &t1=tree1,&t2=tree2;
        select(hfm,t1,t2,i-1);
        hfm[i].weight=hfm[t1].weight+hfm[t2].weight;
        hfm[t1].parent=i;
        hfm[t2].parent=i;
        hfm[i].lchild=t1;
        hfm[i].rchild=t2;
    }
}


int main()
{
    int w[]={5,7,3,2,8};
    hfmnode hfm[M+1];//下标从1开始
    hfm_create(hfm,w,N);
    cout<<"weight"<<" "<<"parent"<<' '<<"lchild"<<' '<<"rchild"<<endl;
    for(int i=1;i<=M;i++){
        cout<<hfm[i].weight<<' '<<hfm[i].parent<<' '<<hfm[i].lchild<<' '
        <<hfm[i].rchild<<endl;
    }
}