题解 | #哈夫曼树#

哈夫曼树

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));
    }
}
全部评论

相关推荐

嵐jlu:我是山川🐔里🐔🧱的,阿里系简历全过; 你这简历一看就还是半成品啊,没有荣誉经历奖项什么的吗?
投递阿里巴巴集团等公司10个岗位
点赞 评论 收藏
分享
陈逸轩1205:才105 哥们在养生呢
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 11:30
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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