优先队列的底层是最大堆或最小堆
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);
}
};
