索引堆
一、什么是索引堆？
索引堆（Index Heap）是二叉堆的一个变种，是二叉堆的一种增强。
相比于二叉堆只能访问堆顶元素，索引堆可以通过索引访问堆中的任意元素。
比如下面的索引堆：
1
2
3
4
5
| 1(30)
/ \
4(28) 3(16)
\ /
5(22) 2(12)
|
除了可以直接访问堆顶元素 30，还可以通过索引访问其他元素：
- 1: 30
- 2: 12
- 3: 16
- 4: 28
- 5: 22
这相当于给堆元素增加了索引，因此称为索引堆。
二、为什么用索引堆？
二叉堆，每次只能操作堆顶元素，没办法操作其他的元素。
在某些场景下，有时候需要操作一下非堆顶的元素，这种二叉堆就做不到了。
索引堆就是专门为了解决操作非堆顶元素问题而设计的。
三、索引堆如何实现？
一种简单的方式是给元素加上索引属性，但是这需要重新实现一套新代码。
但另一种常见方式是，基于现有的二叉堆来改造实现：
其结构类似这样子：
1
2
3
4
5
6
7
8
9
10
11
12
| 6(30)
/ \
4(28) 3(16) -- 索引堆结构
/ \ /
2(18) 5(22) 1(12)
___ ____ ____ ____ ____ ____ ____
| | 6 | 4 | 3 | 2 | 5 | 1 | -- 索引堆数组
___ ____ ____ ____ ____ ____ ____
| | 12 | 18 | 16 | 28 | 22 | 30 | -- 元素数组
|
其中，6(30) 表示索引为 6 的元素，对应的值为 30。
- 元素数组：按照元素索引保存，元素位置会一直保持不变
- 索引堆数组：保存的是元素索引，会按照堆的结构来调整位置
有了这两个数组，就能随意获取堆里面的元素了：
- 获取堆顶元素时，可通过索引堆数组获取
- 根据索引获取元素时，可通过元素数组获取
这其实相当于在二叉堆的基础上，加了一个中间层，用索引数组来替代元素数组建堆而已。
不过利用这种方式，就可以通过直接改造二叉堆的代码来实现索引堆了。
四、实际案例
问题描述：
多路归并问题，将多个有序的输入流，合并成一个有序的输出流。
解决方案：
这个问题，就可以使用索引堆来解决。
每个堆元素表示一路输入流，堆顶元素就是当前最小的那一路输入流。
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
|
IndexHeap<Integer> indexHeap = new MinIndexHeap<>(n);
for (int i = 0; i < n; i++) {
int num = ins[i].readInt();
indexHeap.insert(i, num);
}
while (indexHeap.size() > 0) {
int index = indexHeap.firstIndex();
int num = indexHeap.removeFirst();
out.write(num);
if (ins[index] == null) {
continue;
}
num = ins[index].readInt();
indexHeap.insert(index, num);
}
|
合并多路输入流时，需要操作非堆顶的元素。
如果用普通的二叉堆就不好实现了，而索引堆则正好解决这个问题。
参考
《算法（第4版）》
附录
索引堆接口
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
|
public interface IndexHeap<T> {
void insert(int index, T val);
T removeFirst();
T remove(int index);
T first();
int firstIndex();
boolean containsIndex(int index);
int size();
}
|
索引堆实现
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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
|
public class IndexHeapImpl<T extends Comparable<T>> implements IndexHeap<T> {
private final T[] elements;
private final int[] heap;
private final int[] idxMap;
private final Comparator<T> cmp;
private int size;
public IndexHeapImpl(int capacity) {
this(capacity, Comparator.reverseOrder());
}
public IndexHeapImpl(int capacity, Comparator<T> cmp) {
this.cmp = cmp;
elements = (T[]) new Comparable[capacity];
heap = new int[capacity + 1];
idxMap = new int[capacity];
Arrays.fill(heap, -1);
Arrays.fill(idxMap, -1);
}
@Override
public void insert(int idx, T val) {
if (idx < 0 || idx >= elements.length) {
throw new IllegalStateException(String.format("size: %d, index: %d", elements.length, idx));
}
if (containsIndex(idx)) {
elements[idx] = val;
int hp = idxMap[idx];
siftUp(hp);
siftDown(hp);
} else {
elements[idx] = val;
int hp = ++size;
heap[hp] = idx;
idxMap[idx] = hp;
siftUp(hp);
}
}
@Override
public T removeFirst() {
if (size <= 0) {
throw new IllegalStateException("Heap isEmpty!");
}
int hp = 1;
int idx = heap[hp];
T val = elements[idx];
swap(hp, size);
heap[size] = -1;
idxMap[idx] = -1;
elements[idx] = null;
size--;
siftDown(hp);
return val;
}
@Override
public T remove(int idx) {
if (!containsIndex(idx)) {
throw new IllegalStateException(String.format("size: %d, index: %d", elements.length, idx));
}
int hp = idxMap[idx];
T val = elements[idx];
swap(hp, size);
heap[size] = -1;
idxMap[idx] = -1;
elements[idx] = null;
size--;
if (hp <= size) {
siftUp(hp);
siftDown(hp);
}
return val;
}
@Override
public T first() {
if (size <= 0) {
throw new IllegalStateException("Heap isEmpty!");
}
return elements[heap[1]];
}
@Override
public int firstIndex() {
if (size <= 0) {
throw new IllegalStateException("Heap isEmpty!");
}
return heap[1];
}
@Override
public boolean containsIndex(int idx) {
if (idx < 0 || idx >= elements.length) {
return false;
}
return idxMap[idx] != -1;
}
@Override
public int size() {
return size;
}
private void siftDown(int hp) {
int i = hp;
while (i < size) {
int m = i;
int l = left(i);
if (l <= size && prior(l, m)) {
m = l;
}
int r = right(i);
if (r <= size && prior(r, m)) {
m = r;
}
if (m == i) {
break;
}
swap(i, m);
i = m;
}
}
private void siftUp(int hp) {
int i = hp;
while (i > 1) {
int p = parent(i);
if (p > 0 && prior(i, p)) {
swap(i, p);
i = p;
} else {
break;
}
}
}
private int parent(int hp) {
return hp / 2;
}
private int left(int hp) {
return 2 * hp;
}
private int right(int hp) {
return 2 * hp + 1;
}
private boolean prior(int hp, int hq) {
return cmp.compare(elements[heap[hp]], elements[heap[hq]]) < 0;
}
private void swap(int hp, int hq) {
if (hp == hq) {
return;
}
int t = heap[hp];
heap[hp] = heap[hq];
heap[hq] = t;
idxMap[heap[hp]] = hp;
idxMap[heap[hq]] = hq;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i = 1; i <= size; i++) {
if (i > 1) {
sb.append(", ");
}
sb.append("(")
.append(heap[i])
.append(", ")
.append(elements[heap[i]])
.append(")");
}
sb.append("]");
return sb.toString();
}
}
|