堆与优先队列
2025-06-21 17:15:49
发布于：上海
7阅读
0回复
0点赞
堆与优先队列
1. 堆数据结构
1.1 基本性质
- 完全二叉树结构
- 两种类型：
- 大根堆：父节点 ≥ 子节点
- 小根堆：父节点 ≤ 子节点
- 数组存储方式：
- 父节点i → 左子节点：2i
- 父节点i → 右子节点：2i+1
- 子节点i → 父节点：⌊i/2⌋
1.2 时间复杂度
| 操作 | 时间复杂度 |
|---|---|
| 插入 | O(log n) |
| 删除 | O(log n) |
| 查找极值 | O(1) |
2. C++优先队列
2.1 基本概念
- 容器类型：容器适配器（基于堆数据结构实现）
- 默认行为：大顶堆（队首为最大元素）
- 底层容器：默认使用
vector，支持随机访问的容器（如deque）
2.2 核心操作
| 方法 | 功能描述 | 时间复杂度 |
|---|---|---|
push(x) |
插入元素并维护堆结构 | O(log n) |
pop() |
删除堆顶元素 | O(log n) |
top() |
访问堆顶元素（不删除） | O(1) |
empty() |
判断队列是否为空 | O(1) |
size() |
返回当前元素数量 | O(1) |
2.3基本声明
#include <queue>
using namespace std;
// 默认大根堆
priority_queue<int> max_heap;
// 小根堆声明
priority_queue<int, vector<int>, greater<int>> min_heap;
# priority_queue（优先级队列）
这里空空如也
有帮助，赞一个