priority_queue（优先队列-让数据有序排列）

大风往北吹 2024-11-11 10:40:36 726次浏览

最佳答案优先队列-让数据有序排列优先队列是一种可以让数据按照某种规则有序排列的数据结构。它的基本操作包括：插入一个元素、弹出最外层元素。最外层元素是根据排序规则来决定的，所...

优先队列-让数据有序排列

优先队列是一种可以让数据按照某种规则有序排列的数据结构。它的基本操作包括：插入一个元素、弹出最外层元素。最外层元素是根据排序规则来决定的，所以它能实现快速的查找、插入和删除操作。

1.基本用法

优先队列是一个大顶堆或者是小顶堆。

在C++中，STL提供了一个优先队列优先队列属于容器适配器，是在队列的基础上加了一些运算符。

priority_queue（优先队列-让数据有序排列）

其运算规则定义在每个优先队列之中，是第一缺省的值是最大值。换句话说，以默认规则建立的3中下列值为九个元素的优先队列中，第一个元素的值最大。

```C++priority_queuepq;//建立一个空的优先队列，其默认值是大堆的。通过begin()和end()可以对任何具有随机访问能力的容器以及数组来构造优先队列pq.push(3);//插入元素pq.push(2);pq.push(5);pq.push(1);cout<上述代码中，内部容器是一个vector容器（用于保存优先队列元素），默认形式是大顶堆。这意味着最大的元素总是在队列的前面。

priority_queue（优先队列-让数据有序排列）

2.用户自定义元素的优先队列

以上实例中，元素的优先级是由它们的标准比较运算符定义的。当使用int，double等数据类型时，标准比较运算符尽管无法更改，但它们按递增顺序进行排列。

如果您要使用自己的类来创建队列，则必须定义在类中运算符()以便比较其元素的优先级。运算符应该采用const修饰符，则它将是一个常量，并且不会修改对象。以下是一个例子：

priority_queue（优先队列-让数据有序排列）

```C++//自定义坐标的结构体structCoordinate{intx;inty;};//优先队列的比较函数structcmp{booloperator()(constCoordinate&lhs,constCoordinate&rhs)const{returnlhs.x+lhs.y,cmp>pq;pq.push({0,1});pq.push({1,0});pq.push({0,0});pq.push({1,1});cout<该代码使用了一个自定义的运算符，按照Coordinate类中定义的运算符进行比较。该运算符使用总和来比较每个坐标的优先级，先比较两个x的和，然后再与y的和进行比较。