【leetcode】优先队列题目总结

优先队列的底层是最大堆或最小堆

priority_queue<Type, Container, Functional>;

Type是要存放的数据类型
Container是实现底层堆的容器，必须是数组实现的容器，如vector、deque
Functional是比较方式/比较函数/优先级

priority_queue<Type>;

此时默认的容器是vector，默认的比较方式是大顶堆less<type>

常见的函数有：

top()
pop()
push()
emplace()
empty()
size()

基本类型：

//小顶堆
priority_queue <int,vector<int>,greater<int> > q;
//大顶堆
priority_queue <int,vector<int>,less<int> >q;
//默认大顶堆
priority_queue<int> a;//pair
priority_queue<pair<int, int> > a;
pair<int, int> b(1, 2);
pair<int, int> c(1, 3);
pair<int, int> d(2, 5);
a.push(d);
a.push(c);
a.push(b);
while (!a.empty()) 
{cout << a.top().first << ' ' << a.top().second << '\n';a.pop();
}
//输出结果为：
2 5
1 3
1 2

自定义类型：

struct fruit
{string name;int price;
};// 1. 重载运算符  重载”<”
// 大顶堆
struct fruit
{string name;int price;friend bool operator < (fruit f1, fruit f2){return f1.peice < f2.price;}
};// 小顶堆
struct fruit
{string name;int price;friend bool operator < (fruit f1, fruit f2){return f1.peice > f2.price;  //此处是 >}
};// 此时优先队列的定义应该如下
priority_queue<fruit> q;// 2. 仿函数
// 大顶堆
struct myComparison
{bool operator () (fruit f1, fruit f2){return f1.price < f2.price;}
};struct myComparison
{bool operator () (fruit f1, fruit f2){return f1.price > f2.price;  //此处是 >}
};// 此时优先队列的定义应该如下
priority_queue<fruit, vector<fruit>, myComparison> q;

--------------------------------------------------------------------------------------------------------

215. 数组中的第K个最大元素

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int, vector<int>, greater<int>> pq;for (auto num : nums) {pq.push(num);if (pq.size() > k) {pq.pop();}}return pq.top();}
};

快排思想解法：

class Solution {
public:int partition(vector<int>& nums, int left, int right) {int randIndex = left + rand() % (right - left + 1);swap(nums[left], nums[randIndex]);int pivot = nums[left];while (left < right) {while (left < right && nums[right] >= pivot) {right--;}nums[left] = nums[right];while (left < right && nums[left] <= pivot) {left++;}nums[right] = nums[left];}nums[left] = pivot;return left;}int findKthLargest(vector<int>& nums, int k) {int left = 0, right = nums.size() - 1;int targetIndex = nums.size() - k;while (left <= right) {int mid = partition(nums, left, right);if (mid == targetIndex) {return nums[mid];} else if (mid < targetIndex) {left = mid + 1;} else {right = mid - 1;}}return INT_MIN;}
};

347. 前 K 个高频元素

class Solution {
public:struct compare {bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int, int> mp;for (auto& num : nums) {mp[num]++;}priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;for (auto& item : mp) {pq.push(item);if (pq.size() > k) {pq.pop();}}vector<int> res;while (!pq.empty()) {res.push_back(pq.top().first);pq.pop();}return res;}
};

703. 数据流中的第 K 大元素

class KthLargest {
private:priority_queue<int, vector<int>, greater<int>> _pq;int _k;
public:KthLargest(int k, vector<int>& nums) {_k = k;for (auto& num : nums) {add(num);}}int add(int val) {_pq.push(val);if (_pq.size() > _k) {_pq.pop();}return _pq.top();}
};/*** Your KthLargest object will be instantiated and called as such:* KthLargest* obj = new KthLargest(k, nums);* int param_1 = obj->add(val);*/

295. 数据流的中位数

大顶堆维护左半部分数据
小顶堆维护右半部分数据

class MedianFinder {
public:priority_queue<int, vector<int>, less<int>> leftHeap;priority_queue<int, vector<int>, greater<int>> rightHeap;MedianFinder() {}void addNum(int num) {if (leftHeap.size() == rightHeap.size()) {rightHeap.push(num);leftHeap.push(rightHeap.top());rightHeap.pop();} else {leftHeap.push(num);rightHeap.push(leftHeap.top());leftHeap.pop();}}double findMedian() {return leftHeap.size() == rightHeap.size() ? (leftHeap.top() + rightHeap.top()) * 0.5 : leftHeap.top();}
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/

23. 合并 K 个升序链表

优先队列

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:struct compare {bool operator() (const ListNode* lhs, const ListNode* rhs) {return lhs->val > rhs->val;}};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, compare> pq;for (auto& node : lists) {if (node != nullptr) {pq.push(node);}}ListNode* dummy = new ListNode(-1);ListNode* cur = dummy;while (!pq.empty()) {ListNode* node = pq.top();pq.pop();cur->next = node;cur = cur->next;if (node->next != nullptr) {pq.push(node->next);}}return dummy->next;}
};

二分+递归

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (list1 == nullptr) {return list2;}if (list2 == nullptr) {return list1;}if (list1->val < list2->val) {list1->next = mergeTwoLists(list1->next, list2);return list1;} else {list2->next = mergeTwoLists(list1, list2->next);return list2;}return nullptr;}ListNode* mergeLists(vector<ListNode*>& lists, int left, int right) {if (left > right) {return nullptr;}if (left == right) {return lists[left];}int mid =  left + (right - left) / 2;return mergeTwoLists(mergeLists(lists, left, mid), mergeLists(lists, mid + 1, right));}ListNode* mergeKLists(vector<ListNode*>& lists) {return mergeLists(lists, 0, lists.size() - 1);}
};