从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六大组件之一的仿函数,然后是反向迭代器。