算法数据结构

对顶堆

字数统计: 1.3k字   |   阅读时长: 6分
, ,

摘要: 对顶堆的思想，在中位数问题中的应用

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 二叉堆 中，我们详细学习了二叉堆的原理、代码模板，以及在排序中的应用。

对于一些中位数问题，我们可以将两个容量相等的堆一起维护数据，一个堆放较大的一半，另一个堆放较小的一半。这样通过两个堆的堆头来查询中位数就非常直接了。本文我们来看一下这个算法，然后解决数据流的中位数问题。

$0 场景

维护一个数据结构支持以下操作：

  • 插入 key
  • 查询当前数据结构中的中位 key

$1 对顶堆

以中位数为例，维护一个大顶堆，一个小顶堆，大顶堆，将大顶堆放左边，小顶堆放右边，两个队头对着。

从左向右看两个堆中的数据，恰好从大顶堆底到大顶堆顶到小顶堆顶到小顶堆底是递增的。

维护的时候始终保持两堆的数据量平衡，即左堆数据量始终等于右堆或者比右堆多一个。

平衡

1
2
3
4
5
左堆大小 > 右堆大小加1:
    将左堆堆顶弹出，压进右堆

左堆大小 < 右堆大小
    将右堆堆顶弹出，压进左堆

插入

1
2
3
如果左堆空或者数据小于等于左堆的堆顶，则插入左堆
如果数据比左堆的堆顶大，则插入右堆
平衡对顶堆

查询

1
2
3
4
左堆大小 = 右堆大小 + 1:
    左堆堆顶为中位数
左堆大小 = 右堆大小:
    两个堆顶的平均数为中位数

代码 (C++，模板)

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
class OppositeHeap {
public:
    OppositeHeap()
    {
        pq_right = priority_queue<int, vector<int>, greater<int>>();
        pq_left = priority_queue<int>();
        left_cnt = 0, right_cnt = 0;
    }

    double query()
    {
        double left = pq_left.top();
        if(left_cnt == right_cnt + 1)
            return left;
        double right = pq_right.top();
        return (left + right) / 2;
    }

    void insert(int x)
    {
        if(pq_left.empty() || x <= pq_left.top())
        {
            pq_left.push(x);
            ++left_cnt;
        }
        else
        {
            pq_right.push(x);
            ++right_cnt;
        }
        balance();
    }

private:
    priority_queue<int, vector<int>, greater<int>> pq_right;
    priority_queue<int> pq_left;
    int left_cnt, right_cnt;

    void balance()
    {
        if(left_cnt > right_cnt + 1)
        {
            pq_right.push(pq_left.top());
            pq_left.pop();
            ++right_cnt;
            --left_cnt;
        }
        else if(left_cnt < right_cnt)
        {
            pq_left.push(pq_right.top());
            pq_right.pop();
            ++left_cnt;
            --right_cnt;
        }
    }
};

$2 题目

295. 数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

  • 例如 arr = [2,3,4] 的中位数是 3 。
  • 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

  • MedianFinder() 初始化 MedianFinder 对象。

  • void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

  • double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

提示:

1
2
3
>-1e5 <= num <= 1e5
>在调用 findMedian 之前，数据结构中至少有一个元素
>最多 5 * 1e4 次调用 addNum 和 findMedian

示例 1：
输入
[“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]
解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

代码 (C++)

维护右堆大小与左堆大小相或者比左堆多1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class MedianFinder {
public:
    MedianFinder() {
        opposite_heap = OppositeHeap();
    }

    void addNum(int num) {
        opposite_heap.insert(num);
    }

    double findMedian() {
        return opposite_heap.query();
    }

private:
    OppositeHeap opposite_heap;
};

480. 滑动窗口中位数

本题在对顶堆的基础上还要结合标记删除，算法原理参考 力扣480-滑动窗口中位数。

代码 (C++)

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
class LabelOppositeHeap {
public:
    LabelOppositeHeap()
    {
        pq_right = priority_queue<int, vector<int>, greater<int>>();
        pq_left = priority_queue<int>();
        left_cnt = 0, right_cnt = 0;
        label = unordered_map<int, int>();
    }

    double query()
    {
        clear_left_top();
        clear_right_top();
        double left = pq_left.top();
        if(left_cnt == right_cnt + 1)
            return left;
        double right = pq_right.top();
        return ((double)left + (double)right) / 2;
    }

    void insert(int x)
    {
        clear_left_top();
        clear_right_top();
        if(pq_left.empty() || x <= pq_left.top())
        {
            pq_left.push(x);
            ++left_cnt;
        }
        else
        {
            pq_right.push(x);
            ++right_cnt;
        }
        balance();
    }

    void label_delete(int x)
    {
        clear_left_top();
        clear_right_top();
        if(x <= pq_left.top())
            --left_cnt;
        else
            --right_cnt;
        ++label[x];
        balance();
    }

private:
    priority_queue<int, vector<int>, greater<int>> pq_right;
    priority_queue<int> pq_left;
    int left_cnt, right_cnt;
    unordered_map<int, int> label; // 哈希索引，用作删除标记

    void clear_right_top()
    {
        while(!pq_right.empty() && label.count(pq_right.top()))
        {
            --label[pq_right.top()];
            if(label[pq_right.top()] == 0)
                label.erase(pq_right.top());
            pq_right.pop();
        }
    }

    void clear_left_top()
    {
        while(!pq_left.empty() && label.count(pq_left.top()))
        {
            --label[pq_left.top()];
            if(label[pq_left.top()] == 0)
                label.erase(pq_left.top());
            pq_left.pop();
        }
    }

    void balance()
    {
        if(left_cnt > right_cnt + 1)
        {
            pq_right.push(pq_left.top());
            pq_left.pop();
            ++right_cnt;
            --left_cnt;
        }
        else if(left_cnt < right_cnt)
        {
            pq_left.push(pq_right.top());
            pq_right.pop();
            ++left_cnt;
            --right_cnt;
        }
    }
};

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        LabelOppositeHeap label_opposite_heap;
        for(int i = 0; i < k; ++i)
            label_opposite_heap.insert(nums[i]);
        int n = nums.size();
        vector<double> result(n - k + 1);
        for(int i = k; i < n; ++i)
        {
            result[i - k] = label_opposite_heap.query();
            label_opposite_heap.label_delete(nums[i - k]);
            label_opposite_heap.insert(nums[i]);
        }
        result[n - k] = label_opposite_heap.query();
        return result;
    }
};
Share