霍夫曼树

【树的带权路径长度】

设二叉树具有 $n$ 个带权叶结点，从根结点到各叶结点的路径长度与相应叶节点权值的乘积之和称为树的带权路径长度（Weighted Path Length of Tree，WPL）

设 $w_i$ 为二叉树地 $i$ 个叶结点的权值，$l_i$ 为从根结点到第 $i$ 个叶结点的路径长度，则 WPL 计算公式如下：

$$WPL=\sum_{i=1}^nw_il_i$$

如上图所示，其 WPL 计算过程与结果如下：

$$WPL=2*2+3*2+4*2+7*2=4+6+8+14=32$$

【霍夫曼树】

结构

对于给定一组具有确定权值的叶结点，可以构造出不同的二叉树，其中，WPL 最小的二叉树称为霍夫曼树

对于霍夫曼树来说，其叶结点权值越小，离根越远，叶结点权值越大，离根越近，此外其仅有叶结点的度为 $0$，其他结点度均为 $2$

霍夫曼算法

霍夫曼算法用于构造一棵霍夫曼树，算法步骤如下：

1）初始化：由给定的 $n$ 个权值构造 $n$ 棵只有一个根节点的二叉树，得到一个二叉树集合 $F$

2）选取与合并：从二叉树集合 $F$ 中选取根节点权值最小的两棵二叉树分别作为左右子树构造一棵新的二叉树，这棵新二叉树的根节点的权值为其左、右子树根结点的权值和

3）删除与加入：从 $F$ 中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到 $F$ 中

4）重复 2）、3） 步，当集合中只剩下一棵二叉树时，这棵二叉树就是霍夫曼树

【实现】

霍夫曼树的构建

typedef struct HNode {
    int weight;
    HNode *lchild, *rchild;
} *Htree;
Htree createHuffmanTree(int arr[], int n) {
    Htree forest[N];
    Htree root = NULL;
    for (int i = 0; i < n; i++) { //将所有点存入森林
        Htree temp;
        temp = (Htree)malloc(sizeof(HNode));
        temp->weight = arr[i];
        temp->lchild = temp->rchild = NULL;
        forest[i] = temp;
    }

    for (int i = 1; i < n; i++) { //n-1次循环建哈夫曼树
        int minn = -1, minnSub;   //minn为最小值树根下标,minnsub为次小值树根下标
        for (int j = 0; j < n; j++) {
            if (forest[j] != NULL && minn == -1) {
                minn = j;
                continue;
            }
            if (forest[j] != NULL) {
                minnSub = j;
                break;
            }
        }

        for (int j = minnSub; j < n; j++) { //根据minn与minnSub赋值
            if (forest[j] != NULL) {
                if (forest[j]->weight < forest[minn]->weight) {
                    minnSub = minn;
                    minn = j;
                } else if (forest[j]->weight < forest[minnSub]->weight) {
                    minnSub = j;
                }
            }
        }

        //建新树
        root = (Htree)malloc(sizeof(HNode));
        root->weight = forest[minn]->weight + forest[minnSub]->weight;
        root->lchild = forest[minn];
        root->rchild = forest[minnSub];

        forest[minn] = root;    //指向新树的指针赋给minn位置
        forest[minnSub] = NULL; //minnSub位置为空
    }
    return root;
}

WPL 的计算

对于给出 $n$ 个叶结点的权值，计算构成霍夫曼树的 WPL

1）递归实现

typedef struct HNode {
    int weight;
    HNode *lchild, *rchild;
} *Htree;
int getWPL(Htree root, int len) { //递归实现，对于已经建好的霍夫曼树，求WPL 
    if (root == NULL)
        return 0;
    else {
        if (root->lchild == NULL && root->rchild == NULL) //叶节点
            return root->weight * len;
        else {
            int left = getWPL(root->lchild, len + 1);
            int right = getWPL(root->rchild, len + 1);
            return  left + right;
        }
    }
}

2）非递归实现

int getWPL(int arr[], int n) { //对于未建好的霍夫曼树，直接求其WPL
    priority_queue<int, vector<int>, greater<int>> huffman; //小根堆
    for (int i = 0; i < n; i++) 
        huffman.push(arr[i]);
    
    int res = 0;
    for (int i = 0; i < n-1 ; i++) {
        int x = huffman.top();
        huffman.pop();
        int y = huffman.top();
        huffman.pop();
        int temp = x + y;
        res += temp;
        huffman.push(temp);
    }
    return res;
}