无妄，往吉

0%

Heap and Sliding Window

发表于
本文字数： 4.1k 阅读时长 ≈ 4 分钟

针对数据结构中的堆(Heap)，素来比较陌生，也不知道该如何使用。今天来理一理堆的概念。堆(Heap)又称优先队列(Priority Queue)，其内部元素并非按照一般的“先进先出”原则，而是按照优先级取出元素。此外，堆又可分为大根堆与小根堆。为了更清晰地了解堆的使用，来看一道算法题：

480. 滑动窗口中位数

中位数是有序序列最中间的那个数。如果序列的大小是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。

例如：

[2,3,4]，中位数是3

[2,3]，中位数是 (2 + 3) / 2 = 2.5​

给出一个数组 nums，有一个大小为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

Simple Test Cases
1
2
3
4
5
6
7
8
9
10
11
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[1,-1,-1,3,5,6]
解释：
窗口位置                         中位数
---------------                -------
[1  3  -1] -3  5  3  6  7         1
 1 [3  -1  -3] 5  3  6  7        -1
 1  3 [-1  -3  5] 3  6  7        -1
 1  3  -1 [-3  5  3] 6  7         3
 1  3  -1  -3 [5  3  6] 7         5
 1  3  -1  -3  5 [3  6  7]        6

方法一（超时）：

对于这道题，直观的感觉是维护一个有序的双端队列，将滑动窗口内的元素加入到该有序双端队列之内，并依照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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <deque>
#include <stack>
#include <vector>

using namespace std;

class Solution
{
public:
    void push(deque<long> &window, int value) {
        int back = window.back();
        stack<long> preserve;
        while (back > value && !window.empty()) {
            preserve.push(back);
            window.pop_back();
            back = window.back();
        }

        window.push_back(value);
        while (!preserve.empty()) {
            long top = preserve.top();
            window.push_back(top);
            preserve.pop();
        }
    }

    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        vector<double> medians;

        if (nums.empty()) return medians;

        for (int i = 0; i < nums.size() - (k - 1); ++i) {
            deque<long> window {nums[i]};

            for (int j = i + 1; j <= i + (k - 1); ++j) {
                int front = window.front(), back = window.back();
                if (nums[j] <= front) {
                    window.push_front(nums[j]);
                } else {
                    if (nums[j] >= back) {
                        window.push_back(nums[j]);
                    } else {
                        push(window, nums[j]);
                    }
                }
            }

            double median = 0;
            if (k % 2 == 0) {
                median = (window[k / 2] + window[k / 2 - 1]) / (double)2;
            } else {
                median = window[k / 2];
            }
            medians.push_back(median);
        }

        return medians;
    }
};

对于简单的用例，上述方法能够正确获得中位数序列，但假如输入的用例比较复杂呢？超时的问题如何解决？

方法二

首先，我们维护两个堆：

  • 一个大根堆 lo，用来存放较小的那一半的元素；
  • 一个小根堆 hi，用来存放较大的那一半的元素。

由此，堆顶的元素即为中位数。接下来，使用哈希集合（HashSet）或者哈希映射（HashMap），记为 hash_table，标记所有被移除的无效元素，哈希表的大小等于在堆中无效元素的数量；大根堆 lo 最多允许比小根堆 hi 存放多一个元素，当我们已经处理了 k 个元素时：

  • 如果 k = 2n + 1 为奇数，那么 lo 中存储 k + 1 个元素，hi 中存储 k 个元素；
  • 如果 k = 2n 为偶数，那么 lo 和 hi 中都存储 k 个元素；

如何判断两个堆是否平衡呢？我们引入balance变量，表示两个堆是否平衡：

  • 如果 balance == 0，那么两个堆平衡；
  • 如果 balance < 0，那么 lo 中的元素较少，需要从 hi 中取出若干个元素放入 lo；
  • 如果 balance > 0，那么 hi 中的元素较少，需要从 lo 中取出若干个元素放入 hi。

此时我们需要插入一个新的元素 in_num：

  • 如果 in_num 小于等于 lo 的堆顶元素，那么它可以被放入 lo 中，此时需要增加 balance 的值；
  • 否则，in_num 可以被放入 hi 中，此时需要减少 balance 的值。

延迟删除被移出窗口的元素 out_num：

  • 如果 out_num 在 lo 中，那么需要减少 balance 的值；
  • 如果 out_num 在 hi 中，那么需要增加 balance 的值；
  • 我们将 out_num 放入哈希表中；
  • 每当无效的元素出现在堆顶，我们就将其从堆中删除，同时从哈希表中删除。

由此，我们得到代码：

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <deque>
#include <stack>
#include <vector>

using namespace std;

vector<double> medianSlidingWindow(vector<int>& nums, int k)
{
    vector<double> medians;
    unordered_map<int, int> hash_table;
    priority_queue<int> lo;                                 // max heap
    priority_queue<int, vector<int>, greater<int> > hi;     // min heap

    int i = 0;      // index of current incoming element being processed

    // initialize the heaps
    while (i < k)
        lo.push(nums[i++]);
    for (int j = 0; j < k / 2; j++) {
        hi.push(lo.top());
        lo.pop();
    }

    while (true) {
        // get median of current window
        medians.push_back(k & 1 ? lo.top() : ((double)lo.top() + (double)hi.top()) * 0.5);

        if (i >= nums.size())
            break;              // break if all elements processed

        int out_num = nums[i - k],          // outgoing element
            in_num = nums[i++],             // incoming element
            balance = 0;                    // balance factor

        // number `out_num` exits window
        balance += (out_num <= lo.top() ? -1 : 1);
        hash_table[out_num]++;

        // number `in_num` enters window
        if (!lo.empty() && in_num <= lo.top()) {
            balance++;
            lo.push(in_num);
        }
        else {
            balance--;
            hi.push(in_num);
        }

        // re-balance heaps
        if (balance < 0) {        // `lo` needs more valid elements
            lo.push(hi.top());
            hi.pop();
            balance++;
        }
        if (balance > 0) {        // `hi` needs more valid elements
            hi.push(lo.top());
            lo.pop();
            balance--;
        }

        // remove invalid numbers that should be discarded from heap tops
        while (hash_table[lo.top()]) {
            hash_table[lo.top()]--;
            lo.pop();
        }
        while (!hi.empty() && hash_table[hi.top()]) {
            hash_table[hi.top()]--;
            hi.pop();
        }
    }

    return medians;
}

以上！