题解 | #哈夫曼树#

哈夫曼树

https://www.nowcoder.com/practice/162753046d5f47c7aac01a5b2fcda155

需要把所有元素值的负数存入优先队列,然后每次top出2个最大的,也就是原叶子结点中2个权值最小的。

top完别忘pop,再把新节点push进优先队列,用wpl累加,最后输入wpl时别忘再乘回来-1

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;


int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        priority_queue<int> myPriorityQueue;
        int wpl = 0;
        for (int i = 0; i < n; i++) {
            int num;
            cin >> num;
            //乘-1再入优先队列,即可巧妙运用默认的大根堆实现小根堆
            myPriorityQueue.push(num * (-1));
        }

        //wpl不断累加,退出条件是优先队列中只有一个根节点
        while (myPriorityQueue.size() > 1) {
            int small1 = myPriorityQueue.top();
            myPriorityQueue.pop();
            int small2 = myPriorityQueue.top();
            myPriorityQueue.pop();
            int newWeight = small1 + small2;
            myPriorityQueue.push(newWeight);//别忘新节点入队

            wpl = wpl + small1 + small2;
        }
        printf("%d\n",wpl*(-1));
    }
}
全部评论

相关推荐

05-29 09:02
门头沟学院 Java
点赞 评论 收藏
分享
06-18 13:28
已编辑
门头沟学院 Web前端
爱睡觉的冰箱哥:《给予你300的工资》,阴的没边了
点赞 评论 收藏
分享
07-07 11:33
江南大学 Java
已经在暑假实习了&nbsp;,没有明确说有hc,纠结实习到八月份会不会有点影响秋招毕竟感觉今年好多提前批
程序员小白条:92的话准备提前批,其他没必要,没面试机会的,而且你要准备充分,尤其八股和算法题
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务