从合并果子到哈夫曼编码：用C++优先队列（priority_queue）搞定经典贪心算法-平芜编程栈

从合并果子到哈夫曼编码：用C++优先队列（priority_queue）搞定经典贪心算法

贪心算法在计算机科学中扮演着重要角色，它通过每一步的局部最优选择来达到全局最优解。合并果子问题作为贪心算法的经典案例，不仅能够帮助我们理解贪心策略的精髓，还能自然过渡到哈夫曼编码这一实际应用场景。本文将带你深入理解这一算法思想，并掌握如何用C++的优先队列高效实现。

1. 贪心算法与合并果子问题

贪心算法的核心思想是"每一步都做出当前看起来最好的选择"。在合并果子问题中，我们需要将多堆果子合并成一堆，每次合并两堆，消耗的体力等于两堆果子的重量之和。目标是找到使总体力消耗最小的合并顺序。

为什么贪心策略在这里有效？关键在于每次合并都会将当前结果累加到总消耗中。如果我们总是先合并最小的两堆，那么这些小的数字被累加的次数就会最少。这与哈夫曼编码中频率低的字符获得较长编码的原理如出一辙。

考虑以下例子：

果子堆：1, 2, 9
贪心策略合并顺序：
1. 合并1和2 → 消耗3，新堆：3, 9
2. 合并3和9 → 消耗12，总消耗：3+12=15
非最优策略：
1. 合并2和9 → 消耗11，新堆：1, 11 2.合并1和11 → 消耗12，总消耗：11+12=23

显然，贪心策略得到了更优的结果。这种策略之所以有效，是因为它最小化了较大数字被重复计算的次数。

2. C++优先队列的实现

C++标准模板库(STL)中的priority_queue是实现合并果子问题的理想工具。默认情况下，priority_queue实现的是最大堆，但我们可以通过自定义比较器来实现最小堆。

2.1 基本实现

#include <iostream> #include <queue> #include <vector> using namespace std; int main() { int n, weight; cin >> n; // 定义最小优先队列 priority_queue<int, vector<int>, greater<int>> min_heap; for(int i = 0; i < n; i++) { cin >> weight; min_heap.push(weight); } int total_cost = 0; while(min_heap.size() > 1) { int first = min_heap.top(); min_heap.pop(); int second = min_heap.top(); min_heap.pop(); int combined = first + second; total_cost += combined; min_heap.push(combined); } cout << total_cost << endl; return 0; }

2.2 性能分析

优先队列的底层通常使用二叉堆实现，其时间复杂度如下：

插入操作(push): O(log n)
取出最小元素(pop): O(log n)
查看最小元素(top): O(1)

对于n堆果子，我们需要进行n-1次合并，每次合并涉及2次取出和1次插入操作，因此总时间复杂度为O(n log n)，这对于n≤10000的问题规模是完全可行的。

提示：在实际编程竞赛中，使用STL的优先队列通常比手动实现堆更不容易出错，除非有特殊的性能优化需求。

3. 手动实现最小堆

虽然STL的优先队列很方便，但理解其底层实现有助于我们更深入地掌握数据结构。下面我们来看如何手动实现一个最小堆来解决合并果子问题。

3.1 堆的基本操作

class MinHeap { private: vector<int> heap; void upAdjust(int index) { while(index > 1 && heap[index] < heap[index/2]) { swap(heap[index], heap[index/2]); index /= 2; } } void downAdjust(int index) { int child = index * 2; while(child <= heap.size() - 1) { if(child + 1 <= heap.size() - 1 && heap[child+1] < heap[child]) { child++; } if(heap[child] < heap[index]) { swap(heap[child], heap[index]); index = child; child = index * 2; } else { break; } } } public: MinHeap() { heap.push_back(0); // 占位，使索引从1开始 } void push(int val) { heap.push_back(val); upAdjust(heap.size() - 1); } int top() { return heap[1]; } void pop() { heap[1] = heap.back(); heap.pop_back(); downAdjust(1); } int size() { return heap.size() - 1; } };

3.2 使用手动堆解决问题

int main() { int n, weight; cin >> n; MinHeap min_heap; for(int i = 0; i < n; i++) { cin >> weight; min_heap.push(weight); } int total_cost = 0; while(min_heap.size() > 1) { int first = min_heap.top(); min_heap.pop(); int second = min_heap.top(); min_heap.pop(); int combined = first + second; total_cost += combined; min_heap.push(combined); } cout << total_cost << endl; return 0; }

手动实现堆虽然代码量较大，但它让我们能够：

更灵活地控制堆的行为
在特定场景下进行性能优化
深入理解优先队列的工作原理

4. 从合并果子到哈夫曼编码

合并果子问题实际上是哈夫曼编码问题的简化版本。哈夫曼编码是一种用于数据压缩的算法，它通过给出现频率高的字符分配较短的编码，给出现频率低的字符分配较长的编码，从而实现数据的高效压缩。

4.1 哈夫曼编码的基本原理

统计字符出现的频率
将每个字符及其频率视为一个节点
重复以下步骤直到只剩一个节点：
- 选择频率最低的两个节点
- 合并它们，新节点的频率为两者之和
- 将新节点加入集合
从根节点开始，给左分支赋0，右分支赋1，得到每个字符的编码

4.2 实现哈夫曼编码

#include <iostream> #include <queue> #include <vector> #include <string> #include <unordered_map> using namespace std; struct HuffmanNode { char ch; int freq; HuffmanNode *left, *right; HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {} }; struct Compare { bool operator()(HuffmanNode* a, HuffmanNode* b) { return a->freq > b->freq; } }; void generateCodes(HuffmanNode* root, string code, unordered_map<char, string>& codes) { if(!root) return; if(!root->left && !root->right) { codes[root->ch] = code; return; } generateCodes(root->left, code + "0", codes); generateCodes(root->right, code + "1", codes); } unordered_map<char, string> buildHuffmanTree(const unordered_map<char, int>& freq) { priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> min_heap; for(auto& pair : freq) { min_heap.push(new HuffmanNode(pair.first, pair.second)); } while(min_heap.size() > 1) { HuffmanNode* left = min_heap.top(); min_heap.pop(); HuffmanNode* right = min_heap.top(); min_heap.pop(); HuffmanNode* combined = new HuffmanNode('\0', left->freq + right->freq); combined->left = left; combined->right = right; min_heap.push(combined); } unordered_map<char, string> codes; generateCodes(min_heap.top(), "", codes); return codes; }