算法数据结构

哈希索引堆：维护 key 到堆中节点的哈希映射，支持对给定 key 的删改操作

字数统计: 2.1k字   |   阅读时长: 10分
,

摘要: 哈希索引堆，思想，代码模板，例子

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在常规的堆中，我们只能通过堆头访问堆中的最值元素，无法通过类似下标的方式访问堆中的其它元素。有的时候我们既想要堆的动态维护最值的性质，同时还想能够通过索引对堆中的任意元素做增删改查，此时就需要在堆的基础上增加索引。本文我们主要来看一下这类需求怎样实现。

本文会给出代码模板，并用几个主流解法解决过的题目进行测试。可以看到，哈希索引堆的想法虽然直接，但没有任何优化的话，一般效果不太好。

$0 场景

一般的堆不支持按key操作，例如按 key 删除，按 key 修改。

现实中这种需求是常见的，例如进程调度的时候，进程 ID 和进程优先级在一个堆中维护。直接删除某个进程 ID，以及根据进程 ID 修改进程优先级，都是很合理的需求。

如果真有需求的话，可以直接在内部加索引，使得给堆提供 key 之后，对内部可以找到该 key 对应的节点(数组下标)，这种内部加索引的堆为索引堆。

$1 哈希索引堆

直接对 key 做哈希索引是首先想到的思路，性能不一定好，因为 key 会有重复的情况，但是很直接。

实战中 key 和索引的结构可以根据场景优化，例如给数据分配一个唯一 ID，甚至可以直接用数组下标代替，省去哈希这一步(性能提升较大)，参考：

直接哈希索引

索引堆的实现直接用哈希索引最方便，这样在维护堆的过程中产生了数据移动，只需要同时更新索引即可。

数据结构设计

_size 表示堆中元素个数，data 为数据，mapping 为哈希索引 mapping[key] := key 在 data 中的下标集合：

1
2
3
vector<int> data; // keys
int _size;
unordered_map<int, unordered_set<int>> mapping; // key -> idxs

堆的基础操作

  • 调整堆 push_up(i), push_down(i)
  • 插入 push(key)
  • 查询最值 top()
  • 弹出堆顶 pop()
  • 建堆 build(nums)
  • 扩容 dilatation()

这些操作中当有关于 data[i] 的修改时，在改 data[i] 之前先修改索引 mapping[data[i]]。

如果有 swap(data[i], data[j])，在交换 data[i], data[j] 的索引前先判定下两个值是否相等。

索引堆新增操作：按 key 删除 remove(key)

调度到尾部删除即可：通过哈希索引找到节点下标 i 之后，将 data[i] 与 data[_size] 交换再更新索引，然后直接删除 data[_size]，再调整 data[i]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void remove(int key)
{
    if(mapping.count(key) == 0)
        return;
    int i = *mapping[key].begin();
    _remove(i);
}

void _remove(int i)
{
    if(i > _size)
        return;
    mapping[data[_size]].erase(_size);
    if(data[_size] != data[i])
    {
        mapping[data[_size]].insert(i);
        mapping[data[i]].erase(i);
        if(mapping[data[i]].empty())
            mapping.erase(data[i]);
    }
    data[i] = data[_size--];
    push_up(i);
    push_down(i);
}

完整代码 (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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
class IndexMaxHeap
{
public:
    IndexMaxHeap()
    {
        data.assign(1, -1);
        _size = 0;
    }

    void build(const vector<int>& nums)
    {
        data.clear();
        mapping.clear();
        int n = nums.size();
        data.assign(n + 1, 0);
        data[0] = -1;
        for(int i = 0; i < n; ++i)
        {
            data[i + 1] = nums[i];
            mapping[nums[i]].insert(i + 1);
        }
        _size = n;
        for(int i = n; i >= 1; --i)
            push_down(i);
    }

    int top()
    {
        if(empty())
            return -1;
        return data[1];
    }

    int pop()
    {
        if(empty())
            return -1;
        int ans = data[1];
        _remove(1);
        return ans;
    }

    void push(int key)
    {
        if(_size + 1 >= (int)data.size())
            dilatation();
        ++_size;
        data[_size] = key;
        mapping[key].insert(_size);
        push_up(_size);
    }

    void remove(int key)
    {
        if(mapping.count(key) == 0)
            return;
        int i = *mapping[key].begin();
        _remove(i);
    }

    void change(int key, int new_key)
    {
        if(mapping.count(key) == 0)
            return;
        if(key == new_key)
            return;
        int i = *mapping[key].begin();
        mapping[key].erase(i);
        if(mapping[key].empty())
            mapping.erase(key);
        data[i] = new_key;
        mapping[new_key].insert(i);
        push_up(i);
        push_down(i);
    }

    int size()
    {
        return _size;
    }

    bool empty()
    {
        return _size == 0;
    }

private:
    vector<int> data; // keys
    int _size;
    unordered_map<int, unordered_set<int>> mapping; // key -> idxs

    void dilatation()
    {
        vector<int> tmp_data((_size + 1) * 2 + 1);
        tmp_data[0] = 1;
        for(int i = 1; i <= _size; ++i)
            tmp_data[i] = data[i];
        data.swap(tmp_data);
    }

    void _remove(int i)
    {
        if(i > _size)
            return;
        mapping[data[_size]].erase(_size);
        if(data[_size] != data[i])
        {
            mapping[data[_size]].insert(i);
            mapping[data[i]].erase(i);
            if(mapping[data[i]].empty())
                mapping.erase(data[i]);
        }
        data[i] = data[_size--];
        push_up(i);
        push_down(i);
    }

    void push_up(int i)
    {
        if(i > _size) return;
        while(i / 2 > 0 && data[i / 2] < data[i])
        {
            mapping[data[i]].erase(i);
            mapping[data[i]].insert(i / 2);
            mapping[data[i / 2]].erase(i / 2);
            mapping[data[i / 2]].insert(i);
            swap(data[i], data[i / 2]);
            i /= 2;
        }
    }

    void push_down(int i)
    {
        int ori = i, left = i * 2, right = i * 2 + 1;
        if(left <= _size && data[left] > data[ori])
            ori = left;
        if(right <= _size && data[right] > data[ori])
            ori = right;
        if(ori != i)
        {
            mapping[data[i]].erase(i);
            mapping[data[i]].insert(ori);
            mapping[data[ori]].erase(ori);
            mapping[data[ori]].insert(i);
            swap(data[i], data[ori]);
            push_down(ori);
        }
    }
};

小顶堆

仅修改 push_down 和 push_up，将判断条件中比较 data[i] 和 data[i / 2], data[left], data[right] 的大于号和小于号互换即可.

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
void push_up(int i)
{
    if(i > _size) return;
    while(i / 2 > 0 && data[i / 2] > data[i])
    {
        mapping[data[i]].erase(i);
        mapping[data[i]].insert(i / 2);
        mapping[data[i / 2]].erase(i / 2);
        mapping[data[i / 2]].insert(i);
        swap(data[i], data[i / 2]);
        i /= 2;
    }
}

void push_down(int i)
{
    int ori = i, left = i * 2, right = i * 2 + 1;
    if(left <= _size && data[left] < data[ori])
        ori = left;
    if(right <= _size && data[right] < data[ori])
        ori = right;
    if(ori != i)
    {
        mapping[data[i]].erase(i);
        mapping[data[i]].insert(ori);
        mapping[data[ori]].erase(ori);
        mapping[data[ori]].insert(i);
        swap(data[i], data[ori]);
        push_down(ori);
    }
}

代码测试

912. 排序数组

单纯的数组排序，用索引堆并不好，仅测试哈希索引堆代码模板中基本功能实现的正确性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        IndexMaxHeap heap;
        heap.build(nums);
        vector<int> result;
        while(!heap.empty())
        {
            // cout << heap.top() << endl;
            result.push_back(heap.pop());
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

239. 滑动窗口最大值 / 剑指 Offer 59 - I. 滑动窗口的最大值

滑动窗口最大值最好的解法是单调队列，如果想用堆的话，必须解决滑窗左端点 nums[i - 1] 如何删除的问题，哈希索引堆是一个思路。

注：N = 100000, K = 10000 的 case 超时。

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
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty()) return vector<int>();
        cout << nums.size() << endl;
        int n = nums.size();
        if(n <= k)
        {
            int mx = nums[0];
            for(int i = 1; i < n; ++i)
                mx = max(mx, nums[i]);
            return vector<int>({mx});
        }
        // 滑动 n - k 次
        // 0..k-1
        IndexMaxHeap heap;
        heap.build(vector<int>(nums.begin(), nums.begin() + k));
        vector<int> result;
        result.push_back(heap.top());
        for(int i = k; i < n; ++i)
        {
            heap.change(nums[i - k], nums[i]);
            result.push_back(heap.top());
        }
        return result;
    }
};

480. 滑动窗口中位数

用对顶堆维护数据流的插入和中位数的查询。需要处理滑窗左侧元素的删除，哈希索引堆是一种方式。

将对顶堆中的堆改为哈希索引堆。无脑加哈希索引性能不一定好，对本题来说这个算法的耗时会有点长，有可能过不了。

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
class IndexOppositeHeap
{
public:
    IndexOppositeHeap(){}

    void insert(int x)
    {
        if(heap_left.empty() || x <= heap_left.top())
            heap_left.push(x);
        else
            heap_right.push(x);
        balance();
    }

    double query()
    {
        double left = heap_left.top();
        if(heap_left.size() == heap_right.size() + 1)
            return left;
        double right = heap_right.top();
        return ((double)left + (double)right) / 2;
    }

    void index_delete(int x)
    {
        if(!heap_left.empty() && x <= heap_left.top())
            heap_left.remove(x);
        else
            heap_right.remove(x);
        balance();
    }

private:
    IndexMaxHeap heap_left;
    IndexMinHeap heap_right;

    void balance()
    {
        if(heap_left.size() > heap_right.size() + 1)
        {
            heap_right.push(heap_left.top());
            heap_left.pop();
        }
        else if(heap_left.size() < heap_right.size())
        {
            heap_left.push(heap_right.top());
            heap_right.pop();
        }
    }
};

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        IndexOppositeHeap index_opposite_heap;
        for(int i = 0; i < k; ++i)
        {
            index_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] = index_opposite_heap.query();
            index_opposite_heap.index_delete(nums[i - k]);
            index_opposite_heap.insert(nums[i]);
        }
        result[n - k] = index_opposite_heap.query();
        return result;
    }
};
Share