C++初阶：STL详解（十）——priority_queue的介绍，使用以及模拟实现

✨✨小新课堂开课了，欢迎欢迎~✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：C++：由浅入深篇

小新的主页：编程版小新-CSDN博客

一.priority_queue的介绍

优先级队列被实现为容器适配器，容器适配器就是将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部，并且它的第一个元素总是它所包含的元素中最大的。因为默认情况下priority_queue是大堆。

底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器支持随机访问迭代器访问，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。

二.priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。

注意：默认情况下priority_queue是大堆。

 2.1priority_queue的定义

1.指定定义：

//指定定义
//1.以vector作为底部容器类，内部构建大堆结构
priority_queue<int, vector<int>, less<int>> pq1;//2.以vector作为底部容器类，内部构建小堆结构
priority_queue<int, vector<int>, greater<int>> pq2;

2.未指定定义：

//未指定定义
priority_queue<int> pq3;//默认以vector作为底层容器类，内部构建大堆结构

2.2priority_queue的常见操作 

函数声明	接口说明
priority_queue()/priority_queue(first, last)	构造一个空的优先级队列
empty( )	检测优先级队列是否为空，是返回true，否则返回false
top( )	返回优先级队列中最大(最小元素)，即堆顶元素
push(x)	在优先级队列中插入元素x
pop()	删除优先级队列中最大(最小)元素，即堆顶元素

void priority_queue1()
{priority_queue<int> pq1;pq1.push(3);pq1.push(7);pq1.push(2);pq1.push(5);pq1.push(8);pq1.push(1);pq1.push(6);pq1.push(4);//插入while (!pq1.empty()){cout << pq1.top()<<" ";//返回堆顶元素pq1.pop();//删除堆顶元素}//8 7 6 5 4 3 2 1
}

三.priority_queue的模拟实现

我们在模拟实现priority_queque之前，要先复习一下两个堆算法，这里我们就以构建大堆结构为例。

3.1向上调整建堆

以大堆为例，向上调整建堆就是在堆的末尾插入一个数据后，经过向上调整，依然是一个大堆。

调整思想：
1、将目标结点与其父结点进行比较。
2、若目标结点的值比其父结点的值大，则交换目标结点与其父结点的位置，并将原目标结点的父结点当作新的目标结点继续进行向上调整，直到目标节点的值比其父节点的值小位置位置，调整完毕。

3.2向下调整建堆

以大堆为例，向下调整算法是为了删除堆顶数据，在删除堆顶数据后，让该堆依旧是大根堆。

调整思想：
1、将目标结点与其较大的子结点进行比较。
2、若目标结点的值比其较大的子结点的值小，则交换目标结点与其较大的子结点的位置，并将原目标结点的较大子结点当作新的目标结点继续进行向下调整，直到目标节点比其较大的子节点的值大为止，调整完成。

3.3priority_queue的模拟实现

函数声明	接口说明
priority_queue()/priority_queue(first, last)	构造一个空的优先级队列
empty( )	检测优先级队列是否为空，是返回true，否则返回false
top( )	返回优先级队列中最大(最小元素)，即堆顶元素
push(x)	在优先级队列中插入元素x
pop()	删除优先级队列中最大(最小)元素，即堆顶元素

namespace fu
{//内部构建大根堆template <class T>struct less{bool opeartor()(const T& x, const T& y){return x < y;}};//内部构建小跟堆template <class T>struct greater{bool opeartor()(const T& x, const T& y){return x > y;}};//优先级队列模拟实现template<class T, class Container = vector<int>, class Compare = less<T>>class priority_queue{public://向上调整建堆void AdjustUp(int child){int parent = (child - 1) / 2;while (child > 0){if (_com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}//插入数据void push(const T& x){_con.push_back(x);AdjustUp(x);}//向下调整建堆void AdjustDown(int n, int parent){int child = 2 * parent + 1;while (child < n){if (child + 1 < n && _comp(_con[child], _con[child + 1])){child++;}if (_com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = 2 * parent + 1;}else{break;}}}//删除数据void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(_con.size(),0);}//访问堆顶元素T& top(){return _con[0];}const T& top() {return _con[0];}//返回有效元素个数size_t size() {return _con.size();}//判断队列是否为空bool empty() {return _con.empty();}private:Container _con;Compare _com;};
}

感谢各位大佬的观看，创作不易，还请各位大佬支持~