哈夫曼編碼, 哈夫曼樹

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define swap(a, b) ({\
__typeof(a) temp = a;\
a = b, b = temp;\
})

typedef struct Node {
        double freq;
        char data;
        Node *lchild, *rchild;
} Node;

typedef struct Heap {
        Node **data;
        int cnt, size;
} Heap;

void clearHeap(Heap *heap) {
        free(heap->data);
        free(heap);
        return ;
}

void clear(Node *root) {
        if (!root) return ;
        clear(root->lchild);
        clear(root->rchild);
        free(root);
        return ;
}

Heap *initHeap(int s) {
        Heap *root = (Heap *)malloc(sizeof(Heap));
        root->data = (Node **)malloc(sizeof(Node *) * (s + 5));
        root->size = s, root->cnt = 0;
        return root;
}

Node *top(Heap *heap) {return heap->data[1];}
int empty(Heap *p) {return p->cnt < 1;}

void down_maintain(Heap *p) {
        if (p->cnt < 2) return ;
        int k;
        for (int i = k = 1; i << 1 <= p->cnt; i = k) {
                k = p->data[i]->freq > p->data[i << 1]->freq ? i << 1 : i;
                i << 1 | 1 <= p->cnt && (k = p->data[k]->freq > p->data[i << 1 | 1]->freq ? i << 1 | 1 : k);
                if (k == i) break;
                swap(p->data[i], p->data[k]);
        }
        return ;
}

void up_maintain(Heap *p) {
        if (p->cnt < 2) return ;
        for (int i = p->cnt; i ^ 1; i >>= 1) {
                if (p->data[i]->freq > p->data[i >> 1]->freq) break;
                swap(p->data[i], p->data[i >> 1]);
        }
        return ;
}

void pop(Heap *heap) {
        if (empty(heap)) return ;
        Node *p = top(heap);
        heap->data[1] = heap->data[heap->cnt--];
        down_maintain(heap);
        return ;
}

void push(Heap *heap, Node *p) {
        if (!heap || heap->cnt == heap->size) return ;
        heap->data[(++heap->cnt)] = p;
        up_maintain(heap);
        return ;
}

Node *getNewNode(Node *lchild, Node *rchild, double freq, char data) {
        Node *root = (Node *)malloc(sizeof(Node));
        root->lchild = lchild, root->rchild = rchild;
        root->freq = freq, root->data = data;
        return root;
}

Node *buildhalfman(Heap *heap) {
        if (heap->cnt == 1) return top(heap);
        if (empty(heap)) return top(heap);
        Node *l, *r;
        l = top(heap), pop(heap);
        r = top(heap), pop(heap);
        push(heap, getNewNode(l, r, l->freq + r->freq, 0));
        return buildhalfman(heap);
}

int getHalfmancode(Node *root, char *buff, int k) {
        if (!root) return 0;
        buff[k] = 0;
        if (root->data) return printf("%s %c %.2lf\n", buff, root->data, root->freq);
        buff[k] = '0';
        getHalfmancode(root->lchild, buff, k + 1);
        buff[k] = '1';
        getHalfmancode(root->rchild, buff, k + 1);
        return 0;
}

int main() {
        int n;
        double freq;
        char s[100];
        scanf("%d", &n);
        Heap *heap = initHeap(n);
        for (int i = 0; i < n; i++) {
                scanf("%lf%s", &freq, s);
                push(heap, getNewNode(0, 0, freq, s[0]));
        }
        Node *root = buildhalfman(heap);
        getHalfmancode(root, s, 0);
        return 0;
}