Leetcode--堆类型题总结（单堆与双堆）_双堆leetcode

目录

 

1.C++中的堆实现

2.单堆问题

3.双堆问题

---

1.C++中的堆实现

可以直接用优先级队列priority_queue

默认是大顶堆 priority_queue<int> maxheap

小顶堆 priority_queue<int,vector<int>,greater<int>> minheap

也可以使用 multiset (使用multiset的情况一般为 需要从堆中删除元素，因为priority_queue的方法中没有 erase方法)

默认是小顶堆 multiset<int> minheap

大顶堆 multiset<int,greater<int>> maxheap

2.单堆问题

指通过一个堆就可以解决的问题

一般这种问题都具有以下特点：

求解第/前 k个最大，最小或是最频繁的元素；都可以使用堆来实现 （而不用通过排序实现）

模式：

确定大顶堆还是小顶堆

比如求 第K个最大元素，我们就用 大小为K的小顶堆，遍历数组完毕后，小顶堆堆顶元素即为第K个最大元素

遍历数组，压入小顶堆，判断小顶堆的元素个数，如果大于k，则弹出，保证小顶堆内元素个数始终是 k个

 

对于最频繁或是最不频繁的元素问题：可以首先结合 pair<int,int>对组 通过遍历统计，然后以 对组为 堆中元素进行 入堆

priority_queue<pair<int,int>,vector<pair<int,int>>,less<pair<int,int>>>  maxheap

 

比如：寻找第k个最大元素

求第k个最大元素，我们保留下来前k个最大元素即可，而前k个元素中我们又要最小的一个，所以我们可以使用小顶堆

保证小顶堆元素内个数不超过k即可，因为 随着我们压入元素，堆的大小增大，而小元素 一定在堆顶，所以 当堆的大小超过k时，就会 pop出去小元素，最后堆中剩下前k个大元素

class Solution {
public:
    int findKthLargest(vector<int>&