一、priority_queue 的介绍和使用

1.priority_queue 的介绍

我们和学习之前的容器一样，可以使用cplusplus官网进行学习：priority_queue文档介绍

priority_queue(优先级队列)是一种容器适配器，它 和queue使用同一个头文件，其底层结构是一个堆，并且默认情况下是一个大根堆，此外，priority_queue也不支持迭代器，这是为了不破坏堆的结构使用vec，此外，堆需要进行下标的计算，所以priority_queue使用vector作为它的默认容器适配器

priority_queue和stack、queue不同的是，多了一个模板参数-仿函数，仿函数我们在后文进行介绍

【总结】

1.优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的

2.此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)

3.优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部

4.底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：

empty()：检测容器是否为空

size()：返回容器中有效元素个数

front()：返回容器中第一个元素的引用

push_back()：在容器尾部插入元素

pop_back()：删除容器尾部元素

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

6.需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作

2.priority_queue 的使用

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

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

【注意】

priority_queue默认使用的仿函数是less,所以默认建成的堆是大堆，如果我们要实现一个小堆，就需要指定仿函数为greater,该仿函数包含在头文件functional中，并且由于仿函数是第三个缺省模板参数，所以我们需要先传递第二个模板参数–适配容器

void priority_queue_test(){// 大堆priority_queue<int> pq1;pq1.push(1);pq1.push(2);pq1.push(3);pq1.push(4);cout << pq1.size() << endl;while (!pq1.empty()){cout << pq1.top() << " ";pq1.pop();}cout << endl;// 小堆priority_queue<int, vector<int>, greater<int>> pq2;pq2.push(10);pq2.push(20);pq2.push(30);pq2.push(40);while (!pq2.empty()){cout << pq2.top() << " ";pq2.pop();}cout << endl;}

3.priority_queue 相关OJ题

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

题目描述

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

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例

输入: [3,2,1,5,6,4], k = 2
输出: 5

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

思路1

我们的第一反应就是对数组进行排序，然后返回nums[nums.size()-k]即可，但是即使是快速排序的时间复杂度也为O(N*lonN)，复杂度过高，不太符合题意

class Solution {public:    int findKthLargest(vector<int>& nums, int k) {        sort(nums.begin(),nums.end());        return nums[nums.size()-k];    }};

思路2

我们可以建立一个N个数的大堆，然后pop K次，此时堆顶的元素就是第K大的数字，该方法的时间复杂度：向下调整建堆的时间复杂度为O(N),pop 数据之后向下调整的时间复杂度为O(K*logN),所以总的时间复杂度为O(N+k*logN),对于该方法，当N很大，K很小的时候，时间复杂度过高

class Solution {public:    int findKthLargest(vector<int>& nums, int k) {        // 建立N个数的大堆        priority_queue<int> pq(nums.begin(),nums.end());        // pop K次        while(--k)        {            pq.pop();        }        return pq.top();    }};

思路3

建立K个数的小堆，剩余N-K个数一次与堆顶的元素进行比较，如果大于堆顶的元素pop堆顶的元素，然后将该数据push入堆，最后堆顶的元素就是第K大的数据，建堆的时间复杂度为O(K),push再向上调整的时间复杂度为O((N-K)*logK),所以总的时间复杂度为O(K+(N-K)*logK),当N很大，K很小的时候，复杂度依然不是很高，因为堆的大小固定为K

class Solution {public:    int findKthLargest(vector<int>& nums, int k) {        // 建K个数的小堆，比堆顶的元素大就入堆        priority_queue<int,vector<int>,greater<int>> pq(nums.begin(),nums.begin()+k);        for(size_t i=k;i<nums.size();++i)        {            // 比堆顶的数据大就入堆            if(nums[i]>pq.top())            {                pq.pop();                pq.push(nums[i]);            }        }        return pq.top();    }};

二、仿函数

1.什么是仿函数

仿函数也叫函数对象，仿函数是一个类，且类里必须重载函数调用运算符(),即operator(),这样就使得这样类的对象就行函数一样去使用，我们称其为仿函数或者函数对象，我们以比较大小为例，如下：

// 仿函数/函数对象namespace hdp{template<class T>class less{public:bool operator()(const T& x, const T& y) const{return x < y;}};template<class T>class greater{public:bool operator()(const T& x, const T& y) const{return x > y;}};}void functor_test(){hdp::less<int> lessFunc;hdp::greater<int> greaterFunc;// lessFunc.operator()(1, 2);cout << lessFunc(1, 2) << endl;// greaterFunc.operator()(1, 2);cout << greaterFunc(1, 2) << endl;}

我们可以看到，less和greater类重载了()运算符之后，类对象就可以像函数一样去使用，因此他们被称为仿函数

2.仿函数的运用和作用

我们以冒泡排序为例来说明仿函数的作用，我们知道，排序分为升序和降序，在C语言阶段，我们只能通过改变交换判断的条件来改变升降序方式，但是这种方式及其麻烦，需要写两份只有一个地方不同的代码，造成了代码的冗余，还有一种方式就是传递一个函数指针，根据比较函数来决定排序的方式(升序还是降序)，所以我们在排序函数的最后一个参数传递一个函数指针：

template<class T>bool compare_up(const T& x, const T& y){return x > y;}template<class T>bool compare_down(const T& x, const T& y){return x < y;}//冒泡排序template<class T>void BubbleSort(T* a, int n, bool(*cmp)(const T&,const T&)){for (size_t i = 0; i < n; ++i){int exchange = 0;for (size_t j = 0; j < n - i - 1; ++j){if (cmp(a[j], a[j + 1])){swap(a[j], a[j + 1]);exchange = 1;}}if (exchange == 0){break;}}}void BubbleSort(){int a[] = { 1,3,4,3,2,5,7,2,6,3 };// 升序BubbleSort(a, sizeof(a) / sizeof(int), compare_up);for (auto e : a){cout << e << " ";}cout << endl;// 降序BubbleSort(a, sizeof(a) / sizeof(int), compare_down);for (auto e : a){cout << e << " ";}cout << endl;}

在C++中，我们不需要再使用函数指针来解决排序的升降序的问题，而是使用仿函数：

// 仿函数/函数对象namespace hdp{template<class T>class less{public:bool operator()(const T& x, const T& y) const{return x < y;}};template<class T>class greater{public:bool operator()(const T& x, const T& y) const{return x > y;}};}template<class T,class Compare>// 仿函数一般比较小，所以可以不用传引用//void BubbleSort(T* a, int n, const Compare& com)void BubbleSort(T* a, int n, const Compare com){for (size_t i = 0; i < n; ++i){int exchange = 0;for (size_t j = 0; j < n - i - 1; ++j){if (com(a[j], a[j + 1])){swap(a[j], a[j + 1]);exchange = 1;}}if (exchange == 0){break;}}}void BubbleSort_test(){int a[] = { 3,2,6,4,2,5,6,4,7,3,2,1 };BubbleSort(a, sizeof(a) / sizeof(int), hdp::less<int>());for (auto e : a){cout << e << " ";}cout << endl;BubbleSort(a, sizeof(a) / sizeof(int), hdp::greater<int>());for (auto e : a){cout << e << " ";}cout << endl;}

三、priority_queue 的模拟实现

priority_queue.h

#pragma oncenamespace hdp{template<class T>class less{public:bool operator()(const T& x, const T& y) const{return x < y;}};template<class T>class greater{public:bool operator()(const T& x, const T& y) const{return x > y;}};template<class T,class Container=vector<T>,class Compare=less<T>>class priority_queue{public:// 无参构造priority_queue(){}// 迭代器区间构造template<class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first,last){// 向下调整建堆for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i){adjust_down(i);}}// 向上调整void adjust_up(size_t child){Compare com;size_t parent = (child - 1) / 2;while (child > 0){//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 push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}// 向下调整void adjust_down(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){// if (child+1 < _con.size() && _con[child] < _con[child+1])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;}}}// 删除堆顶元素void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}// 获取堆顶元素const T& top()  const{return _con[0];}// 判空bool empty()  const{return _con.size() == 0;}// 获取元素个数size_t size()  const{return _con.size();}private:Container _con;};}

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>using namespace std;#include <functional>#include <vector>#include "priorityqueue.h"void priority_queue_test(){std::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(5);v.push_back(4);// 大堆hdp::priority_queue<int> pq1(v.begin(), v.end());while (!pq1.empty()){cout << pq1.top() << " ";pq1.pop();}cout << endl;// 小堆hdp::priority_queue <int, vector<int>, greater<int>> pq2;pq2.push(10);pq2.push(20);pq2.push(30);pq2.push(40);cout << pq2.size() << endl;while (!pq2.empty()){cout << pq2.top() << " ";pq2.pop();}cout << endl;}int main(){priority_queue_test();return 0;}