【力扣】堆相关总结
priority_queue
`std::priority_queue` 是 C++ 标准库中的一个容器适配器，提供了堆（Heap）数据结构的功能。它通常用于实现优先队列，允许你高效地插入元素和访问最大或最小元素。
头文件
#include <queue>基本定义
`std::priority_queue` 默认是一个最大堆（Max-Heap），即堆顶元素是最大的元素。其模板定义如下：
template<
class T,
class Container = std::vector<T>,
class Compare = std::less<typename Container::value_type>
> class priority_queue;参数解释
1. T: 元素类型。
2. Container: 存储元素的底层容器，默认为 `std::vector<T>`。
3. Compare: 比较函数对象，默认为 `std::less<T>`，这意味着默认创建的是最大堆。
创建优先队列
默认最大堆
priority_queue<int> maxHeap;这会创建一个存储整数的最大堆。
最小堆
如果你想创建一个最小堆（即堆顶是最小元素），可以指定比较函数为 `greater<T>`：
#include <functional>
priority_queue<int, vector<int>, greater<int>> minHeap;对复杂类型的堆
对于复杂类型如 `pair<int, int>`，可以这样创建最大堆和最小堆：
// 默认最大堆
priority_queue<pair<int, int>> maxHeap;
// 最小堆
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;基本操作
插入元素
使用 `push()` 方法向优先队列中添加元素：
maxHeap.push(10);
minHeap.push({5, 100});访问堆顶元素
使用 `top()` 方法获取堆顶元素（但不移除它）：
int topElement = maxHeap.top();移除堆顶元素
使用 `pop()` 方法移除堆顶元素：
maxHeap.pop();检查优先队列是否为空
使用 `empty()` 方法检查优先队列是否为空：
if (!maxHeap.empty()) {
// 队列非空
}获取优先队列的大小
使用 `size()` 方法获取优先队列中的元素数量：
int size = maxHeap.size();自定义比较函数
#如果你需要根据特定规则对元素进行排序，可以通过提供自定义的比较函数来实现。例如，假设我们有一个 `pair<int, int>` 类型的数据，并且我们希望根据第一个元素进行排序：
#最大堆（基于第一个元素）
struct CompareFirst {
bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
return a.first < b.first; // 对于最大堆
}
};
priority_queue<pair<int, int>, vector<pair<int, int>>, CompareFirst> customMaxHeap;
#最小堆（基于第一个元素）
struct CompareFirst {
bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
return a.first > b.first; // 对于最小堆
}
};
priority_queue<pair<int, int>, vector<pair<int, int>>, CompareFirst> customMinHeap;使用模版应注意：
greater<pair<int, int>> 默认会按如下规则比较两个 pair<int, int>：
-
首先比较
pair.first -
如果
pair.first相同，则比较pair.second
215.数组中的第K个最大元素
可以直接使用堆：
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> heap;
for(int i=0;i<nums.size();i++){
heap.push(nums[i]);
}
while(--k>0){
heap.pop();
}
return heap.top();
}
};也可以手搓堆：
class Solution {
public:
void maxHeapify(vector<int>& nums,int i,int heapSize){
int l = i*2+1;
int r = i*2+2;
int largest = i;
if(l<heapSize && nums[l]>nums[largest]){
largest = l;
}
if(r<heapSize && nums[r]>nums[largest]){
largest = r;
}
if(i!=largest){
swap(nums[i],nums[largest]);
maxHeapify(nums,largest,heapSize);
}
}
void buildMaxHeap(vector<int>& nums,int heapSize){
for(int i=heapSize/2-1;i>=0;i--){
maxHeapify(nums,i,heapSize);
}
}
int findKthLargest(vector<int>& nums, int k) {
int heapSize = nums.size();
buildMaxHeap(nums,heapSize);
for(int i=nums.size()-1;i>=nums.size()-k+1;i--){
swap(nums[i],nums[0]);
heapSize--;
maxHeapify(nums,0,heapSize);
}
return nums[0];
}
};
347.前K个高频元素
这道题就是维护一个小根堆。
如果小根堆容量小于k，则直接push入堆
否则就和堆顶元素出现的频率比较，如果大于堆顶元素出现的频率，就push入堆
因为使用了greater模板，所以入堆时应该是{频率，数值} 这样才会默认先比较频率
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> mp;
//key:元素值 value:频率
for(int i=0;i<nums.size();i++){
mp[nums[i]]++;
}
vector<pair<int,int>> vec(mp.begin(),mp.end());
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> heap;
for(auto v:vec){
if(heap.size()<k){
heap.push({v.second,v.first});
}else if(heap.top().first < v.second){
heap.pop();
heap.push({v.second,v.first});
}
}
vector<int> res;
for(int i=0;i<k;i++){
res.push_back(heap.top().second);
heap.pop();
}
return res;
}
};