【STL专题】优先级队列priority_queue的使用和模拟实现，巧妙利用仿函数解决优先级

  欢迎来到 CILMY23的博客

🏆本篇主题为：优先级队列priority_queue的使用和模拟实现，巧妙利用仿函数解决优先级

🏆个人主页：CILMY23-CSDN博客

🏆系列专栏： C++ | C语言 | 数据结构与算法 | Linux | 算法专题 

🏆感谢观看，支持的可以给个一键三连，点赞收藏+评论。如果你觉得有帮助，还可以点点关注

---

目录

前言

 优先级队列的使用

优先级队列的常用接口

 实例演示

优先级队列的模拟实现

如何控制优先级？

---

前言

上期我们讲了栈和队列的使用和模拟实现，本期我们将探究priority_queue,优先级队列的使用和模拟实现，并应用仿函数来解决优先级的问题。

---

 优先级队列的使用

我们还是从官方文档看起， 

• 

1. 优先级队列是容器适配器的一种，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此语法类似于堆，在堆中可以随时插入元素，并且只能检索堆的最大元素(优先级队列中位于顶部的元素)。
3. 优先级队列被设计成容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：        
   • empty()：检测容器是否为空
   • size()：返回容器中有效元素个数
   • front()：返回容器中第一个元素的引用
   • push_back()：在容器尾部插入元素
5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

不难看出实际上的优先级队列和使用堆没什么差别，当然从接口上我们也不难看出，其次是它没有单独的头文件，它和queue公用一个头文件，都是queue.h。

优先级队列的常用接口

接口	功能
bool empty() const;	检测优先级队列是否为空，是返回true，否则返回 false
const value_type& top() const;	返回优先级队列中最大(最小元素)，即堆顶元素
void push (const value_type& val);	在优先级队列中插入元素x
void pop();	删除优先级队列中最大(最小)元素，即堆顶元素

 实例演示

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

215. 数组中的第K个最大元素

我们可以通过这个例子来看。

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int> pq;for (auto& e : nums) {pq.push(e);}// 删除前K-1个元素for (int i = 0; i < k - 1; i++) {pq.pop();}return pq.top();}
};

本题要求在一个整数数组中找到第k个最大的元素，且必须设计时间复杂度为O(n)的算法。如果我们使用堆排序，就可以发现时间复杂度为O(nlogn)，建堆的时间代价是O(n)，删除的总代价是O(klogn)，因为k<n，故渐进时间复杂为O(n+klogn)=O(nlogn)。

那如果我们想实现小堆就可以使用greater，functional，它是greater算法的头文件，创建实例，priority_queue<int, vector<int>, greater<int>>

优先级队列的模拟实现

首先我们先写好各类接口函数，以及容器适配器。

template<class T,class Container = vector<T>>
class priority_queue
{
public:bool empty() const{}size_t size() const{}const T& top() const{}void push(const T& x){}void pop(){}private:Container _con;
};

大部分和堆的实现都类似，可以参照过去的文章，堆的模拟。那这里的判空，大小，堆顶接口函数都很容易写，重点还是插入和删除，这里的插入还是和以前一样，先插入到末尾，然后再向上调整。

void push(const T& val)
{_con.push_back(val);Adjustup(_con.size() - 1);
}Adjustup(int child)
{int parent = (child - 1) / 2;while (child > 0){if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

 在C++中我们不再像过去那样造轮子确实会轻松不少，利用交换函数swap和插入函数就能节省很多时间。

删除，我们说堆的删除是删除堆顶数据，所以我们进行首尾交换然后再进行向下调整。

void pop()
{if (_con.empty()){return ;}swap(_con.front(), _con.back());_con.pop_back();AdjustDown(0);
}void AdjustDown(int parent)
{int child = parent * 2 + 1;while (child < _con.size()){////如果左孩子比右孩子大，则从右孩子开始if (child +1 < _con.size() && _con[child] > _con[child +1]){++child;}if (_con[child] < _con[parent]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

注意，这里在找左孩子和右孩子的时候必须要考虑到二者都在size之内，否则就会越界报错啦。

如何控制优先级？

过去我们控制优先级是在qsort中用函数指针解决的，而在c++中我们用仿函数解决。

什么是仿函数？

仿函数（Functor）是 C++ 中通过重载 operator() 运算符的类或结构体，其对象可以像函数一样被调用。它常用于定制算法的行为，例如排序规则、比较逻辑等，相比普通函数指针，仿函数能携带状态（成员变量），灵活性更高。 

 例如我们在算法algorithm中使用sort，我们可以利用两个仿函数，来控制排序的逻辑。

struct greater
{bool operator()(int a, int b){return a > b;}
};sort(vec.begin(), vec.end(), greater());

 priority_queue 的仿函数

 

在我们的priority_queue中，它默认为大堆，而这里使用的是less，less表示父节点值 >= 子节点（最大堆），实际就是子节点要小于父节点，我们原先的逻辑是如果子节点大于父节点，我们就交换，所以这里我们可以把逻辑变通一下，如果父节点小于子节点，我们就交换两个值，于是我们这里的仿函数就和库里一样了。

template<class T>struct less
{bool operator()(const T& x,const T& y){return x < y;}
};//向上调整
void AdjustUp(int child)
{int parent = (child - 1) / 2;while (child > 0){Compare com;//子节点大于父节点//if (_con[child] > _con[parent])//父节点小于子节点//if(_con[parent] > _con[child])if(com(_con[parent],_con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

同理，把向下调整也改造一下，删除完后，greater就是子节点大于父节点，也就是父节点小于等于子节点，我们原先的逻辑是如果父节点比子节点大，我们就交换父子节点。

template<class T>struct greater
{bool operator()(const T& x, const T& y){return x > y;}
};void AdjustDown(int parent)
{int child = parent * 2 + 1;while (child < _con.size()){Compare com;//如果左孩子比右孩子大，则从右孩子开始//if (child +1 < _con.size() && _con[child] > _con[child +1])//if (child +1 < _con.size() && _con[child + 1] < _con[child])if (child + 1 < _con.size() && com(_con[child] , _con[child + 1])){ ++child;}if (com(_con[parent] ,_con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}

到这里我们的优先级队列就实现完了，主要还是利用仿函数进行一个控制，我们可以利用仿函数控制大堆和小堆。