2024年4月12日发(作者：)

priority_queue用法 小根堆

priority_queue是STL库中的一个模板类，它被用来实现优先队列，也就是一

个元素集合，每个元素都有一个关键字，可以比较大小，且具有最高优先级的元

素总是最先被访问（出队）。

小根堆：在优先队列中，元素的优先级被定义为元素的大小，小的元素优先级高，

因此，如果想要实现小根堆，只需要定义一个存放元素的数据结构，比较大小的

时候，使用“大于号”（>）进行比较，即将小的元素放在队首（出队），大的元

素放在队尾（入队）。

priority_queue的基本操作：

1.入队：push()

2.出队并返回队首元素：top()

3.出队：pop()

4.判断队列是否为空：empty()

5.求队列中元素的个数：size()

下面是一个小根堆的例子：

c++

#include

#include

using namespace std;

int main() {

priority_queue,greater > q;定义小根堆

int a[] = {54,78,24,65,12,57,93};

for(int i=0;i<7;i++) (a[i]);入队

while(!()) {输出队列中的元素

cout<<()<<" ";

();出队

}

return 0;

}

运行结果：12 24 54 57 65 78 93

这里我们使用了std::greater作为比较的方式，因为priority_queue默认

是大根堆，而我们要实现小根堆，则需要借助greater类。