#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 100
#define inf 1000.0

typedef struct HtNode{
    double weight;
    int parent, lchild, rchild;
};

typedef struct HtTree{
    HtNode* ht;
    int root;
};

typedef HtTree* PHtTree;

PHtTree Huffman(double* w, int n){
    PHtTree pht;
    int i, j, p1, p2;
    double min1, min2;
    if(n <= 1)  return pht; //

    pht = (PHtTree)malloc(sizeof(HtTree));
    pht -> ht = (HtNode*)malloc(sizeof(HtNode)*(2*n-1));

    for(i = 0; i < 2*n-1; i++){
        (pht->ht[i]).parent = -1;
        (pht->ht[i]).lchild = -1;
        (pht->ht[i]).rchild = -1;
        if(i < n)  (pht->ht[i]).weight = w[i];
        else (pht->ht[i]).weight = inf;
    }

    for(i = 0; i < n-1; i++){

        p1 = p2 = -1;
        min1 = min2 = inf;
        for(j = 0; j < n+i; j++)
            if((pht->ht[j]).parent == -1)
            if((pht->ht[j]).weight < min1){
                min2 = min1;
                min1 = (pht->ht[j]).weight;
                p2 = p1;
                p1 = j;
            }
            else if((pht->ht[j]).weight < min2){
                min2 = (pht->ht[j]).weight;
                p2 = j;
            }

        pht->ht[p1].parent = n+i;
        pht->ht[p2].parent = n+i;
        pht->ht[n+i].lchild = p1;
        pht->ht[n+i].rchild = p2;
        pht->ht[n+i].weight = min1+min2;
    }

    pht->root = 2*n-1;
    return pht;
}

void HuffmanCode(int i, PHtTree pht){
    int n = MAXN;
    int k, f;
    char c[MAXN] = {'\0'};
    int start = 0;
    for(k = i, f = pht->ht[i].parent; f != -1; k = f, f = pht->ht[f].parent){
        if(pht->ht[f].lchild == k)
            c[start] = '0';
        else
            c[start] = '1';
        start++;
    }
    strrev(c);
    printf("%d,\t%s\n", i, c);
}

int main(){
    int n = 8;
    double w[8] = {5, 29, 7, 8, 14, 23, 3, 11};

    PHtTree ppht;

    ppht = Huffman(w, n);

    for(int i = 0; i < 2*n - 1; i++)
        printf("%d,%d,%d,%d\n", i, ppht->ht[i].parent, ppht->ht[i].lchild, ppht->ht[i].rchild);

    printf("\n\n");

    for(int i = 0; i < n; i++)
        HuffmanCode(i, ppht);

    return 0;
}