【C++】优先级队列（priority_queue）的用法与实现

一、概念：

二、仿函数（Functor）：

概念：

应用：

三、底层实现：

基本操作：

完整代码：

测试示例：

一、概念：

优先级队列（priority_queue）在功能上类似于堆（heap）这个数据结构，在优先级队列中，元素的出队顺序（或检索顺序）基于它们的优先级，而不是它们进入队列的顺序。具有最高优先级的元素将最先出队，而具有最低优先级的元素将最后出队（或反之，取决于具体实现），就像是在大堆中堆顶元素是堆中最大的值，在删除堆顶元素时总是删除的最大值，而不是取决于它们入堆的顺序。

定义：

#include <queue> // 引头文件// 类似于大堆; less表示按照递减(从大到小)的顺序插入元素
priority_queue<int, vector<int>, less<int>> s; // 类似于小堆; greater表示按照递增（从小到大）的顺序插入元素
priority_queue<int, vector<int>, greater<int>> s;

二、仿函数（Functor）：

概念：

仿函数（Functor）也称为函数对象，是一种可调用的对象，一般通过重载函数调用操作符（operator()）来实现。这使得仿函数类具有像函数一样的特性：可以接受参数并返回值。

仿函数的目的为：使一个类的使用看上去像一个函数，从而方便地应用于算法、STL容器以及其他需要函数对象的场合。

仿函数的优点：

1、可以拥有状态，这意味着仿函数可以在运行时动态地改变其行为。

2、与纯函数相比，仿函数在某些情况下可能具有更快的执行速度。

注意：

仿函数并不是真正的函数，而是具有函数行为的类对象。因此，它们可以像类一样存储和访问数据，同时又具有函数的调用特性。

应用：

例如在C++ algorithm 库中的 sort 函数的第三个参数：

template<class RandomIt, class Compare>  
void sort(RandomIt first, RandomIt last, Compare comp);

comp：（可选）：一个接受两个参数并返回一个布尔值的函数或函数对象。

默认的排序是升序，此时我们不用库中提供的降序仿函数，自己实现一个简单的降序仿函数：

template<class T>
struct Greater // 函数对象(仿函数)功能实现
{bool operator()(const T& x, const T& y){return x > y;}
};void Test()
{vector<int> v = { 5,3,7,8,3,0,6,3,1,2,9 };sort(v.begin(), v.end(), Greater<int>()); // 匿名调用// Greater<int> s1;// sort(v.begin(), v.end(), s1); // 显式调用for (auto e : v){cout << e << " ";}
}

三、底层实现：

基本操作：

1、push()：将元素入队列。【操作与堆类似，向尾部插入并不断向上调整至合适位置】

2、pop()：删除队列中优先级最高的元素。【操作与堆类似，首尾交换后删除尾部，队头元素不断向下调整至合适位置】

3、top()：获取并返回队列中优先级最高的元素。

4、size()：获取并返回队列大小。【返回值为 unsigned int（size_t）类型】

5、empty()：判断队列是否为空。【返回值为bool类型。队列为空返回true，不空返回false】

完整代码：

template<class T>
struct Less
{bool operator()(const T& x, const T& y){return x < y;}
};template<class T>
struct Greater
{bool operator()(const T& x, const T& y){return x > y;}
};template<class T, class Con = vector<T>, class Com = Less<T>>
class priority_queue
{
public:// 向上调整void adjust_up(int child){Com com; // 模板实例化一个函数对象，默认Less，取小int parent = (child - 1) / 2;while (child > 0){//if (_con[child] > _con[parent])// if(_con[parent] < _con[child])if (com(_con[parent], _con[child])) // 为真执行，为假跳出{swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}// 向下调整void adjust_down(size_t parent){Com com;size_t child = parent * 2 + 1;while (child < _con.size()){// 找左右孩子中大的那个与父节点交换，换算关系如下//if (child + 1 < _con.size() && _con[child + 1] > _con[child])//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}//if (_con[child] > _con[parent])//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& val){_con.push_back(val);adjust_up(_con.size() - 1); // 传入刚插入的子节点下标}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top() const{return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}
private:Con _con;
};

测试示例：

给一个数组（升序）以此按序进入队列，此时优先级队列的功能类似大堆，应该按照降序返回：

int main()
{vector<int> v = { 1,2,3,4,5,6,7,8,9,10 };priority_queue<int> q1; // 默认大堆 Lessfor (auto i : v){q1.push(i);}while (!q1.empty()){cout << q1.top() << " ";q1.pop();}return 0;
}

测试结果：