贪心，优先队列，小根堆一口气学会

### 贪心算法基本概念

贪心算法是一种通过一系列的选择来解决问题的方法，在每一步选择中都做出当前状态下最好的选择，期望最终能够得到全局最优解。这种策略并不总是能获得最优化的结果，但在某些情况下确实可以找到最佳解决方案[^1]。

对于最小生成树问题而言，如果一个无向加权连通图被划分为两个集合A和B，那么连接这两个集合之间权重最小的边必定会成为构成最小生成树的一部分。这一特性使得Prim算法能够在构建过程中始终选取局部最优方案从而达到整体最优效果。

### 优先队列与小根堆介绍

#### 优先队列定义
优先队列是一个抽象数据类型，它类似于常规队列或栈的数据结构，但是其中每个元素都有一个预先关联好的“优先级”。当访问、移除元素时，最先处理的是具有最高优先级别的那个元素；而插入操作则按照新加入项的实际价值自动调整其位置以维持内部顺序不变。

#### 小根堆概述
小根堆（Min Heap）是一类特殊的完全二叉树形式实现的优先队列，满足如下条件：

- 对于任意节点i (除了根)，`heap[i] >= heap[parent(i)]` 成立；
- 新增元素通常放置到最后一层最右侧的位置上，并向上浮动直至恢复上述性质；
- 删除最小值后需将最后一个叶子替换至顶部并向下沉降直到重新符合规则。

这些特点让小根堆非常适合用来高效管理动态变化中的极值查询需求场景下作为底层支撑工具之一[^2]。

### 使用C++ STL库中的`priority_queue`

在实际编程实践中可以直接利用标准模板库提供的容器适配器——`std::priority_queue<T>` 来快速搭建起基于最大/最小堆逻辑运作机制下的先进先出(FIFO) 或者 后进先出(LIFO) 的自适应型序列化存储空间。默认配置下它是大顶堆行为模式，不过可以通过指定比较函数参数轻松切换成相反形态的小顶堆版本。

#include <queue>
// 定义一个小根堆
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

### 实现哈夫曼编码案例分析

考虑到字符频率分布情况各异可能导致不同长度前缀码表的存在，因此采用贪心思路配合优先队列技术可有效降低计算成本。具体做法是在初始化阶段把所有可能出现过的字母及其对应的出现次数封装成一个个独立对象存入到由小根堆维护着的一组候选列表里头去；之后不断取出概率最低两位组合起来形成新的综合体再放回原处继续参与后续竞争过程...如此这般循环往复直至最后只剩下一个超级节点为止。此时从这棵满二叉树顶端到底部路径所经过各分支方向上的0/1标记串接而成的就是相应叶节点代表的那个特定符号应该分配给它的唯一标识符了。