问题描述 给定n个互不相同的整数，以及这些整数出现的次数。 以每个整数出现的次数作为权值，构造一颗哈夫曼树。 求哈夫曼树的加权路径长度。 输入 输入第一行是一个正整数n(0<n<100000)。接下来总共n行。 每行两个整数v和w，v表示整数值，w表示整数v出现的次数。(0<w<=100) 输出 输出一个整数，即哈夫曼树的带权路径长度。c语言代码

以下是C语言代码实现：

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

#define MAX_N 100000

struct Node {
    int val, freq;
    struct Node *left, *right;
};

struct MinHeap {
    int size;
    struct Node **arr;
};

struct Node *newNode(int val, int freq) {
    struct Node *node = (struct Node*) malloc(sizeof(struct Node));
    node->val = val;
    node->freq = freq;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct MinHeap *createMinHeap(int capacity) {
    struct MinHeap *minHeap = (struct MinHeap*) malloc(sizeof(struct MinHeap));
    minHeap->size = 0;
    minHeap->arr = (struct Node**) malloc(capacity * sizeof(struct Node*));
    return minHeap;
}

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

void minHeapify(struct MinHeap *minHeap, int index) {
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    if (left < minHeap->size && minHeap->arr[left]->freq < minHeap->arr[smallest]->freq) {
        smallest = left;
    }
    if (right < minHeap->size && minHeap->arr[right]->freq < minHeap->arr[smallest]->freq) {
        smallest = right;
    }
    if (smallest != index) {
        swapNodes(&minHeap->arr[smallest], &minHeap->arr[index]);
        minHeapify(minHeap, smallest);
    }
}

int isSizeOne(struct MinHeap *minHeap) {
    return minHeap->size == 1;
}

struct Node *extractMin(struct MinHeap *minHeap) {
    struct Node *temp = minHeap->arr[0];
    minHeap->arr[0] = minHeap->arr[minHeap->size - 1];
    --minHeap->size;
    minHeapify(minHeap, 0);
    return temp;
}

void insertMinHeap(struct MinHeap *minHeap, struct Node *node) {
    ++minHeap->size;
    int i = minHeap->size - 1;
    while (i && node->freq < minHeap->arr[(i - 1) / 2]->freq) {
        minHeap->arr[i] = minHeap->arr[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    minHeap->arr[i] = node;
}

struct Node *buildHuffmanTree(int vals[], int freqs[], int n) {
    struct Node *left, *right, *top;
    struct MinHeap *minHeap = createMinHeap(n);
    for (int i = 0; i < n; ++i) {
        insertMinHeap(minHeap, newNode(vals[i], freqs[i]));
    }
    while (!isSizeOne(minHeap)) {
        left = extractMin(minHeap);
        right = extractMin(minHeap);
        top = newNode(-1, left->freq + right->freq);
        top->left = left;
        top->right = right;
        insertMinHeap(minHeap, top);
    }
    return extractMin(minHeap);
}

int getDepth(struct Node *root, int val, int depth) {
    if (!root) {
        return -1;
    }
    if (root->val == val) {
        return depth;
    }
    int leftDepth = getDepth(root->left, val, depth + 1);
    if (leftDepth != -1) {
        return leftDepth;
    }
    return getDepth(root->right, val, depth + 1);
}

int main() {
    int n;
    scanf("%d", &n);
    int vals[MAX_N], freqs[MAX_N];
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &vals[i], &freqs[i]);
    }
    struct Node *root = buildHuffmanTree(vals, freqs, n);
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += freqs[i] * getDepth(root, vals[i], 0);
    }
    printf("%d\n", sum);
    return 0;
}

代码的核心是哈夫曼树的构建和加权路径长度的计算。首先，我们需要定义一个结构体来表示哈夫曼树的节点，其中包括节点的值、出现频率以及左右子节点。其次，我们需要定义一个最小堆来维护出现频率最小的节点。然后，我们需要实现最小堆的插入、删除最小元素以及堆化等操作。接着，我们需要实现哈夫曼树的构建，具体过程是不断取出最小频率的两个节点，并将它们合并成一个新节点，直到堆中只剩下一个节点为止。最后，我们需要计算哈夫曼树的加权路径长度，具体过程是对于每个节点，计算其到根节点的距离乘以该节点出现的频率，然后将所有节点的贡献相加即可。

时间复杂度：O(nlogn)

空间复杂度：O(n)