多支持咱一起进步

一、priority_queue的介绍二、为什么priority_queue不像stack和queue一样使用deque作为其底层存储数据的容器呢三、priority_queue的常见操作四、模拟实现priority_queue4.1

构造函数4.2

priority_queue是一个容器适配器默认使用vector作为其底层存储数据的容器priority_queue在vector上使用了堆heap的算法将vector中元素构造堆的结构因此priority_queue就是堆。

默认情况下是大堆。

如何构造成小堆在【仿函数】会讲解到

二、为什么priority_queue不像stack和queue一样使用deque作为其底层存储数据的容器呢

在堆中插入新元素时为了保持堆的特性大堆/小堆。

则需要通过不断地比较和移动元素来完成。

vector作为一个连续的内存块可以更高效地进行元素的插入操作。

相比之下deque在插入和删除操作时需要考虑在数组的两端进行操作头部和尾部并且要进行元素的移动操作使得时间复杂度稍高于vector。

尽管deque在头部和尾部插入/删除操作上有一些优势但对于优先级队列这种需要频繁访问和处理最高优先级元素的场景来说vector更加合适

弹出pop元素若要得到堆顶的元素需要将堆顶元素与最后一个元素交换并重新调整堆使其满足堆的性质。

同样由于vector是连续存储的这个操作也可以更高效地进行。

deque的存储空间不是连续的因此在使用时需要更多的空间可能会导致空间的浪费。

#include

pq;pq.push(3);pq.push(5);pq.push(1);pq.push(4);pq.push(0);while

(!pq.empty()){cout

_con[parent]){swap(_con[child],

_con[parent]);parent

InputIteratorpriority_queue(InputIterator

first,

last){_con.push_back(*first);first;}//

建堆操作

i--){AdjustDown(i);}}private:container

_con;};

}插入一个数据由于还要保持大堆的性质如果尾插的结点要比其父结点大就要进行

向上调整

仿函数函数对象是一种能够被像函数一样调用的对象。

它通常是一个类或者结构体重载了函数调用运算符

operator(),通过重载这个运算符我们可以将对象当作函数来使用实现了类似函数的行为。

仿函数可以有自己的状态和成员变量因此可以在多次调用中保持状态。

它可以接受参数并返回一个值。

struct

operator()使得add对象可以像函数一样被调用。

通过add(3,

中仿函数是一种灵活且强大的编程工具常常用于算法和标准库中的函数对象。

#include

那么如果想排降序可以将less替换成greater这也是库里提供的其作用是用于大于不等式比较的函数对象类

#include

_con[child])){swap(_con[child],

_con[parent]);parent

_con[child])){swap(_con[child],

_con[parent]);child

InputIteratorpriority_queue(InputIterator

first,

last){_con.push_back(*first);first;}//

建堆操作

}注意如果在priority_queue中放自定义类型的数据用户需要在自定义类型中提供或者的重载。

namespace

_con[child])){swap(_con[child],

_con[parent]);parent

_con[child])){swap(_con[child],

_con[parent]);child

InputIteratorpriority_queue(InputIterator

first,

last){_con.push_back(*first);first;}//

建堆操作