索引堆是一個相對于普通堆更加高級的數(shù)據(jù)結(jié)構(gòu)。

為什么要引入索引堆這個數(shù)據(jù)結(jié)構(gòu)渠脉？

在一些場景下寻拂，堆這個數(shù)據(jù)結(jié)構(gòu)不高效，或者說功能不夠用：

1逢艘、如果元素是非常復(fù)雜的結(jié)構(gòu)（例如是長字符串）旦袋，交換這件事情會產(chǎn)生大量的性能消耗；

我們之前在堆中的操作有大量地交換操作它改，這種直接交換內(nèi)存的操作疤孕，在元素占用內(nèi)存比較小的時候，并沒有多少性能的消耗央拖，但是當(dāng)須交換位置的元素占用內(nèi)存很大的時候祭阀，此時交換兩個元素的內(nèi)存就不可以被忽視鹉戚，于是，我們就想通過給堆中的每個元素映射一個標(biāo)識专控，也就是我們這一節(jié)提到的索引抹凳。通過索引的操作來實現(xiàn)元素的操作。

通過索引可以找到我們真正存放在數(shù)組中的元素伦腐，而索引所代表數(shù)據(jù)構(gòu)成一個最大堆赢底。

舉一個可能不是很恰當(dāng)?shù)纳钪械睦樱覀円o一組學(xué)生按照身高進行排序柏蘑，我們不用把他們?nèi)亢俺鰜碜屗麄儚陌礁吲藕眯叶常覀冎灰屗麄儓笊献约旱纳砀撸诩埳献鏊麄兩砀叩谋容^就可以了咳焚。

2洽损、元素位置發(fā)生改變以后，很難再次索引到它革半，例如：我們想要將原來索引是 的元素的優(yōu)先級提升或者下降一下碑定，但是我們不知道原來索引是 的元素到底是誰了。

想一想為什么沒有索引就不能支持 change督惰，因為索引不到原來的數(shù)據(jù)不傅，因此我就不知道要 change 哪個數(shù)據(jù)，除非遍歷一遍整個數(shù)組元素赏胚。

在實際應(yīng)用中访娶，我們除了有 insert 和 extract 這兩個操作以外，我們數(shù)組中的元素很可能是動態(tài)變化的觉阅，在變化的過程中崖疤，如何保持最大堆的性質(zhì)，這就是我們要討論的問題典勇。在以后章節(jié)的學(xué)習(xí)中劫哼，我們將會看到 change 操作的實際應(yīng)用。

我們不交換數(shù)據(jù)割笙，而給每個數(shù)據(jù)一個索引权烧，索引代表的數(shù)據(jù)是堆有序的。即：我們比較的是數(shù)據(jù)伤溉，交換的是索引般码。

最大索引堆

索引堆的思想類似于在醫(yī)院看病使用的“叫號排隊”機制，想想我們?nèi)メt(yī)院掛號排隊的時候：我們不用真的站在那里排成一隊乱顾，每個人領(lǐng)一個號坐在大廳里板祝，輪到你了，你才進去看病走净。

最大索引堆的內(nèi)部維護了一個索引數(shù)組券时，這個索引數(shù)組所代表的數(shù)據(jù)構(gòu)成了一個最大堆孤里；由于索引和堆中數(shù)據(jù)存在一一對應(yīng)的關(guān)系，我們通過索引可以很快地定位到數(shù)據(jù)橘洞，而索引的操作又是十分方便的捌袜。

下面以最大索引堆為例，闡述相關(guān)的技巧和思想：

最大索引堆中的 data 數(shù)組是由用戶定義的震檩，用戶的 insert琢蛤、extract、和 change 操作只會插入抛虏、取出和修改 data 數(shù)組中的元素博其，由程序員來維護內(nèi)部的索引數(shù)組，索引數(shù)組堆有序迂猴。

1慕淡、比較的時候使用 data 數(shù)組進行比較，交換的時候交換的是 indexes 數(shù)組的元素沸毁；

2峰髓、比較的是 data 的數(shù)據(jù)，交換的是 indexes 的位置息尺。

下面携兵，我們看一個例子，我們浪費一個元素的位置搂誉。下面這張表是數(shù)組原始的樣子：

heapify 以后徐紧，data 元素不動，將 indexes 替換成它們代表的元素的值以后炭懊，就是一個最大堆：

說明：indexes[1] = 10 并级，表示 data[10] 在最大堆中的位置是 1 ，抽象成一般情況就是：indexes[x] = i 侮腹，表示 data[i] 在最大堆中的位置是 x 嘲碧。緊扣索引數(shù)組是堆有序這一點就不難理解了。

索引堆-1

我們可以通過對之前最大堆的數(shù)據(jù)結(jié)構(gòu)的改造父阻，修改成一個最大索引堆愈涩。首先修改構(gòu)造函數(shù)，引入索引數(shù)組加矛。

Python 代碼：

class IndexMaxHeap:
    def __init__(self, capacity):
        self.data = [None for _ in range(capacity + 1)]
        # 初值設(shè)置為 0 钠署，表示該位置還沒有放置元素
        self.indexes = [0 for _ in range(capacity + 1)]
        self.count = 0
        self.capacity = capacity

其次修改 insert 方法：這里的 insert 雖然指定了索引，但是一定是在 data 數(shù)組的最后添加數(shù)據(jù)荒椭。我們插入一個元素的時候，同時要指定這個元素的索引 i 舰蟆，這里要注意：傳入的 i 對用戶而言是從 開始的趣惠，因此在底層發(fā)生操作之前狸棍，得先加 。

Python 代碼：

# 此時 insert 要給一個索引位置
def insert(self, i, item):
    if self.count + 1 > self.capacity:
        raise Exception('堆的容量不夠了')
        i += 1
        self.data[i] = item
        # 這一步很關(guān)鍵味悄，在內(nèi)部索引數(shù)組的最后設(shè)置索引數(shù)組的索引
        self.indexes[self.count + 1] = i
        self.count += 1
        self.__shift_up(self.count)

shift_up 方法也要修改：這里就是我們上面說的那一點：比較的是 data 的數(shù)據(jù)草戈，交換的是 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

最后實現(xiàn) change 方法：為了維持堆的性質(zhì)涨颜，我們應(yīng)當(dāng)嘗試向上挪一下 shift up费韭，向下挪一下 shift down。關(guān)鍵在于找到用戶認(rèn)為的那個數(shù)據(jù)庭瑰，在索引數(shù)組中是第幾位星持，針對這個位置進行下沉和上移，即找到一個 j 滿足：indexes[j] = i弹灭，j 表示 data[i] 在堆中的位置督暂，之后 shift up(j)，然后 shift down(j)穷吮。還是緊扣那一點：比較的是 data 逻翁，交換的是 indexes。

Python 代碼：

def change(self, i, new_item):
    # 把用戶視角改成內(nèi)部索引
    i += 1
    self.data[i] = new_item

    # 重點：下面這一步是找原來數(shù)組中索引是 i 的元素
    # 在索引數(shù)組中的索引是幾捡鱼，這是一個唯一值八回，找到即返回
    # 優(yōu)化：可以引入反向查找技術(shù)優(yōu)化
    for j in range(1, self.count + 1):
        if self.indexes[j] == i:
            self.__shift_down(j)
            self.__shift_up(j)
            return

說明： change 這個函數(shù)是可以進行優(yōu)化的，通過引入反向查找數(shù)組來進行優(yōu)化堰汉。反向查找的作用辽社，就是幫助我們尋找原來索引的位置，在最大堆中是幾翘鸭。這個操作也叫“反向查找”滴铅，是一個基礎(chǔ)且常見的技巧。

索引堆的優(yōu)化：反向查找

我們引入了反向查找表就乓。這一節(jié)的內(nèi)容和思想很重要汉匙，要多看。reverse[i] 表示索引 i 在 indexes（堆）中的位置生蚁。引入 reveres 數(shù)組的意義是噩翠，可以在執(zhí)行 change 這個方法的時候，可以通過 時間復(fù)雜度查詢到用戶認(rèn)為索引是 i 的元素邦投，在索引數(shù)組組成的堆中的索引是幾伤锚。

注意：為 reverse 數(shù)組賦初始值， 有特殊的含義：reverse[i] = 0 表示 data[i] 未賦值志衣。

我們在捋一遍：引入反向查找是為了“找到 indexes 數(shù)組中原來索引是 i 的元素的位置”屯援，即 reverse[i] = j 表示 data[i] 在索引堆中的位置是 j猛们。

通過引入反向查找數(shù)組，實現(xiàn)反向查找 indexes 數(shù)組中狞洋，原來為第 i 號的那個元素排在了 indexes 數(shù)組的第幾位弯淘，通過對 reverse 數(shù)組的維護，使得 change 操作時間復(fù)雜度降到了 吉懊。

reverse[i] 表示原來第 i 個數(shù)在 indexes 數(shù)組中的位置庐橙。

根據(jù) reverse 數(shù)組反向查找的意義，我們很容易得到：如果 indexes[i] = j借嗽，那么 reveres[j] = i态鳖，可以看出來，“反向查找”有點“反函數(shù)”的意思淹魄。

把 indexes[i] = j 代入 reveres[j] = i 郁惜，得 reveres[index[i]] = i；

把 reveres[j] = i 代入 indexes[i] = j 甲锡，得 indexes[reveres[j]] = j兆蕉。

這也就是“反函數(shù)的反函數(shù)是自己”。利用上述兩個性質(zhì)可以實現(xiàn)反向查找缤沦。

注意： reveres 數(shù)組的概念其實并不難理解虎韵，大家只要把 reveres 這個數(shù)組自己填一下就會非常清楚了。

說明：indexes[1] = 10缸废，表示使用者認(rèn)為的第 號數(shù)據(jù)包蓝，在 indexes 數(shù)組中的索引是 ，故 reverse[10] = 1企量；

indexes[2] = 9测萎，表示使用者認(rèn)為的第 號數(shù)據(jù)，在 indexes 數(shù)組中的索引是 届巩，故 reverse[9] = 2硅瞧；

indexes[3] = 5，表示使用者認(rèn)為的第 號數(shù)據(jù)恕汇，在 indexes 數(shù)組中的索引是 腕唧，故 reverse[5] = 3；

因此瘾英，reverse 數(shù)組的作用就是：通過使用者認(rèn)為的索引編號枣接，快速找到它在 indexes 數(shù)組形成的堆中的位置。

維護reverse 數(shù)組要注意的事項：在 indexes 數(shù)組交換位置的時候缺谴，reverse 數(shù)組也要同步交換但惶。

下面我們來分析一下 indexes 數(shù)組如果交換了位置，reverse 數(shù)組要如何交換。

假如要交換 indexes 數(shù)組 3 和 4 的位置榆骚，由于此時 indexes[3] = 7 片拍，indexes[4] = 5 ，為了保證 reverse 數(shù)組的正確性妓肢，（我們暫時不去看表），就應(yīng)該使得 reverse[7] = 3苫纤，reverse[5] = 4碉钠。

此時再去看表， reverse[7] = 4卷拘，reverse[5] = 3喊废。怎么交換的，就很清楚了栗弟。reverse 數(shù)組是 indexes 數(shù)組映射以后的兩個值交換污筷。

索引堆的應(yīng)用

實現(xiàn)多路歸并排序

這部分的知識我是在參考資料1（《算法》（第4版）P204）中看到的。在這里做一個筆記乍赫。索引堆只存了 3 個元素瓣蛀，索引堆不僅僅把我們要的那個數(shù)據(jù)拿出來了，并且還給出了這個數(shù)據(jù)在使用者眼里的索引的位置雷厂。

圖論中使用索引堆找到最小生成樹

本文源代碼

Python：代碼文件夾惋增，Java：代碼文件夾。

參考資料

1改鲫、圖書《算法》(第4版)诈皿， Algorithms Fourth Edition，作者：[美] Robert Sedgewick像棘，[美] Kevin Wayne 著稽亏，謝路云 譯，圖書配套網(wǎng)站

2、慕課網(wǎng) liuyubobobo 老師《算法與數(shù)據(jù)結(jié)構(gòu)》課程以及對應(yīng)的 GitHub 代碼倉庫

3、慕課網(wǎng) liuyubobobo 老師《看得見的算法》課程以及對應(yīng)的 GitHub 代碼倉庫葫盼。

4址貌、【多說兩句】關(guān)于索引堆中的索引和數(shù)據(jù)

https://coding.imooc.com/learn/questiondetail/4945.html。

（本節(jié)完）