优先级队列（priority_queue）

大家好，欢迎来到IT知识分享网。

一.什么是优先级队列

首先要注意的就是别与队列（queue）搞混了，队列是一种先进先出（First in First out，FIFO）的数据类型。每次元素的入队都只能添加到队列尾部，出队时从队列头部开始出。

优先级队列（priority_queue）其实，不满足先进先出的条件，更像是数据类型中的“堆”。优先级队列每次出队的元素是队列中优先级最高的那个元素，而不是队首的元素。这个优先级可以通过元素的大小等进行定义。比如定义元素越大优先级越高，那么每次出队，都是将当前队列中最大的那个元素出队。

详细介绍：priority_queue – C++ Reference (cplusplus.com) （官方网站）

优先级队列的定义：

简单理解：

priority_queue<typename, container, functional>

typename是数据的类型；
container是容器类型，可以是vector,queue等用数组实现的容器，不能是list，默认用的vector；
functional是比较的方式，默认是大顶堆（就是元素值越大，优先级越高）；如果使用C++基本数据类型，可以直接使用自带的less和greater这两个仿函数（默认使用的是less，就是构造大顶堆，元素小于当前节点时下沉）。使用自定义的数据类型的时候，可以重写比较函数，也可以在自定义类型中进行运算符重载（less重载小于“<”运算符，构造大顶堆；greater重载大于“>”运算符，构造小堆）。

说到这里，大家应该都知道了，优先级队列的底层就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆

常用接口：

优先级队列的简单使用:

215. 数组中的第K个最大元素 – 力扣（LeetCode）

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int> q1(nums.begin(),nums.end()); while(--k) { q1.pop(); } return q1.top(); } };

是不是就很简单。

二.如何模拟实现一个优先级队列 

我们前面谈到过了，优先级队列的底层就是堆。故把建堆这个大工程搞定就会轻松很多很多。

在我们实现的优先级队列中，模板的定义如下：template<class T,class Container = vector<T>,class comper=Less<T>>，这里我们自己实现了仿函数 ：

这里可能有人会问了，什么是仿函数：

仿函数（Functor）是一种行为类似于函数的对象，可以像函数一样被调用。仿函数是一个类或结构体，它重载了圆括号操作符 “()”，因此可以像函数一样被调用。像是一个可调用的函数，但它实际上是一个类或结构体。你可以像调用函数一样来使用它，传入参数并获得返回值

template <class T> class Less { public: bool operator()(const T& x, const T& y) { return x < y; } }; template<class T> class Greater { public: bool operator()(const T& x, const T& y) { return x > y; } };

建堆

建堆，我们就要想到两种算法。向上调整算法，向下调整算法。

备注：因为默认的容器时vector，故这里再模拟的时候也是vector，_con其实是vector<类型>_con

向上调整算法O（N*logN）：

简单来说，向上调整算法是当你插入一个元素时，它是从叶子节点逐步向父亲节点比较，直到根节点。

void AdjustUp(int child) { comper com; int parent = (child - 1) / 2; while (child > 0) { if (com(_con[parent], _con[child])) { swap(_con[child], _con[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } }

向下调整算法O（N）：

void AdjustDown(int parent) { comper com; int child = parent * 2 + 1;//假设左孩子大 while (child<_con.size()) { //判断右孩子是否存在，并找最大发的哪一个孩子 if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) //if (child + 1 < _con.size() && _con[child] < _con[child + 1]) { child++; } if (com(_con[parent], _con[child])) { swap( _con[parent],_con[child]); parent=child; child= parent * 2 + 1; } else { break; } } }

因为向下调整的时间复杂度要小，故建堆的时候我们通常采用向下调整算法。这个算法是通过parent来找child的，故需要parent。而在vector中，我们如何找parent？

for (size_t i = (_con.size() - 1 - 1)/2; i >=0; i--) { AdjustDown(i);//向下调整算法,建大堆 }

 _con.size()-1是找到下标（child），根据公式，parent=（child-1）/2来找到。

建堆完成后，其他功能的实现就很简单。

pop与push:

注意：在pop时，不能直接删除。要先将第一个和最后一个元素交换，再删除最后一个位置，然后为了保持原来的大堆/小堆结构，再走一次向下调整算法。

void pop()//堆顶元素 { swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); }

注意：push也不能只插入到里面就不管，为了防止破坏原来的结构，则需要走一次向上调整算法。

void push(const T& x) { _con.push_back(x); AdjustUp(_con.size() - 1); }

其他功能接口：

因为容器的类型时vector，所以判断empty，size时，可以直接调用vector的接口：

bool empty() { return _con.empty(); } size_t size() { return _con.size(); }

再模拟实现的priority_queue中，top接口如何实现呢？其实很简单，它就是vector的第一个元素。

三.完整代码：

//仿函数 //仿函数（Functor）是一种行为类似于函数的对象，可以像函数一样被调用。仿函数是一个类或结构体，它重载了圆括号操作符 "()"，因此可以像函数一样被调用。 //仿函数就像是一个可调用的函数，但它实际上是一个类或结构体。你可以像调用函数一样来使用它，传入参数并获得返回值 template <class T> class Less { public: bool operator()(const T& x, const T& y) { return x < y; } }; template<class T> class Greater { public: bool operator()(const T& x, const T& y) { return x > y; } }; namespace dnx { template<class T,class Container = vector<T>,class comper=Less<T>> class priority_queue { private: void AdjustDown(int parent) { comper com; int child = parent * 2 + 1;//假设左孩子大 while (child<_con.size()) { //判断右孩子是否存在，并找最大发的哪一个孩子 if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) //if (child + 1 < _con.size() && _con[child] < _con[child + 1]) { child++; } if (com(_con[parent], _con[child])) { swap( _con[parent],_con[child]); parent=child; child= parent * 2 + 1; } else { break; } } } void AdjustUp(int child) { comper com; int parent = (child - 1) / 2; while (child > 0) { if (com(_con[parent], _con[child])) { swap(_con[child], _con[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } public: //初始化 priority_queue() { } template<class InputIterator> priority_queue(InputIterator first, InputIterator end) { while (first != end) { _con.push_back(*first); first++; } //建堆----时间复杂度O（n） //默认情况下priority_queue是大堆，故我们这里排升序 for (size_t i = (_con.size() - 1 - 1)/2; i >=0; i--) { AdjustDown(i);//向下调整算法,建大堆 } } void pop()//堆顶元素 { swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); } void push(const T& x) { _con.push_back(x); AdjustUp(_con.size() - 1); } const T& top() { return _con[0]; } bool empty() { return _con.empty(); } size_t size() { return _con.size(); } private: Container _con; }; }

四.总结

1.优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构。

2.当数据类型是自定义类型的时候，我们可以重写仿函数，或者再自定义类型里面重载”<“,”>”。

eg：如再日期类里面就重载了小于大于符号，但是如果我的数据类型恰好是日期类对象的地址。

这个时候我们只有重写仿函数（一般的日期类里面咋会有堆解引用的重载，不符合实际应用）。

struct LessPDate { bool operator()(const Date* p1, const Date* p2) { return *p1 < *p2; } };