首先需要明确哈弗曼树的几个概念：

• 权：节点的值；出现的概率的大小

• 节点路径长度：从0开始，根节点长度为0，根节点的子节点路径长度为1，以此类推

• 树的路径长度：所有叶节点路径长度之和

• 节点带权路径长度：该节点路径长度*该节点权

• 树的带权路径长度：所有节点路径长度*该节点权

这题的目标是求树的带权路径长度。

计算树的带权路径长度，本来是计算是所有节点深度*权的和，但是这里通过迭代累加，也能实现乘法的效果。在最下面的节点，累加次数最多，即相当于乘的数值最大。

关键代码：

            //取出两个权最小的
            int num1 = (q.top()).x;
            q.pop();
            int num2 = (q.top()).x;
            q.pop();
            //权相加，生成新的节点，并放入队列
            node new_node;
            new_node.x = num1 + num2;
            //cout << new_node.x << endl;
            q.push(new_node);
            //结果累加。本来树的带权路径计算是所有节点深度*权的和，但是这里通过
            //几层累加，也能实现乘法的效果。在最下面的节点，累加次数最多，即相当于
            //乘的数值最大
            ans += num1 + num2;

最后输出ans就是结果。

因为需要每次选取节点集中最小的两个节点构成一课数，因此选用优先级队列。

两种排序方式：

• 重载运算符
• 因为这里节点只包含一个int值，因此也可以使用自带的greater完成升序排序。less是降序。

本代码两种方法均实现，起到一个复习的效果。注释掉了greater的。

代码如下：

// 哈弗曼树，树的带权路径问题
//使用了2种方法来对优先级队...