优先队列：

• 大根堆：priority_queue<int> maxHeap;
• 小根堆：priority_queue<int, vector<int>, greater<int>> minHeap;

自定义比较器：

struct Comparator {  
    bool operator()(ListNode *a,ListNode *b) {
        return a->val > b->val; //代表小根堆，因为如果返回true，就表示左侧元素的优先级低于右侧元素(有点反直觉)
    }
};
priority_queue<ListNode*, vector<ListNode* >, Comparator> queue;

※找第k大/前k大元素优先使用小根堆，反之亦然

---

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

Solution1大根堆：把所有元素压入堆，再弹出k-1个元素，此时堆顶就是第k大的元素（性能比小根堆差，需要不断调整大根堆的堆顶来排除较小的元素）

Solution2小根堆：维护一个容量为k的小根堆，在容量达到k后，元素大于堆顶元素才能压入堆，遍历完所有元素后堆顶就是第k大的元素

class Solution1 {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> maxHeap;
        
        for(const auto &i : nums) maxHeap.push(i);
        while(--k) maxHeap.pop(); //注意不是k--

        return maxHeap.top();
    }
};

class Solution2 {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> minHeap;

        for(const auto &i : nums) {
            if(minHeap.size() < k || minHeap.top() < i) {
                minHeap.push(i);
                if(minHeap.size() > k) minHeap.pop(); //超出容量时弹出最小元素
            }       
        }
 
        return minHeap.top();
    }
};

---

347. 前 K 个高频元素❌

map用来通过元素映射到数量，堆里存pair用来通过数量映射到元素

class Solution {
public:
    struct Comparator {  
        bool operator()(const pair<int, int> &a, const pair<int, int> &b) {
            return a.second > b.second; //定义小根堆
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> res(k);
        unordered_map<int ,int> mp;
        priority_queue<pair<int, int>, vector<pair<int, int>>, Comparator> minHeap;

        for(const auto &i : nums) mp[i]++;

        for(unordered_map<int ,int>::iterator it = mp.begin(); it != mp.end(); it++) {
            if(minHeap.size() < k || it->second > minHeap.top().second) {
                minHeap.push(*it);
                if(minHeap.size() > k) minHeap.pop();
            }            
        }
        
        for(int i = k - 1; i >= 0; i--) {
            res[i] = minHeap.top().first;
            minHeap.pop();
        }

        return res;
    }
};

---

295. 数据流的中位数❌

一个小顶堆和一个大顶堆，各保存数组的一半元素

大根堆保存较小的一半 小根堆保存较大的一半

题解中每次插入元素不用比较大小的原因是：此时来了一个新的元素，我想插入小根堆，有两种情况，第一种他比大根堆的堆顶元素大，此时理论上可以直接插入小根堆（保存较大的一半元素）；第二种情况，他比大根堆的堆顶元素小，此时就不能直接插入小根堆，需要先插入大根堆维持较小的元素都在大根堆内，然后取大根堆的堆顶元素插入小根堆。为了统一操作，回到第一种情况，可以先统一把元素插入大根堆，然后此时大根堆基于自身的结构特性，会将该元素作为新的堆顶元素，此时再执行插入小根堆的操作就相当于此前在大根堆处过渡了一下，最终还是会插入小根堆（太™巧妙了）

class MedianFinder {
private:
    priority_queue<int> maxHeap; //大根堆 保存较小的一半
    priority_queue<int, vector<int>, greater<int>> minHeap; //小根堆 保存较大的一半
public:
    MedianFinder() {
    }
    
    void addNum(int num) {  //两边元素数量相等时优先压入小根堆
        if(minHeap.size() != maxHeap.size()) {
            minHeap.push(num);
            maxHeap.push(minHeap.top());
            minHeap.pop();
        } else {
            maxHeap.push(num);
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        }
    }
    
    double findMedian() {
        return minHeap.size() != maxHeap.size() ? minHeap.top() : (minHeap.top() + maxHeap.top()) / 2.0;

    }
};