题解 | 【模板】哈夫曼编码

【模板】哈夫曼编码

https://www.nowcoder.com/practice/4c0419eb07c840ca8402e4f2a52cfd49

#include <iostream>
#include <queue>
using namespace std;
typedef long long ll ;
int main() {
    int n;
    cin >> n;
    priority_queue<ll, vector<ll> , greater<ll> > q;
    for(int i = 0;i < n;i ++){
        ll x;
        cin >> x;
        q.push(x);
    }
    ll sum = 0;
    while(q.size() > 1){
        ll t1 = q.top();
        q.pop();
        ll t2 = q.top();
        q.pop();
        ll t = t1 + t2;
        q.push(t);
        sum += t;
    }
    cout << sum;
}
// 64 位输出请用 printf("%lld")
//贪心算法(Greedy Algorithm):

//哈夫曼编码的构建过程是一个典型的贪心算法应用。每次选择当前频率最小的两个节点合并,直到只剩一个节点。

//优先队列(Priority Queue)或最小堆(Min-Heap):

//高效实现哈夫曼编码的关键是使用优先队列(通常是最小堆)来动态获取当前频率最小的两个节点。

//需要熟悉优先队列的操作(如插入、提取最小值等)及其时间复杂度。

全部评论

相关推荐

06-12 16:00
天津大学 Java
牛客30236098...:腾讯坏事做尽,终面挂是最破防的 上次被挂了后我连简历都不刷了
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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