哈夫曼树WPL值的高效计算方法

哈夫曼树WPL值的高效计算方法

引用

CSDN

1.

https://blog.csdn.net/VVVLeHr/article/details/87877439

哈夫曼树（Huffman Tree）是一种带权路径长度最短的二叉树，广泛应用于数据压缩和编码等领域。在哈夫曼树中，WPL（Weighted Path Length）值是一个重要的概念，它表示所有叶子节点的权值与其路径长度的乘积之和。本文将介绍一种计算WPL值的高效方法，并通过具体示例和代码实现来说明其原理和应用。

在计算WPL值的时候，一般采用的方法是用叶子节点的权值乘上其路径长度。但是，实际上在构建哈夫曼树的过程中，我们已经计算过路径长度了。因此，可以采用一种更高效的方法来计算WPL值：

WPL = 哈夫曼树中所有非叶子结点的权值之和

举个例子，构造1 2 2 5 9的哈夫曼树并计算其WPL值：

上图即为构建出来的HuffmanTree，

使用传统的计算方法：

WPL= （1+2）* 4 + 3 * 2 + 5 * 2 + 9 =37

这个是使用权值乘以路径长度，但是在计算其中非叶子节点的权值时，3 包含了1个(1+2)，5是用3得来的，所以也包含了一个(1+2)，同理10和19也是一样，所以如果直接将所有非叶子节点相加

WPL = 3 + 5 + 10 + 19 = 37。

得到的结果是一样的。这种方法在实际计算中可以省去再次迭代计算路径长度的logn的复杂度。

实际应用

下面是一个实际应用的例子，来自北京邮电大学的复试题：

题目描述

哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。

输入描述:

输入有多组数据。 每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。

输出描述:

输出权值。

输入例子:

5
1 2 2 5 9

输出例子:

37

示例1

输入
5
1 2 2 5 9

输出
37

下面是具体的C++代码实现：

#include <iostream>
#include <queue>
#include <stdlib.h>
#include <stdio.h>
#include <map>
#include <string>
#include <cstdlib>
#include <stack>
#include <vector>
#include <math.h>
#include <algorithm>
#include <typeinfo>
#include <cstring>
using namespace std;
const int maxn = 1003;
int data[maxn];
priority_queue<int ,vector<int> ,greater<int>> q;
int main(int argc, char const *argv[])
{
    int n;
    while(cin>>n){
        while(!q.empty())	q.pop();
        for(int i=0;i<n;i++){
            cin>>data[i];
            q.push(data[i]);
        }
        int ans=0;
        while(q.size()>=2){
            int a=q.top();q.pop();
            int b=q.top();q.pop();
            q.push(a+b);
            ans+=(a+b);
        }
        cout<<ans<<endl;
    }
    return 0;
}

这段代码通过优先队列实现哈夫曼树的构建，并在构建过程中计算WPL值，时间复杂度为O(nlogn)。