单独写出数组形式哈夫曼树 求带权长度的函数

假设有 $n$ 个权值 $w_1, w_2, \cdots, w_n$，它们构成的哈夫曼树的带权路径长度为 $WPL$。我们可以使用数组来表示哈夫曼树，具体方法如下：

1. 创建一个长度为 $2n-1$ 的数组 $huff$，用来存储这棵哈夫曼树的所有节点。
2. 将权值 $w_i$ 存储在数组的前 $n$ 个位置上，即 $huff[0] = w_1, huff[1] = w_2, \cdots, huff[n-1] = w_n$。
3. 从数组的第 $n$ 个位置开始，存储哈夫曼树的非叶子节点。假设节点 $i$ 的左子节点为 $2i+1$，右子节点为 $2i+2$，父节点为 $\lfloor\frac{i-1}{2}\rfloor$，则节点 $i$ 的权值为其左右子节点权值之和，即 $huff[i] = huff[2i+1] + huff[2i+2]$。

在上述数组表示方法的基础上，我们可以编写求带权路径长度 $WPL$ 的函数。具体实现如下：

int getWPL(int* huff, int n) {
    int wpl = 0;
    for (int i = n; i < 2 * n - 1; i++) {
        int parent = (i - 1) / 2;
        wpl += huff[i] * (i % 2 == 0 ? parent - i / 2 + n : i / 2 - parent);
    }
    return wpl;
}

其中，变量 $wpl$ 用来存储带权路径长度，变量 $parent$ 用来存储节点 $i$ 的父节点。在循环中，我们遍历所有的非叶子节点，计算它们到根节点的路径长度并累加到 $wpl$ 中。具体计算方法如下：

1. 如果节点 $i$ 是其父节点的左子节点，则它到根节点的路径长度为 $i$ 到根节点路径长度加上节点 $i$ 的权值。
2. 如果节点 $i$ 是其父节点的右子节点，则它到根节点的路径长度为 $i$ 到根节点路径长度加上节点 $i$ 的权值乘以 $i$ 到根节点路径上左子节点的个数。

最终，函数返回变量 $wpl$，即哈夫曼树的带权路径长度。