C++ Priority Queue的使用

Posted on | In |

刷LeetCode中用到的Priority Queue使用

Priority Queue 优先队列

priority_queue是包含在头文件#include<queue>中的，它与queue不同点就在于它会自动为queue内的元素进行排序。

priority_queue包含所有队列的特性，包括所有的基本操作，只是在这个基础上添加了一个内部排序，它的本质是一个堆实现的。

1
2
3
4
5
什么是堆？

我们说的堆（heap）是程序员申请的内存空间。在C++中你可以理解为所有非常量的指针空间。和heap相对应的，还有栈stack，静态区static，常量区const，以及程序代码区。这些都是程序运行所需要申请的内存空间。

heap堆与其他内存的主要差别是，heap是由程序员申请、释放和管理的，而不是由程序和系统自动分配和释放的，是动态的。另一个区别是其他区域都是有固定大小的，而heap的大小仅受内存和虚拟内存大小的限制。

和队列基本操作相同：

  • top() 访问对头元素
  • empty() 队列是否为空
  • size() 返回队列内元素个数
  • push() 插入元素到队尾，并排序
  • emplace() 原地构造一个元素并插入队列
  • pop() 弹出队头元素
  • swap() 交换内容

优先队列定义

priority_queue<Type, Container, Functional>

  • Type是数据类型
  • Container是容器类型，Container必须是用数组实现的容器，比如vector，dqueue等，但是不能用list。STL里默认用vector
  • Functional是比较的方式。

当需要自定义的数据类型时才需要传入这三个参数。
对于基本数据类型，排序默认大推顶

  • priority_queue<int, vector<int>, greater<int> > 小推顶
  • priority_queue<int, vector<int>, less<int>> 大推顶

LeetCode例子

#215. Kth Largest element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        
        priority_queue<int, vector<int>, greater<int> > q; //小推顶
        int n = nums.size();
        
        for(int i = 0; i<n; i++){
            if(q.size() < k){
                q.push(nums[i]);
            }
            else{
                if(nums[i] > q.top()){
                    q.pop();
                    q.push(nums[i]);
                }
            }
        }
        
        return q.top();
        
    }
};