题解 | #哈夫曼树#优先队列+迭代求带权路径和

哈夫曼树

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

#include <bits/stdc++.h>
using namespace std;
int main() {
    //迭代求带权路径和
    int n, leaf;
    while (cin >> n) {
        priority_queue<int> q;
        for (int i = 0; i < n; i++) {
            cin >> leaf;
            q.push(-leaf);//存入相反数
        }
        int res = 0;
        while (q.size() > 1) {
            int leaf1 = q.top();
            q.pop();
            int leaf2 = q.top();
            q.pop();
            res = res + leaf1 + leaf2;
            q.push(leaf1 + leaf2);
        }
        cout << -res << endl;
    }

    return 0;
}

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务