思想

今天看看堆。堆是一种特殊的二叉树，分成最大堆和最小堆。最大堆中，树根是最大的元素；最小堆中，树根是最小的元素。在 C++ 中用堆，可以用优先队列，它的底层是堆实现，同时提供了一些常见的方法，使得我们可以把它当作堆来处理。

当遇到第 k 大，或者反复取最值的题目，或许堆是一个不错的考虑。

题目

215. Kth Largest Element in an Array

这题让我们找出一个数组中第 k 大的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq;

        for (int num : nums) {
            pq.push(num);

            if (pq.size() > k) {
                pq.pop();
            }
        }

        return pq.top();
    }
};

有些反直觉，明明要求第 k 大 的元素，结果用了一个最小堆。是的，对于这种第 k 大的题目，可以用一个有限长度的最小堆，这样可以一下子得到第 k 个元素，而不需要 pop k 次后才得到结果。

这里还是费一些笔墨讲关于优先队列的定义，接收 3 个参数：元素类型、实现优先队列的容器，以及比较方法。前两个不必多说，一般是 foo、vector<foo> 的形式。比较运算要接收一个类型，具体在合并 k 个有序链表中有提到。此外，如果仅仅想让默认的最大堆变成最小堆，可以传入 greater<int>。

怎样看是最大堆还是最小堆？比较运算 a ?? b 在成立的时候，b 优先级比 a 高。所以如果 a > b，这是一个最小堆。

295. Find Median from Data Stream

这题算是个小模拟，可以进行压数操作和找中位数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class MedianFinder {
private:
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
public:
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        maxHeap.push(num);
        minHeap.push(maxHeap.top());
        maxHeap.pop();

        if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }
    
    double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.top();
        } else {
            return (maxHeap.top() + minHeap.top()) / 2.0;
        }
    }
};

是一道 Hard，但是如果稍微分析下，其实并不是很复杂。

既然是寻找中位数，自然的想法是，要把输入分成两部分，从中间对半分，左边是小的那一堆，右边是大的那一堆。这样的话，如果确保左侧个数 >= 右侧，那中位数根据数列的奇偶性，很好求得。

问题转变为，如何把数组分成两半，且容易维护呢？说是分成两半，其实我们只在乎边界：左侧那一半的最大值和右侧那一半的最小值。每接收一个值的输入，导致数列的长度发生变化，需要在左右之间调整，把左侧的最大值移动到右侧。反复地获取最大值，这符合引言中堆的应用场景。

此外，有时候还需要把右侧的最小值挪回左边，那么右侧用一个最小堆。

关于这两个堆之间的腾挪，主要的目的是为了让数组在奇数长度时，最大堆的堆顶存放中位数；偶数长度时，最大堆和最小堆的长度相等，且堆顶是各是距离中位数最近的值。构造的顺序保证了这个数学性质

$$
最小堆大小 \in [最大堆大小 - 1, 最大堆大小]
$$

347. Top K Frequent Elements

找出一段数组中，出现频率前 K 个的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> mp;

        for (int num : nums) {
            mp[num]++;
        }

        priority_queue<pair<int, int>> pq;

        for (auto &[key, cnt] : mp) {
            pq.push({cnt, key});
        }

        vector<int> ans;

        for (int i = 0; i < k; i++) {
            ans.push_back(pq.top().second);
            pq.pop();
        }

        return ans;
    }
};

这题需要做个预处理，先遍历数组，记录每个元素出现的次数。随后，用一个堆实现排序。这里既可以用一个最大堆，随后弹出 k 次；也可以用一个长度为 k 的最小堆，弹出到堆为空。个人认为前者的实现相对容易。