【C++】priority_queue使用和模拟实现——仿函数（上）

首先，在这里还是推荐一下我正在用的一个C++的查询文档网站，这里是关于 priority_queue的使用文档。有什么本文中没有讲清楚的东西，可以去参考这个网站的内容。

1. priority_queue的使用

1.priority_queue的介绍

priority_queue(优先级队列)，是包含在<queue>头文件下的一个容器适配器。下面是cplusplus网站对priority_queue的介绍。

可以看到，priority_queue是一个容器适配器，默认的容器是vector。他和队列在使用上是类似的，只是出队列的规则不同，queue是按照入队列的顺序出队列，priority_queue是按照优先级出队列，这里的优先级是按照类模板的第三个参数决定的，这里的第三个参数是一个仿函数，关于仿函数的概念将会在下文中详细讲解。

2.priority_queue的结构

priority_queue在底层的逻辑上，是一个堆，每次pop的都是堆定的数据，关于堆的讲解，可以去看一下博主之前写的【数据结构】树与二叉树，里面对堆这个数据结构讲解的还是比较清楚的。

3. 主要接口

priority_queue是一个容器适配器，所以接口基本上都差不多，我们看一下文档：

可以看到，接口和stack、queue基本相同，这里给出几个重点的函数接口：

4. 使用示例

了解了上述的一些接口之后，总是要实践一下的，接下来我们使用以下这个结构，来测试一下：

//这里放一下测试代码，读者可以自行拷贝下去测试
void Test1()
{
  priority_queue<int> heap;
  heap.push(5);
  heap.push(3);
  heap.push(7);
  heap.push(10);
  heap.push(1);
  heap.push(9);
  while (!heap.empty())
  {
    cout << heap.top() << " ";
    heap.pop();
  }
  cout << endl;
}

可以看到，默认情况pop出来的是当前堆内的最大值，所以可知默认的堆是大堆。

❓那么如果想让堆变成小堆需要怎么做呢？

✅这里就要注意到，在文章的开头，我们讲到的类模板的第三个参数。可以看到默认传的参数是less，这就是表示默认建立大堆，如果想建小堆的话需要传的仿函数就是greater。

接下来，就用刚学的priority_queue做一道OJ题吧：215. 数组中的第K个最大元素 - 力扣（LeetCode）.

我是题解，点我