算法数据结构

哈希索引堆的索引优化：给 key 绑定自增 id，支持对给定 key 的删改操作

字数统计: 2.9k字   |   阅读时长: 13分
, ,

摘要: 哈希索引堆的优化，给 key 绑定自增 id，维护 id 到堆中节点的映射，支持对给定 key 的删改操作

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

$0 背景：哈希索引堆

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

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

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

一种直观的想法是直接对 key 做哈希索引，这是首先想到的思路，性能不一定好，但是很直接。参考 哈希索引堆。虽然思路很直接，但是如果没有任何优化的话，效果一般会很差。下面我们看看有哪些优化的手段。

实战中 key 和索引的结构可以根据场景优化，有些时候甚至可以直接用数组下标代替，省去哈希这一步(性能提升较大)，但是编码比较难。

$1 优化1：分配唯一 ID

(1) 分配唯一 ID

在直接哈希索引的办法中(Ref: 哈希索引堆)，索引结构是这样的。

1
2
unordered_map<int, unordered_set<int>> mapping;
// mapping[key] := key 对应的下标集合

这里直接把堆的数据数组中存储的值当成了哈希索引的 key，它也是堆按照大小比较依据进行比较的值。这个值在数据数组各个节点上是不唯一的，所以 mapping[key] 不是一个单一节点，而是节点集合(数据数组的下标集合)。

如果 mapping[key] 中的 key 在每个数据节点是唯一的，那索引结构可以改为以下结构，少了一层 unordered_set<int> 还是提升不少。

1
2
unordered_map<int, int> mapping;
// mapping[key] := key 对应的下标

这种每个数据上唯一的 key，在很多场景中的是自带的，例如在进程优先级调度时，进程 ID 是堆中维护的每个数据都天然自带的。

有些时候，调用方自己的业务逻辑中处理的数据，并没有天然自带 ID，可以给每个数据分配一个 ID，分配 ID 有很多成熟算法可以选用。每接到一个数据，给数据分配一个 ID 并打包成结构体，再将结构题整体压堆，哈希索引就用分配的 ID。

1
2
3
4
5
6
struct Item
{
    int val;
    int id;
    Item(int val, int id):val(val),id(id){}
};

分配 ID 最简单的方式是直接把每个数据的访问次序作为 ID 赋给每个数据。

堆中维护的数据在调用方经常是通过线性遍历的方式访问的，有可能是接收数据流，有可能是直接遍历数组或其它数据结构。这样数据按照访问次序可以给定一个 ID，如果是从前向后遍历数组，那么可以直接把数组下标作为 ID。

(2) 实现

接口，整体逻辑与直接哈希索引中实现的完全一样，只是每个数据多了一个 ID 字段，哈希索引的依据改为这个新增的 ID 字段。

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
struct Item
{
    int val;
    int id;
    Item(int val, int id):val(val),id(id){}
    Item(){}
    bool operator<(const Item& i) const
    {
        return this -> val < i.val; // 大顶堆
    }
};

class IndexMaxHeap
{
public:
    IndexMaxHeap()
    {
        data.assign(1, Item(-1, -1));
        _size = 0;
    }

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

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

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

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

    void remove(const int id)
    {
        if(mapping.count(id) == 0)
            return;
        int i = mapping[id];
        _remove(i);
    }

    void change(int id, int new_key)
    {
        if(mapping.count(id) == 0)
            return;
        int i = mapping[id];
        if(data[i].val == new_key)
            return;
        data[i].val = new_key;
        push_up(i);
        push_down(i);
    }

    int size()
    {
        return _size;
    }

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

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

    void dilatation()
    {
        vector<Item> tmp_data((_size + 1) * 2 + 1, Item(-1, -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.erase(data[i].id);
        data[i] = data[_size--];
        mapping[data[i].id] = i;
        push_up(i);
        push_down(i);
    }

    void push_up(int i)
    {
        if(i > _size) return;
        while(i / 2 > 0 && data[i / 2].val < data[i].val)
        {
            swap(mapping[data[i].id], mapping[data[i / 2].id]);
            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].val > data[ori].val)
            ori = left;
        if(right <= _size && data[right].val > data[ori].val)
            ori = right;
        if(ori != i)
        {
            swap(mapping[data[i].id], mapping[data[ori].id]);
            swap(data[i], data[ori]);
            push_down(ori);
        }
    }
};

(3) 代码测试

1
2
3
更新窗口端点时:
用 change(id, new_key);             1136ms
用 remove(id) + push(new_item);     1532ms

比对 key 直接加哈希索引有明显优化。约等于于直接对 key 做惰性更新的方式。

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
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty()) return vector<int>();
        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});
        }
        vector<Item> items;
        for(int i = 0; i < n; ++i)
            items.emplace_back(nums[i], i);
        // 滑动 n - k 次
        // 0..k-1
        IndexMaxHeap heap;
        heap.build(vector<Item>(items.begin(), items.begin() + k));
        vector<int> result;
        result.push_back(heap.top());
        for(int i = k; i < n; ++i)
        {
            heap.change(items[i % k].id, items[i].val);
            // heap.remove(i - k);
            // heap.push(items[i]);
            result.push_back(heap.top());
        }
        return result;
    }
};

$2 优化2：vector 代替 unordered_map

(1) vector 代替 unordered_map

当分配的 ID 是从 0 开始线性增长的时候。内部的哈希索引结构 mapping 可以考虑用数组实现。

1
2
vector<int> mapping;
// mapping[id] := id 对应数据的位置，-1 表示数据不存在，-2 表示已经被删除

mapping 的长度始终与 data 同步。即每次扩容的时候，data 和 mapping 的长度同步更新。比如 data 长度为 N + 1 ，可以容纳 N 个数据。则 mapping 的长度为 N, 刚好索引这 N 个数据。

当 _size + 1 >= (int)data.size() 或者 id >= (int)mapping.size() 的时候，均会触发扩容，新容量为 max((_size + 1) * 2 + 1, id * 2 + 1)。

(2) 实现

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
150
151
152
153
154
155
156
157
158
struct Item
{
    int val;
    int id;
    Item(int val, int id):val(val),id(id){}
    Item(){}
    bool operator<(const Item& i) const
    {
        return this -> val < i.val; // 大顶堆
    }
};

class IndexMaxHeap
{
public:
    IndexMaxHeap()
    {
        data.assign(1, Item(-1, -1));
        _size = 0;
    }

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

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

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

    void push(const Item& key)
    {
        if(_size + 1 >= (int)data.size() || key.id >= (int)mapping.size())
            dilatation(key.id);
        ++_size;
        data[_size] = key;
        mapping[key.id] = _size;
        push_up(_size);
    }

    void remove(const int id)
    {
        if(mapping[id] < 0)
            return;
        int i = mapping[id];
        _remove(i);
    }

    void change(int id, int new_key)
    {
        if(mapping[id] < 0)
            return;
        int i = mapping[id];
        if(data[i].val == new_key)
            return;
        data[i].val = new_key;
        push_up(i);
        push_down(i);
    }

    int size()
    {
        return _size;
    }

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

private:
    vector<Item> data; // keys
    int _size;
    vector<int> mapping; // id -> idxs

    void dilatation(int id=-1)
    {
        int target = _size + 1;
        if(id != -1)
            target = max(target, id + 1);
        int new_capacity = target * 2 + 1;
        vector<Item> tmp_data(new_capacity, Item(-1, -1));
        vector<int> tmp_mapping(new_capacity - 1, -1);
        for(int i = 1; i <= _size; ++i)
            tmp_data[i] = data[i];
        for(int i = 0; i < (int)mapping.size(); ++i)
            tmp_mapping[i] = mapping[i];
        data.swap(tmp_data);
        mapping.swap(tmp_mapping);
    }

    void _remove(int i)
    {
        if(i > _size)
            return;
        if(i == _size)
        {
            mapping[data[_size].id] = -2;
            --_size;
            return;
        }
        mapping[data[i].id] = -2;
        data[i] = data[_size--];
        mapping[data[i].id] = i;
        push_up(i);
        push_down(i);
    }

    void push_up(int i)
    {
        if(i > _size) return;
        while(i / 2 > 0 && data[i / 2].val < data[i].val)
        {
            swap(mapping[data[i].id], mapping[data[i / 2].id]);
            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].val > data[ori].val)
            ori = left;
        if(right <= _size && data[right].val > data[ori].val)
            ori = right;
        if(ori != i)
        {
            swap(mapping[data[i].id], mapping[data[ori].id]);
            swap(data[i], data[ori]);
            push_down(ori);
        }
    }
};

(3) 代码测试

只是 IndexMaxHeap 的实现变了，业务代码不变。结果如下：

1
2
3
更新窗口端点时:
用 change(id, new_key);             616ms
用 remove(id) + push(new_item);     660ms

(4) 问题

这样做有个问题，就是数据经过多次插入删除之后，数据数组在交替的插入删除操作下大致保持平衡，而分配的 ID 却在这个过程中越来越大。

根据是否知道总数据量，可以考虑以下方法。

知道总数据量

  • 建堆的时候直接开长为 N 的数据数组和索引的空间，此后都在这个空间下操作，不会触发扩容。

这种办法的场景限制比较大(提前知道数据量 <= N)，但是分配的 ID 具有下标意义，因此调用方不需要额外成本就可以把数据和 ID 对应起来。

当外面是通过遍历一个固定长度的数组来遍历所有数据的时候，这种办法很适用，数组下标直接就是 ID，并且大小可控。

数据量未知

  • 在外面维护一个已删除 ID 的有序集合，数据插入前分配 ID 时，优先分配已经删除的 ID，这样索引数据长度也会在交替的插入删除下大致保持平衡。

将已删除 ID 从小到大重新分配，本身是一个比较独立的组件，经常与各种加索引的数据 【设计难题】力扣1500-设计文件分享系统。

这种办法可以适应数据量不确定的场景，调用方需要额外的成本维护数据和分配的 ID 的对应关系，以及哪些 ID 是被删掉的。

实践起来未必比索引堆内部用 unordered_map 但是调用方不用额外维护 ID 信息的做法好。因为内部虽然把 unordered_map 改成了 vector，但是外面需要数据结构维护 ID 信息。

总结

  • 不论哪种情况，维护 ID 的操作都是在调用方做，也就是调用方需要对数据或 ID 的分配情况有所了解，索引堆内部不参与 ID 的分配逻辑。
  • 如果第一种情况满足，那么用第一种办法是一个很好的优化。
Share