C++小根堆做优先队列
时间: 2024-10-27 13:08:49 浏览: 15
C++利用小根堆实现霍夫曼树
在C++中,小根堆(也称为最小堆)是一种常用的数据结构,用于实现优先队列。优先队列的特点是可以快速获取当前“优先级最高”的元素,常用于需要处理优先级任务的情况,如任务调度、事件驱动系统等。
小根堆是一个完全二叉树,满足每个节点都小于或等于其子节点的值(对于最小堆)。插入新元素时,将其添加到堆顶,然后调整堆结构以保持性质;删除堆顶元素(即当前优先级最高的元素)后,将堆底的元素替换到堆顶,并再次调整堆。
以下是使用C++ STL库中的`priority_queue`实现优先队列的基本步骤:
```cpp
#include <queue>
using namespace std;
// 创建一个最小堆作为优先队列
priority_queue<int, vector<int>, greater<int>> pq; // 使用greater模板函数指定升序排序
// 插入元素
pq.push(5); // 元素5的优先级较高
pq.push(3);
pq.push(7);
// 获取并移除优先级最高的元素
int topPriority = pq.top(); // 返回当前最大值(最小优先级)
pq.pop(); // 删除当前元素
阅读全文