Huffman树

Huffman树

1、合并果子：

描述：

​ 将若干堆果子合并到一堆，每次可以将任意两堆进行合并。

思路：

​ 每次选取最少的两堆进行合并即可，采用优先队列，即小根堆进行存储所有果子。

代码模板：

priority_queue<int, vector<int>, greater<int>> heap; //小根堆定义
    
for (int i = 0; i < n; i ++)
{
    int x;
    cin >> x;
    heap.push(x); //入堆
}

while (heap.size() > 1)
{
    int a = heap.top(); heap.pop();	//取出堆顶并剔除
    int b = heap.top(); heap.pop();
    res += a + b;
        
    heap.push(a + b);	//将合并得到的新堆加入堆中
}

注意：

​ 很容易忽略的一点是，没有将合并得到的新堆加入堆中。