【C++】STL容器适配器——priority_quene（堆/优先级队列）类的使用指南（含代码使用）（19）

一.priority_quene的文档介绍

1. 优先队列被实现为 【容器适配器】，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特 定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
2. 此上下文类似于 （二叉树）堆 ，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元 素)。
3. 优先队列是一种容器适配器，根据严格的弱排序标准，它的 第一个元素 总是它所包含的元素中 最大的 。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过 随机访问迭代器 访问，并支持以下操作：

• empty()：检测容器是否为空
• size()：返回容器中有效元素个数
• front()：返回容器中第一个元素的引用
• push_back()：在容器尾部插入元素
• pop_back()：删除容器尾部元素

5. 标准容器类vector和deque满足这些需求。 [ 默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector ]
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数
   make_heap、push_heap和pop_heap来自动完成此操作。

二、priority_quene 类——使用环境准备

• 在使用priority_quene类时，必须包含#include<quene> #include<iostream>以及 展开命名空间 using namespace std;

三、priority_quene 类——文档查看

• 查看所有接口网站：https://cplusplus.com
  

五.priority_quene的使用

1.使用要点

• . 默认情况下，priority_queue是 大堆(大的优先级高) 【栈顶元素是最大的】

2.基本使用函数

3.基本使用场景（1）——对vector一段区间内的元素进行建堆

vector<int> v{3,2,7,6,0,4,1,9,8,5};
 priority_queue<int> q1(v.begin(),v.begin()+k);//对前k个数进行建堆
 priority_queue<int> q1(v.begin(),v.end());//对整个区间进行1建堆

4.特殊使用场景（1）——用【仿函数】控制实现小堆

• priority_queue<int, vector<int>, greater<int>> pq;
• 虽然是小堆，但是用的是greater，可以从数组从小到大角度理解

void test_priority_queue()
{
  // 默认是大堆 -- less
  //priority_queue<int> pq;
  // 仿函数控制实现小堆
  priority_queue<int, vector<int>, greater<int>> pq;
  pq.push(3);
  pq.push(5);
  pq.push(1);
  pq.push(4);
  while (!pq.empty())
  {
    cout << pq.top() << " ";
    pq.pop();
  }
  cout << endl;
}

四、priority_quene(堆)——例题应用（求数组中的第k个最大元素）

1）做法1：用默认给的大堆直接解决

• 我们可以用优先级队列（堆）来处理
• 我们要建立一个堆(默认是大堆)，首先要把数组传进去，也就是传区间【运用到优先级队列传区间的函数】
  

class Solution {
public:
   int findkthLargest(vector<int>& nums,int k){
      //默认建立大堆
   priority_queue<int>pq(nums.begin(),nums.end)）；
 //k*logN
 while(--k)
 {
      pq.pop()；
 }
return pq.top();
}`

2）做法2：用小堆解决【用【仿函数】控制实现小堆应用】

• 这里用仿函数【greater<int>】如下所示，让优先级队列（堆）变成小堆
• 将前k个数组数据建立成小堆，将剩余的数据不断和小堆堆顶元素（最小的）进行比较，比其大则替换，后面堆会自己调整
• 遍历完整个数组以后，堆顶元素即是堆中最小的，也是整个数组中第k个大的元素

class Solution {
public:
   int findkthLargest(vector<int>& nums,int k){
      //仿函数实现小堆
   priority_queue<int,vector<int>,greater<int>> pq(nums.begin(),nums.begin()+k)；
   for(int i=k;i<nums.size();++i)
   {
    if(nums[i]>pq.top())
    {
      pq.pop();
      pq.push(nums[i]);  
    }
   }
    return pq.top();
}