上篇描写叙述了哈夫曼编码问题的基本描写叙述以及建造一个哈夫曼树的过程分析，那么当算法已经描写叙述清楚之后，我们要怎么样来实现

代码呢？或者说，给你一些带有权值的叶子节点，要怎么样利用程序高速算出所相应的哈夫曼树的带权路径WPL呢？

我们首先回想一下上篇讲到的那个问题：

比如有这一个字符串“good good study day day up”，如今我们要对字符串进行哈夫曼编码，该字符串一共同拥有 26 个字符，10 种字符。我们首先统计出每一个字符的频率，然后按从大到小顺序排列例如以下（第二列的字符是空格）：

最后，我们依据每一个字符出现的频率，建造出了这种一棵哈夫曼树：

然后根结点到每一个叶子结点的路径便是其相应字母的编码了。于是我们能够得到：

然后就是计算一下哈夫曼树的带权路径长度 WPL。也就是每一个叶子节点的权值乘以到根的距离（即每一个叶子节点的深度，在这个样例中根节点为第0层）结果之和。

WPL = 5 * 2 + 5 * 3 + 4 * 3 + 3 * 3 + 2 * 4 + 2 * 4 + 2 * 4 + 1 * 4 + 1 * 4 + 1 * 4 = 82。

算法描写叙述得很清楚了，那么我们思考这样一个问题，要怎么将详细的算法实现成对应代码呢？是否模拟上述过程，每次都是取当中权值最小的两个节点呢？这种话在数据量较小的情况下是能够实现的，可是假设当数据量比較大的时候。比方说节点数到达10^6以上时。那么每取两个节点，增加新的节点后就要又一次排序一次，然后在整棵哈夫曼树建立完毕之后，再依据每一个叶节点的深度以及权值。计算整棵哈夫曼树的带权路径WPL，可是这种话会因为时间复杂度过大而无法在短时间内执行出程序结果。

那么问题来了。我们不用这样的方法去计算WPL，还有其它的办法吗？

首先我们来看这棵构造好的哈夫曼树：

为了简便起见。我们从树的左边開始考虑。即B,E,F节点。

对于节点B，其深度为3。权值为5。那么其带权路径长度为5*3 = 15。

那么我们再看一下节点B的父亲节点，其权值为9，是由权值为4和权值为5的节点B构造而成，那么即是9 = 4 + 5；

相同的再往上一层，节点B的爷爷节点，其权值为16，是由权值为9和权值为7的节点构造而成，而权值为9的节点的构造前面已经说明，则有16 = 4 + 5 + 7；

再往上一层就到根节点了。

那么到这里我们能够看到，节点B的父亲节点和爷爷节点的组成部分都有节点B的“功劳”。即节点B的权值是其另外两个的“组成部分”。那么节点B的带权路径长度即为其到根节点路径上（不包括根节点）。与其（或者说是与其父节点。爷爷节点等）有父子关系的节点抽取出节点B的组成部分（包括节点B本身），再所有相加。这种话就得到了节点B的带权路径长度为5 + 5 + 5 = 15；

相同的。节点E,F依照相同的方法进行推导。

所以我们从上面的分析得出：

每一个带权叶节点到根节点的带权路径长度等于其到根节点路径上全部节点的包括该带权叶节点权值组成部分之和。

因此，最后我们推导出，全部叶节点，即整棵哈夫曼树的带权路径长度 WPL即为：

除了根节点以外。全部节点的权值之和。

如上图哈夫曼树的带权路径长度 WPL即为：

WPL = 16 + 10 + 9 + 7 + 5 + 5 + 4 + 5 + 3 + 4 + 2 + 3 + 2 + 2 + 2 + 1 + 1 + 1 = 82

有了这种推断之后，我们便非常easy计算出一颗哈夫曼树的带权路径WPL了。

因此我们能够借助一个叫做优先队列的数据结构，而优先队列的实现往往是借助于二叉堆的结构实现。在这里我们要实现的是小根堆的数据结构。一開始的时候，我们能够将全部的节点一个一个的压入队列中。每次有节点入队，队列都会进行自调整，使其保持一个小根堆的状态。当全部的节点全部入队之后。这时候我们依据以上推导出来的结论，每次取两个权值最小的节点。将其值计算之后，然后再将两个节点权值之和的节点压入队列中，直到队列中仅仅剩下一个节点（即根节点），跳出循环体。输出最后的答案。

即整棵哈夫曼树的带权路径WPL。

完整代码实现（C++版，非STL）：

#include
     
      using namespace std;class Heap {private:    int *data, size;public:    Heap(int length_input) {        data = new int[length_input];        size = 0;    }    ~Heap() {        delete[] data;    }    void push(int value) {        data[size] = value;        int current = size;        int father = (current - 1) / 2;        while (data[current] < data[father]) {            swap(data[current], data[father]);            current = father;            father = (current - 1) / 2;        }        size++;    }    int top() {         return data[0];    }    void update(int pos, int n) {        int lchild = 2 * pos + 1, rchild = 2 * pos + 2;        int max_value = pos;        if (lchild < n && data[lchild] < data[max_value]) {            max_value = lchild;        }        if (rchild < n && data[rchild] < data[max_value]) {            max_value = rchild;        }        if (max_value != pos) {            swap(data[pos], data[max_value]);            update(max_value, n);        }    }    void pop() {        swap(data[0], data[size - 1]);        size--;        update(0, size);    }    int heap_size() {        return size;    }};int main() {    int n,value,ans = 0;    cin >> n;    Heap heap(n);     //表示队列中的元素的上限    for(int i = 1;i <= n;++i){        cin >> value;        heap.push(value);    }    if(n==1){        ans = ans + heap.top();            }    while(heap.heap_size() > 1){        int a = heap.top();                heap.pop();        int b = heap.top();         heap.pop();        ans += a + b;        heap.push(a+b);    }    cout << ans << endl;    return 0;}
     

完整代码实现（C++版。STL优先队列实现）：

#include
     
      #include
      
       #include
       
        using namespace std;int main(){    int num[10];    priority_queue 
        
         
          ,greater 
          
            > que; printf("叶节点的权值分别为:\n"); for(int i = 0;i < 10;++i){ scanf("%d",&num[i]); que.push(num[i]); } int ans = 0; while(que.size() > 1){ int a = que.top(); que.pop(); int b = que.top(); que.pop(); ans += a + b; que.push(a + b); } printf("所相应的哈夫曼树的带权路径长度WPL = %d\n",ans); return 0;}
          
         
        
       
      
     

如有错误，还请指正，O(∩_∩)O谢谢