贪心算法

定义：贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解

1. 类似于二分，将大集合进行划分，得出最优解所在的小集合
2. 与动态规划的不同: 在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能

贪心算法步骤

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

哈夫曼树

给定 N 个权值作为 N 个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)

实现手段：
通过一个小根堆(priority_queue<int,vector<int>,greater<int>>)，每次取出队列顶部的两个元素进行合并，同时将这两个元素出队，将合并之后得到的新元素入队
直到队列中只剩下一个元素为止

#include <iostream>
#include <queue> // 优先队列头文件

using namespace std;

int n;
priority_queue<int, vector<int>, greater<int>> q; // 大根堆 + 大于号 = 小根堆

int main()
{
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        q.push(x); // 加入节点
    }

    int res = 0; // res: 结果
    while (q.size() > 1) // 模拟哈夫曼树生成过程
    {
        // 挑两个最小的数
        int a = q.top();
        q.pop();
        int b = q.top();
        q.pop();

        res += a + b; // 把他们之和加到答案里
        q.push(a + b); // 合并节点
    }

    cout << res;

    return 0;
}