【力扣】堆相关总结

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;}
};