【算法日积月累】11
2025-06-02 07:50:08
索引堆是一个相对于普通堆更加高级的数据结构。
为什么要引入索引堆这个数据结构？
在一些场景下，堆这个数据结构不高效，或者说功能不够用：
1、如果元素是非常复杂的结构（例如是长字符串），交换这件事情会产生大量的性能消耗；
我们之前在堆中的操作有大量地交换操作，这种直接交换内存的操作，在元素占用内存比较小的时候，并没有多少性能的消耗，但是当须交换位置的元素占用内存很大的时候，此时交换两个元素的内存就不可以被忽视，于是，我们就想通过给堆中的每个元素映射一个标识，也就是我们这一节提到的索引。通过索引的操作来实现元素的操作。
通过索引可以找到我们真正存放在数组中的元素，而索引所代表数据构成一个最大堆。
举一个可能不是很恰当的生活中的例子，我们要给一组学生按照身高进行排序，我们不用把他们全部喊出来让他们从矮到高排好，我们只要让他们报上自己的身高，在纸上做他们身高的比较就可以了。
2、元素位置发生改变以后，很难再次索引到它，例如：我们想要将原来索引是 的元素的优先级提升或者下降一下，但是我们不知道原来索引是 的元素到底是谁了。
想一想为什么没有索引就不能支持 change，因为索引不到原来的数据，因此我就不知道要 change 哪个数据，除非遍历一遍整个数组元素。
在实际应用中，我们除了有 insert 和 extract 这两个操作以外，我们数组中的元素很可能是动态变化的，在变化的过程中，如何保持最大堆的性质，这就是我们要讨论的问题。在以后章节的学习中，我们将会看到 change 操作的实际应用。
我们不交换数据，而给每个数据一个索引，索引代表的数据是堆有序的。即：我们比较的是数据，交换的是索引。
最大索引堆
索引堆的思想类似于在医院看病使用的“叫号排队”机制，想想我们去医院挂号排队的时候：我们不用真的站在那里排成一队，每个人领一个号坐在大厅里，轮到你了，你才进去看病。
最大索引堆的内部维护了一个索引数组，这个索引数组所代表的数据构成了一个最大堆；由于索引和堆中数据存在一一对应的关系，我们通过索引可以很快地定位到数据，而索引的操作又是十分方便的。
下面以最大索引堆为例，阐述相关的技巧和思想：
最大索引堆中的 data 数组是由用户定义的，用户的 insert、extract、和 change 操作只会插入、取出和修改 data 数组中的元素，由程序员来维护内部的索引数组，索引数组堆有序。
1、比较的时候使用 data 数组进行比较，交换的时候交换的是 indexes 数组的元素；
2、比较的是 data 的数据，交换的是 indexes 的位置。
下面，我们看一个例子，我们浪费一个元素的位置。下面这张表是数组原始的样子：
0
1
2
3
4
5
6
7
8
9
10
indexes
（空着）
1
2
3
4
5
6
7
8
9
10
data
（空着）
15
17
19
13
22
16
28
30
41
62
heapify 以后，data 元素不动，将 indexes 替换成它们代表的元素的值以后，就是一个最大堆：
0
1
2
3
4
5
6
7
8
9
10
indexes
10
9
5
7
8
6
2
4
3
1
data
15
17
19
13
22
16
28
30
41
62
说明：indexes[1] = 10 ，表示 data[10] 在最大堆中的位置是 1 ，抽象成一般情况就是：indexes[x] = i ，表示 data[i] 在最大堆中的位置是 x 。紧扣索引数组是堆有序这一点就不难理解了。
索引堆-1
我们可以通过对之前最大堆的数据结构的改造，修改成一个最大索引堆。首先修改构造函数，引入索引数组。
Python 代码：
class IndexMaxHeap:
def __init__(self, capacity):
self.data = [None for _ in range(capacity + 1)]
# 初值设置为 0 ，表示该位置还没有放置元素
self.indexes = [0 for _ in range(capacity + 1)]
self.count = 0
self.capacity = capacity
其次修改 insert 方法：这里的 insert 虽然指定了索引，但是一定是在 data 数组的最后添加数据。我们插入一个元素的时候，同时要指定这个元素的索引 i ，这里要注意：传入的 i 对用户而言是从 开始的，因此在底层发生操作之前，得先加 。
Python 代码：
# 此时 insert 要给一个索引位置
def insert(self, i, item):
if self.count + 1 > self.capacity:
raise Exception('堆的容量不够了')
i += 1
self.data[i] = item
# 这一步很关键，在内部索引数组的最后设置索引数组的索引
self.indexes[self.count + 1] = i
self.count += 1
self.__shift_up(self.count)
shift_up 方法也要修改：这里就是我们上面说的那一点：比较的是 data 的数据，交换的是 indexes 的位置。
Python 代码：
def __shift_up(self, k):
# 比较的时候，上面套一层 indexes，交换的是 indexes
while k > 1 and self.data[self.indexes[k // 2]] < self.data[self.indexes[k]]:
self.indexes[k // 2], self.indexes[k] = self.indexes[k], self.indexes[k // 2]
k //= 2
然后修改 extract_max 方法：
Python 代码：
def extract_max(self):
if self.count == 0:
raise Exception('堆里没有可以取出的元素')
# 里面套一层 indexes
ret = self.data[self.indexes[1]]
# 交换的是索引
self.indexes[1], self.indexes[self.count] = self.indexes[self.count], self.indexes[1]
self.count -= 1
self.__shift_down(1)
return ret
Python 代码：
def __shift_down(self, k):
while 2 * k <= self.count:
j = 2 * k
# 比较的是 data ，交换的是 indexes
if j + 1 <= self.count and self.data[self.indexes[j + 1]] > self.data[self.indexes[j]]:
j = j + 1
if self.data[self.indexes[k]] >= self.data[self.indexes[j]]:
break
self.indexes[k], self.indexes[j] = self.indexes[j], self.indexes[k]
k = j
最后实现 change 方法：为了维持堆的性质，我们应当尝试向上挪一下 shift up，向下挪一下 shift down。关键在于找到用户认为的那个数据，在索引数组中是第几位，针对这个位置进行下沉和上移，即找到一个 j 满足：indexes[j] = i，j 表示 data[i] 在堆中的位置，之后 shift up(j)，然后 shift down(j)。还是紧扣那一点：比较的是 data ，交换的是 indexes。
Python 代码：
def change(self, i, new_item):
# 把用户视角改成内部索引
i += 1
self.data[i] = new_item
# 重点：下面这一步是找原来数组中索引是 i 的元素
# 在索引数组中的索引是几，这是一个唯一值，找到即返回
# 优化：可以引入反向查找技术优化
for j in range(1, self.count + 1):
if self.indexes[j] == i:
self.__shift_down(j)
self.__shift_up(j)
return
说明： change 这个函数是可以进行优化的，通过引入反向查找数组来进行优化。反向查找的作用，就是帮助我们寻找原来索引的位置，在最大堆中是几。这个操作也叫“反向查找”，是一个基础且常见的技巧。
索引堆的优化：反向查找
我们引入了反向查找表。这一节的内容和思想很重要，要多看。reverse[i] 表示索引 i 在 indexes（堆）中的位置。引入 reveres 数组的意义是，可以在执行 change 这个方法的时候，可以通过 时间复杂度查询到用户认为索引是 i 的元素，在索引数组组成的堆中的索引是几。
注意：为 reverse 数组赋初始值， 有特殊的含义：reverse[i] = 0 表示 data[i] 未赋值。
我们在捋一遍：引入反向查找是为了“找到 indexes 数组中原来索引是 i 的元素的位置”，即 reverse[i] = j 表示 data[i] 在索引堆中的位置是 j。
通过引入反向查找数组，实现反向查找 indexes 数组中，原来为第 i 号的那个元素排在了 indexes 数组的第几位，通过对 reverse 数组的维护，使得 change 操作时间复杂度降到了 。
reverse[i] 表示原来第 i 个数在 indexes 数组中的位置。
根据 reverse 数组反向查找的意义，我们很容易得到：如果 indexes[i] = j，那么 reveres[j] = i，可以看出来，“反向查找”有点“反函数”的意思。
把 indexes[i] = j 代入 reveres[j] = i ，得 reveres[index[i]] = i；
把 reveres[j] = i 代入 indexes[i] = j ，得 indexes[reveres[j]] = j。
这也就是“反函数的反函数是自己”。利用上述两个性质可以实现反向查找。
注意： reveres 数组的概念其实并不难理解，大家只要把 reveres 这个数组自己填一下就会非常清楚了。
0
1
2
3
4
5
6
7
8
9
10
data
15
17
19
13
22
16
28
30
41
62
indexes
10
9
5
7
8
6
2
4
3
1
reverse
10
7
9
8
3
6
4
5
2
1
说明：indexes[1] = 10，表示使用者认为的第 号数据，在 indexes 数组中的索引是 ，故 reverse[10] = 1；
indexes[2] = 9，表示使用者认为的第 号数据，在 indexes 数组中的索引是 ，故 reverse[9] = 2；
indexes[3] = 5，表示使用者认为的第 号数据，在 indexes 数组中的索引是 ，故 reverse[5] = 3；
因此，reverse 数组的作用就是：通过使用者认为的索引编号，快速找到它在 indexes 数组形成的堆中的位置。
维护reverse 数组要注意的事项：在 indexes 数组交换位置的时候，reverse 数组也要同步交换。
下面我们来分析一下 indexes 数组如果交换了位置，reverse 数组要如何交换。
假如要交换 indexes 数组 3 和 4 的位置，由于此时 indexes[3] = 7 ，indexes[4] = 5 ，为了保证 reverse 数组的正确性，（我们暂时不去看表），就应该使得 reverse[7] = 3，reverse[5] = 4。
此时再去看表， reverse[7] = 4，reverse[5] = 3。怎么交换的，就很清楚了。reverse 数组是 indexes 数组映射以后的两个值交换。
索引堆的应用
实现多路归并排序
这部分的知识我是在参考资料1（《算法》（第4版）P204）中看到的。在这里做一个笔记。索引堆只存了 3 个元素，索引堆不仅仅把我们要的那个数据拿出来了，并且还给出了这个数据在使用者眼里的索引的位置。
图论中使用索引堆找到最小生成树
本文源代码
Python：代码文件夹，Java：代码文件夹。
参考资料
1、图书《算法》(第4版)， Algorithms Fourth Edition，作者：[美] Robert Sedgewick，[美] Kevin Wayne 著，谢路云 译，图书配套网站
2、慕课网 liuyubobobo 老师《算法与数据结构》课程以及对应的 GitHub 代码仓库
3、慕课网 liuyubobobo 老师《看得见的算法》课程以及对应的 GitHub 代码仓库。
4、【多说两句】关于索引堆中的索引和数据
https://coding.imooc.com/learn/questiondetail/4945.html。
（本节完）