问题描述 给定n个互不相同的整数，以及这些整数出现的次数。 以每个整数出现的次数作为权值，构造一颗哈夫曼树。 创建哈夫曼树中间节点时，中间节点数值为左右孩子节点中数值较小者，并且较小权值的子节点作为左孩子。 在选择节点时，如果两个节点权相同，则选择数值较小的节点。 输入 输入第一行是一个正整数n(0<n<100000)。接下来总共n行。 每行两个整数v和w，v表示整数值，w表示整数v出现的次数。(0<w<=100) 输出 输出总共n行，每行先输出一个叶节点的数值，然后是该叶节点的编码。中间有一个冒号。 节点按先序遍历的顺序，节点编码按左0右1的方案编码。 c代码

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

typedef struct Node{
    int value;
    int weight;
    struct Node *left, *right;
}Node;

typedef struct MinHeap{
    int size;
    int capacity;
    Node **nodes;
}MinHeap;

Node *createNode(int value, int weight){
    Node *node = (Node*)malloc(sizeof(Node));
    node->value = value;
    node->weight = weight;
    node->left = node->right = NULL;
    return node;
}

MinHeap *createMinHeap(int capacity){
    MinHeap *heap = (MinHeap*)malloc(sizeof(MinHeap));
    heap->size = 0;
    heap->capacity = capacity;
    heap->nodes = (Node**)malloc(sizeof(Node*) * capacity);
    return heap;
}

void swap(Node **a, Node **b){
    Node *temp = *a;
    *a = *b;
    *b = temp;
}

void minHeapify(MinHeap *heap, int index){
    int smallest = index;
    int left = index * 2 + 1;
    int right = index * 2 + 2;
    if(left < heap->size && heap->nodes[left]->weight < heap->nodes[smallest]->weight){
        smallest = left;
    }
    if(right < heap->size && heap->nodes[right]->weight < heap->nodes[smallest]->weight){
        smallest = right;
    }
    if(smallest != index){
        swap(&heap->nodes[index], &heap->nodes[smallest]);
        minHeapify(heap, smallest);
    }
}

Node *extractMin(MinHeap *heap){
    Node *node = heap->nodes[0];
    heap->nodes[0] = heap->nodes[heap->size - 1];
    heap->size--;
    minHeapify(heap, 0);
    return node;
}

void insertMinHeap(MinHeap *heap, Node *node){
    heap->size++;
    int i = heap->size - 1;
    while(i > 0 && node->weight < heap->nodes[(i - 1) / 2]->weight){
        heap->nodes[i] = heap->nodes[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    heap->nodes[i] = node;
}

void buildMinHeap(MinHeap *heap){
    int n = heap->size - 1;
    for(int i = (n - 1) / 2; i >= 0; i--){
        minHeapify(heap, i);
    }
}

Node *buildHuffmanTree(int *values, int *weights, int n){
    MinHeap *heap = createMinHeap(n);
    for(int i = 0; i < n; i++){
        Node *node = createNode(values[i], weights[i]);
        insertMinHeap(heap, node);
    }
    buildMinHeap(heap);
    while(heap->size > 1){
        Node *left = extractMin(heap);
        Node *right = extractMin(heap);
        Node *parent = createNode(left->value < right->value ? left->value : right->value, left->weight + right->weight);
        parent->left = left;
        parent->right = right;
        insertMinHeap(heap, parent);
    }
    return extractMin(heap);
}

void printCodes(Node *root, int *arr, int top){
    if(root->left){
        arr[top] = 0;
        printCodes(root->left, arr, top + 1);
    }
    if(root->right){
        arr[top] = 1;
        printCodes(root->right, arr, top + 1);
    }
    if(!root->left && !root->right){
        printf("%d: ", root->value);
        for(int i = 0; i < top; i++){
            printf("%d", arr[i]);
        }
        printf("\n");
    }
}

void huffmanCoding(int *values, int *weights, int n){
    Node *root = buildHuffmanTree(values, weights, n);
    int arr[n];
    int top = 0;
    printCodes(root, arr, top);
}

int main(){
    int n;
    scanf("%d", &n);
    int values[n];
    int weights[n];
    for(int i = 0; i < n; i++){
        scanf("%d%d", &values[i], &weights[i]);
    }
    huffmanCoding(values, weights, n);
    return 0;
}