[编程笔记]-Huffman_Tree(Greedy)哈夫曼树（贪心）

前言

本文并非对数据结构哈夫曼树的详细讲解（不然就会放进数据结构里了），而是对贪心问题中哈夫曼树有关思想题目的讲解。

还没创建hhh

例题

对没有概念（贪心算法还能有概念？就是每次找局部最优解嘛；哈夫曼树详见哈夫曼树页面），直接给例题。
AcWing148-合并果子

还记得石子合并吗？它们两道题的区别是，合并果子不用相邻的两堆。

毫无疑问，最优解肯定是每次选最小的两堆进行合并，以消耗最小的能量。

这就让我们不由想到了哈夫曼树思想。

假设把合并过程想成一棵树，两堆果子合并之后的新堆是原来两堆果子的父节点，毫无疑问，每堆果子消耗的能量就是重量*合并次数，也就是权重*深度。

那么，我们就会想到尽量减少深度——构建完全二叉树，深度越深的权重越小——权重小的尽量放在更深层。

这样，我们就想好了思路——构建一棵哈夫曼树。

但是，以上只是思想，我们不会真的去构造一棵哈夫曼树，实现方法很简单。

对于当前所有堆，找出最小的两个堆合并，然后把合并出的新堆放回去，结果加上新堆的大小即可。

毫无疑问，还是用小根堆实现。

#include<bits/stdc++.h>
using namespace std;

int n,a;
int ans;
priority_queue<int, vector<int>, greater<int> > pq; 

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a;
        pq.push(a);
    }
    while(pq.size()>1){
        int a=pq.top();pq.pop();
        int b=pq.top();pq.pop();
        pq.push(a+b);
        ans+=a+b;
    }
    cout<<ans;
    return 0;
}

这，就是贪心的毒瘤魅力所在

完结撒花o(￣︶￣)o