索引堆是一个相对于普通堆更加高级的数据结构。

为什么要引入索引堆这个数据结构？

在一些场景下，堆这个数据结构不高效，或者说功能不够用：

1、如果元素是非常复杂的结构（例如是长字符串），交换这件事情会产生大量的性能消耗；

我们之前在堆中的操作有大量地交换操作，这种直接交换内存的操作，在元素占用内存比较小的时候，并没有多少性能的消耗，但是当须交换位置的元素占用内存很大的时候，此时交换两个元素的内存就不可以被忽视，于是，我们就想通过给堆中的每个元素映射一个标识，也就是我们这一节提到的索引。通过索引的操作来实现元素的操作。

通过索引可以找到我们真正存放在数组中的元素，而索引所代表数据构成一个最大堆。

举一个可能不是很恰当的生活中的例子，我们要给一组学生按照身高进行排序，我们不用把他们全部喊出来让他们从矮到高排好，我们只要让他们报上自己的身高，在纸上做他们身高的比较就可以了。

2、元素位置发生改变以后，很难再次索引到它，例如：我们想要将原来索引是 的元素的优先级提升或者下降一下，但是我们不知道原来索引是 的元素到底是谁了。

想一想为什么没有索引就不能支持 change，因为索引不到原来的数据，因此我就不知道要 change 哪个数据，除非遍历一遍整个数组元素。

在实际应用中，我们除了有 insert 和 extract 这两个操作以外，我们数组中的元素很可能是动态变化的，在变化的过程中，如何保持最大堆的性质，这就是我们要讨论的问题。在以后章节的学习中，我们将会看到 change 操作的实际应用。

我们不交换数据，而给每个数据一个索引，索引代表的数据是堆有序的。即：我们比较的是数据，交换的是索引。

最大索引堆

索引堆的思想类似于在医院看病使用的“叫号排队”机制，想想我们去医院挂号排队的时候：我们不用真的站在那里排成一队，每个人领一个号坐在大厅里，轮到你了，你才进去看病。

最大索引堆的内部维护了一个索引数组，这个索引数组所代表的数据构成了一个最大堆；由于索引和堆中数据存在一一对应的关系，我们通过索引可以很快地定位到数据，而索引的操作又是十分方便的。

下面以最大索引堆为例，阐述相关的技巧和思想：

最大索引堆中的 data 数组是由用户定义的，用户的 insert、extract、和 change 操作只会插入、取出和修改 data 数组中的元素，由程序员来维护内部的索引数组，索引数组堆有序。

1、比较的时候使用 data 数组进行比较，交换的时候交换的是 indexes 数组的元素；

2、比较的是 data 的数据，交换的是 indexes 的位置。

下面，我们看一个例子，我们浪费一个元素的位置。下面这张表是数组原始的样子：

heapify 以后，data 元素不动，将 indexes 替换成它们代表的元素的值以后，就是一个最大堆：

说明：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 这个数组自己填一下就会非常清楚了。

说明：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。

（本节完）