从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)（中）：https://developer.aliyun.com/article/1521888
4.2 priority_queue的使用
优先级队列默认使用 vector 作为其底层存储数据的容器，
在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构，因为 priority_queue 就是堆。
所有需要用到堆的地方，都可以考虑使用 priority_queue。
值得注意的是，priority_queue 默认为大根堆。注意下面是反过来的：
优先级队列默认大的优先级高，传的是 less 仿函数，底层是一个大堆；
如果想控制小的优先级高，需手动传 greater 仿函数，其底层是一个小堆。
（仿函数后面讲，实现优先级队列时详细讲解，现在只需要知道如何使用即可）
看看文档使用：
常用接口函数：
代码使用：（包的是queue的头文件）
#include <iostream> #include <queue> using namespace std; void test_priority_queue() { priority_queue<int> pq;//默认大堆优先级高 pq.push(3); pq.push(1); pq.push(2); pq.push(5); pq.push(0); pq.push(8); pq.push(1); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } cout << endl; // 迭代器区间初始化：原生指针也是迭代器 int arr[] = { 3, 2, 7, 6, 0, 4, 5, 9, 8, 1 }; priority_queue<int> heap(arr, arr+sizeof(arr)/sizeof(arr[0])); while (!heap.empty()) { cout << heap.top() << " "; heap.pop(); } cout << endl; } int main() { //test_stack(); //test_queue(); test_priority_queue(); return 0; }
默认是用 vector 存储的，注意这里没有明确指定 less 还是 greater，所以默认为 less。
令该优先级队列以小的优先级高：在定义优先级队列时主动去传 greater<int>
（包一下头文件functional）因为传 greater<int> 是在第三个参数接收的，
如果你想传第三个模板参数，你必须得先传第二个（下面是定义，仔细观察缺省值部分）
代码演示小的优先级高：
#include <iostream> #include <queue> #include <vector> #include <functional> // greater和less的头文件 using namespace std; void test_priority_queue() { priority_queue<int, vector<int>, greater<int>> pq; pq.push(3); pq.push(1); pq.push(2); pq.push(5); pq.push(0); pq.push(8); pq.push(1); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } cout << endl; // 迭代器区间初始化：原生指针也是迭代器 int arr[] = { 3, 2, 7, 6, 0, 4, 5, 9, 8, 1 }; priority_queue<int, vector<int>, greater<int>> heap(arr, arr+sizeof(arr)/sizeof(arr[0])); while (!heap.empty()) { cout << heap.top() << " "; heap.pop(); } cout << endl; } int main() { //test_stack(); //test_queue(); test_priority_queue(); return 0; }
值得注意的是如果在priority_queue中放自定义类型的数据，
用户需要在自定义类型中提供> 或者< 的重载。（像日期类一样）
4.3 priority_queue解决TopK问题
剑指 Offer II 076. 数组中的第 k 大的数字 - 力扣（LeetCode）
215. 数组中的第K个最大元素 - 力扣（LeetCode）
（这两题是一样的，我们在讲TopK问题的时候也用C语言写过：）
数据结构与算法⑬(第四章_中_续二)堆解决Topk问题+堆的概念选择题_GR C的博客-CSDN博客
难度中等
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入:
[3,2,1,5,6,4],
k = 2
输出: 5
示例 2:
输入:
[3,2,3,1,2,4,5,5,6],
k = 4
输出: 4
提示：
1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
int findKthLargest(int* nums, int numsSize, int k){ }
解析代码：（sort一下也能过，但是时间是O（N*logN））
和以前一样：这里我们需要把整个数组建成一个大堆，然后pop（k-1）次堆顶的元素后堆顶的元素
就是第k大的数。而且我们不用自己写大堆下调算法了，建堆也可以直接用priority_queue:
class Solution { public: int findKthLargest(vector<int>& nums, int k) { //把整个数组建成一个大堆，(O(N)) priority_queue<int> MaxHeap(nums.begin(),nums.end()); while(--k)//然后pop（k-1）次堆顶的元素(log(N*K)) { MaxHeap.pop(); } return MaxHeap.top();//堆顶的元素就是第k大的数 } };
看下C语言写的：（调整算法后面模拟实现priority_queue还会用，面试可能也要写）
void Swap(int* px, int* py) { int tmp = *px; *px = *py; *py = tmp; } void justDown(int* arr, int n, int root)//大堆下调 { int father = root; int child = father * 2 + 1;//默认左孩子大 while (child < n) { if (child + 1 < n && arr[child] < arr[child + 1]) { // 如果右孩子存在且右孩子比左孩子大 child++; } if (arr[father] < arr[child]) { Swap(&arr[father], &arr[child]); father = child; child = father * 2 + 1; } else { break; } } } int findKthLargest(int* nums, int numsSize, int k) { for (int i = (numsSize - 1 - 1) / 2;i >= 0;i--) //建堆的for写法 { justDown(nums, numsSize, i); } // 删除数据 for (int i = 1;i <= k - 1;i++) { Swap(&nums[0], &nums[numsSize - i]); justDown(nums, numsSize - i, 0);//删除多少个numsize-多少个 } return nums[0]; }
本章完。
下一部分：模拟实现 priority_queue，过程中讲STL六大组件之一的仿函数，然后是反向迭代器。
