下标索引堆:key 是大对象时,如何实现可对给定 key 删改的堆

  |  

摘要: 下标索引堆,思想,代码模板,例子

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


$0 背景

(1) 支持按 key 删除的堆

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

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

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

(2) 哈希索引堆

一种直观的想法是直接对 key 做哈希索引,这是首先想到的思路,性能不一定好,但是很直接。参考 哈希索引堆

(3) 标记删除 + 惰性更新

另外一种办法类似于 GC 中常见的标记-清除算法,是基于惰性更新的思想,先标记删除,访问到该数据的时候才真正删除。参考 堆的标记删除

(4) 哈希索引堆的索引优化

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


$1 下标索引堆

(1) ID从1自增时用vector代替unordered_map的哈希索引堆

为了按 key 删除或修改,采用最直观的对 key 直接加哈希索引形成哈希索引堆。对哈希索引的常规优化,涉及到两个方面:

  • 第一个是在将数据压堆之前分配一个唯一 ID。
  • 第二个是如果分配的 ID 是从 1 开始自增的,将索引堆内部的 unordered_map 改为 vector

在哈希索引堆的基础上增加以上两个优化,形成了 ID从1自增时用vector代替unordered_map的哈希索引堆,并解决滑动窗口最大值问题,性能取得明显优化。

参考 哈希索引堆的索引优化

遗留问题:ID 越来越大

ID从1自增时用 vector 代替 unordered_map 的哈希索引堆有个问题,就是数据经过多次插入删除之后,数据数组在交替的插入删除操作下大致保持平衡,而分配的 ID 却在这个过程中越来越大。

此时按照是否了解数据量,有两种方法。

<1> 数据量未知

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

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

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

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

<2> 了解总数据量

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

这种方法相当于对 ID 无限增长的问题视而不见,但是因为能保证数据量小于 N,视为没有这个问题。

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

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

(2) 内部树形索引

当已知数据量 <= N 的情况下用这种 ID 从 1 自增时用 vector 代替 unordered_map 的哈希索引堆是一种比较有效的索引堆。

如果数据数组中的对象很重的时候,维护堆的元素大量交换产生的代价不可接受的话,可以让存数据的数组 data 不变,中间加一层数组形式的树形索引 indexes

  • data 只有在插入的时候改变。
  • 删除的时候, data 不做改变,只在 indexes 做相应的调度和修改。
  • 调整堆的过程在 indexes 做。

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

由于有数据 <= N 这个可控的条件,因此调用方很容易维护数据和 ID 的对应关系。

data 除了插入的时候是不修改的,即插入的时候插入到 data 的哪个下标 idx,直到该数据删除的时候依然在 data[idx],该数据的索引也是 idx。

每个数据在堆中维护的整个生命周期,data 对调用方都是透明的。因此数据在 data 的什么位置完全由调用方指定,插入的时候就需要提供下标,即该数据插入在 data 的什么位置。

而数据的索引恰恰是数据插入时在 data 上的下标,即 push(int val, int idx) 插入时提供的 idx 交给索引堆的既是该数据的索引,也是数据 val 在 data 上的下标

(3) 外层哈希索引

充当哈希索引的 idx,通过 mapping 指向该数据在索引堆的逻辑位置,即 mapping[idx] 指向的是 indexes 中对应的位置。data[indexes[i]] 是按照堆的特性排序的。

数据的索引并不需要在 data 的节点上保存了,因为 data[idx] 的索引就是 idx,而 idx 本身就是插入时由调用方提供的并且整个生命周期不变,因此插入的时候不需要再把索引包装成结构体存在 data 上了

(4) 堆的调整

调整的时候,通过比较 data[indexes[i]]data[indexes[j]] 决定是否要交换,如果交换,则交换 indexes[i]indexes[j]


$2 下标索引堆的实现

数据结构设计

1
2
3
4
5
vector<int> data;
vector<int> indexes; // 数组形式树形索引 i -> data[indexes[i]]
vector<int> mapping; // 数组形式哈希索引 mapping[indexes[i]] = i
// data[i] = data[indexes[mapping[i]]]
int _size;

代码 (C++,模板)

大顶堆,小顶堆只需要把调整对的 push_uppush_down 改一下。

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
class IndexMaxHeap
{
public:
IndexMaxHeap()
{
_size = 0;
}

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

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

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

void push(int idx, const int key)
{
++idx;
// 覆盖 data[idx] 的数据, idx 同时也是 key 的索引
// mapping[idx] := key 在堆中的逻辑位置,即 indexes 中的位置
if(idx >= (int)data.size())
dilatation();
++_size;
data[idx] = key;
mapping[idx] = _size;
indexes[_size] = idx;
push_up(_size);
}

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

void change(int idx, const int new_key)
{
++idx;
if(mapping[idx] < 0)
return;
if(data[idx] == new_key)
return;
data[idx] = new_key;
int i = mapping[idx];
push_up(i);
push_down(i);
}

int size()
{
return _size;
}

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

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

void dilatation()
{
int new_capacity = (int)data.size() * 2 + 1;
vector<int> tmp_data(new_capacity, -1);
vector<int> tmp_indexes(new_capacity, -1);
vector<int> tmp_mapping(new_capacity, -1);
for(int i = 0; i < (int)data.size(); ++i)
{
tmp_data[i] = data[i];
tmp_indexes[i] = indexes[i];
tmp_mapping[i] = mapping[i];
}
data.swap(tmp_data);
indexes.swap(tmp_indexes);
mapping.swap(tmp_mapping);
}

void _remove(int i)
{
if(i > _size)
return;
if(i == _size)
{
mapping[indexes[_size]] = -2;
--_size;
return;
}
int idx_i = indexes[i];
int idx_j = indexes[_size];
swap(mapping[idx_i], mapping[idx_j]);
indexes[i] = indexes[_size--];
mapping[idx_i] = -2;
push_up(i);
push_down(i);
}

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

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

$3 代码测试

1
2
3
更新窗口端点时:
用 change(id, new_key); 572ms
用 remove(id) + push(new_item); 648ms
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 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];
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});
}
// 滑动 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(i % k, nums[i]);
// heap.remove(i - k);
// heap.push(i, nums[i]);
result.push_back(heap.top());
}
return result;
}
};
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(i % k, nums[i]);
// heap.remove(i - k);
// heap.push(i, nums[i]);
result.push_back(heap.top());
}
return result;
}
};

Share