「队列」专题 3:索引堆
索引堆是一个相对于普通堆更加高级的数据结构。
为什么要引入索引堆这个数据结构?
在一些场景下,堆这个数据结构不高效,或者说功能不够用:
1、如果元素是非常复杂的结构(例如是长字符串),交换这件事情会产生大量的性能消耗;
我们之前在堆中的操作有大量地交换操作,这种直接交换内存的操作,在元素占用内存比较小的时候,并没有多少性能的消耗,但是当须交换位置的元素占用内存很大的时候,此时交换两个元素的内存就不可以被忽视,于是,我们就想通过给堆中的每个元素映射一个标识,也就是我们这一节提到的索引。通过索引的操作来实现元素的操作。
通过索引可以找到我们真正存放在数组中的元素,而索引所代表数据构成一个最大堆。
举一个可能不是很恰当的生活中的例子,我们要给一组学生按照身高进行排序,我们不用把他们全部喊出来让他们从矮到高排好,我们只要让他们报上自己的身高,在纸上做他们身高的比较就可以了。
2、元素位置发生改变以后,很难再次索引到它,例如:我们想要将原来索引是 $6$ 的元素的优先级提升或者下降一下,但是我们不知道原来索引是 $6$ 的元素到底是谁了。
想一想为什么没有索引就不能支持 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
。紧扣索引数组是堆有序这一点就不难理解了。
我们可以通过对之前最大堆的数据结构的改造,修改成一个最大索引堆。首先修改构造函数,引入索引数组。
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
对用户而言是从 $0$ 开始的,因此在底层发生操作之前,得先加 $1$。
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
这个方法的时候,可以通过 $O(1)$ 时间复杂度查询到用户认为索引是 i
的元素,在索引数组组成的堆中的索引是几。
注意:为 reverse
数组赋初始值,$0$ 有特殊的含义:reverse[i] = 0
表示 data[i]
未赋值。
我们在捋一遍:引入反向查找是为了“找到 indexes
数组中原来索引是 i
的元素的位置”,即 reverse[i] = j
表示 data[i]
在索引堆中的位置是 j
。
通过引入反向查找数组,实现反向查找 indexes
数组中,原来为第 i
号的那个元素排在了 indexes
数组的第几位,通过对 reverse
数组的维护,使得 change
操作时间复杂度降到了 $O(1)$。
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
,表示使用者认为的第 $10$ 号数据,在 indexes
数组中的索引是 $1$,故 reverse[10] = 1
;
indexes[2] = 9
,表示使用者认为的第 $9$ 号数据,在 indexes
数组中的索引是 $2$,故 reverse[9] = 2
;
indexes[3] = 5
,表示使用者认为的第 $5$ 号数据,在 indexes
数组中的索引是 $2$,故 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 个元素,索引堆不仅仅把我们要的那个数据拿出来了,并且还给出了这个数据在使用者眼里的索引的位置。
图论中使用索引堆找到最小生成树
本文源代码
参考资料
1、图书《算法》(第4版), Algorithms Fourth Edition,作者:[美] Robert Sedgewick,[美] Kevin Wayne 著,谢路云 译,图书配套网站
2、慕课网 liuyubobobo 老师《算法与数据结构》课程以及对应的 GitHub 代码仓库
3、慕课网 liuyubobobo 老师《看得见的算法》课程以及对应的 GitHub 代码仓库。
4、【多说两句】关于索引堆中的索引和数据
https://coding.imooc.com/learn/questiondetail/4945.html。
(本节完)
索引堆是一个比较有意思的数据结构。索引技术其实还是满常见的,听起来比较高大上,其实就是做了一个对应关系。
堆排序和 Heapify
什么是基础堆排序
我们的排序工作就描述如下:把待排序数组按顺序放入一个堆(入队),全部放入以后,然后再从堆中出队,每次出队的元素就是当前数组中最大的元素,于是我们可以倒着赋值回去,直到堆中没有元素(此时原始数组也被赋值“满”了)时,就能得到一个升序的数组。
Java 代码:
全部放入优先队列,再一个一个取出,倒着放即可:
import java.util.Arrays;
public class HeapSort {
// 我们之前实现的 MaxHeap 这个数据结构,把它作为成员变量,利用它来完成排序
private MaxHeap maxHeap;
public HeapSort() {
this.maxHeap = new MaxHeap(20);
}
public HeapSort(int capacity) {
this.maxHeap = new MaxHeap(capacity);
}
// 把数组中的元素先全部挨个 insert 到最大堆中
// 然后在依次取出,因为每次取出的都是剩下的元素中的最大者
// 因此应该倒着覆盖到原待排序数组
public void sort(int[] nums) {
int[] temp = nums.clone();
for (Integer item : temp) {
maxHeap.insert(item);
}
while (maxHeap.getSize() > 0) {
nums[maxHeap.getSize() - 1] = maxHeap.extractMax();
}
}
public static void main(String[] args) {
int[] nums = {8, 1, 4, 6, 3, 2, 5, 9, 7};
HeapSort heapSort = new HeapSort(nums.length);
heapSort.sort(nums);
System.out.println(Arrays.toString(nums));
}
}
最大堆的第 3 个重要操作:heapify
什么是 heapify
在上一步“堆排序”中,我们注意到,有这样一个操作“把待排序数组按顺序放入一个堆(入队)”,这一步得一个接着一个按照顺序放入堆中,那么我们有没有一个神一样的操作,直接把一个数组丢给一个“堆”(此时还不能称为“堆”,只能说是把一个数组丢给一个堆的构造方法),让这个数组自行调整成一个最大堆,那么这个操作就叫 heapify。
因此 heapify 就是尝试将一整个数组构建成一个堆的更好的方式,因为此时无需借助额外的空间就完成了最大堆的构建,并且我们只需对数组中一半的元素执行 shift down 就可以了。
首先,我们直接把一个数组传到 MaxHeap 的构造方法里,通过从 length / 2 索引到索引 1 ,逐个执行 shift down 操作就使得了此时的数组成为了最大堆。
Java 代码:
public MaxHeap(int[] arr) {
int length = arr.length;
data = new int[length + 1];
for (int i = 0; i < length; i++) {
data[i + 1] = arr[i];
}
count = length;
// heapify:通过从 length / 2 索引到索引 1 ,逐个执行 shift down 操作就使得了此时的数组成为了最大堆
for (int i = length / 2; i >= 1; i--) {
shiftDown(i);
}
}
注意:heapify 的操作只有 shift down。
那么为什么没有 shift up 呢?我是这样认为的:shift up 是认为”上面”的元素可能不对,所以要将当前考虑的元素尝试上移。shift down 是认为”下面”的元素可能不对,所以要将当前考虑的元素直至根节点逐个尝试下移。
heapify 后挨个取出来,倒着放回待排序数组就可以了。
import java.util.Arrays;
public class HeapSort2 {
private MaxHeap maxHeap;
public HeapSort2(int[] arr) {
this.maxHeap = new MaxHeap(arr);
}
public void sort(int[] nums) {
while (maxHeap.getSize() > 0) {
nums[maxHeap.getSize() - 1] = maxHeap.extractMax();
}
}
public static void main(String[] args) {
int[] nums = {8, 1, 4, 6, 3, 2, 5, 9, 7};
HeapSort2 heapSort2 = new HeapSort2(nums);
heapSort2.sort(nums);
System.out.println(Arrays.toString(nums));
}
}
原地堆排序
原地堆排序的基本思路
注意:在这一小节中,我们要转换一下脑筋,我们要使用原地堆排序,就是不想借助额外的空间,那么拿到的数组一定 0 号位置是有数值的,所以,我们要实现的算法必须基于 0 号位置存放元素来实现。
我们在上一节也可以看到,我们将一个数组通过 heapify 即 shift down 的方式逐渐地整理成一个最大堆。
其实,原地堆排序这个想法是非常直观的,从 shift down 的操作我们就可以得到启发,堆中最大的那个元素在数组的 0 号索引位置,我们把它与此时数组中的最后一个元素交换,那么数组中最大的元素就放在了数组的末尾,此时再对数组的第一个元素执行 shift down,那么 shift down 操作都执行完以后,数组的第 1 个元素就存放了当前数组中的第 2 大的元素。
可能以上这样说,并不是很严谨,但我想思路已经说得很清楚了。
代码实现的注意事项
此时最大堆中数组的索引从 $0$ 开始计算。与之前索引从 $1$ 开始的最大堆实现比较,性质就发生了变化,但并不会不好找,我们可以自己在纸上画一个完全二叉树就可以很清晰地发现规律:${\rm parent}(i)=\cfrac{i-1}{2}$,${\rm left \quad child}(i) = 2 \times i +1$,${\rm right \quad child}(i) = 2 \times i +2$,最后一个非叶子结点的索引是:$\cfrac{count-1}{2}$;
原地堆排序,因为索引从 0 号开始,相应的一些性质在索引上都发生变化了,为此,需要重新实现一下,但并不需要重新实现 MaxHeap 里所有的方法;
注意到我们只有 shift down 的操作,对于 shift down 的实现,一些细节就要很小心,shift down 是在一个区间内进行的,这个区间的端点,应该成为我们新设计的 shift down 方法的实现。
Java 代码:
import java.util.Arrays;
public class HeapSort3 {
/**
* 原地堆排序的目标就是,不再借助 MaxHeap 这个数据结构进行排序,减少了空间复杂度
* 注意:此时我们的数组索引从 0 开始定义(自己在纸上画一下图,就能清晰地明白算法实现的含义)
*
* @param arr 待排序数组
*/
public void sort(int[] arr) {
int length = arr.length;
// 首先 heapify:将一个无序的数组组成了一个最大堆,第 1 个元素就是最大值
for (int i = (length - 1) / 2; i >= 0; i--) {
shiftDown(arr, length, i);
}
for (int i = length - 1; i > 0; i--) {
swap(arr, 0, i);
shiftDown(arr, i, 0);
}
}
// 注意 shiftDown 不能复用我们上面写的,而设计成
// 对 0 开始,end 为止,即将 arr 中 [0,end] 部分的数组元素视为"最大堆"
// 对索引为 i 的元素进行 shift down 的操作
private void shiftDown(int[] arr, int end, int i) {
// 如果有右孩子的节点,并且右孩子节点比左孩子节点的值要大
// 此时可以忽略左孩子节点的存在,拿右孩子节点的数值和自己比较
// 只要它有左孩子,就不是叶子节点,就可能 shift down,注意:这里是小于号
while (2 * i + 1 < end) {
int k = 2 * i + 1;
if (k + 1 < end && arr[k] < arr[k + 1]) {
k = k + 1;
}
if (arr[i] < arr[k]) {
swap(arr, i, k);
i = k; // 留意
} else {
break;
}
}
}
private void swap(int[] arr, int index1, int index2) {
if (index1 == index2) {
return;
}
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
public static void main(String[] args) {
int[] nums = {8, 1, 4, 6, 3, 2, 5, 9, 7};
HeapSort3 heapSort3 = new HeapSort3();
heapSort3.sort(nums);
System.out.println(Arrays.toString(nums));
}
}
索引堆
为什么要引入索引堆这个数据结构?
在堆的一些操作过程中,不论是 insert 还是 extractMax 方法,都涉及了一些元素的交换操作,交换数组中的元素的位置,在一些场景下性能消耗很大。因此,我们可以在堆的内部实现一个索引数组,通过索引可以找到我们真正存放在数组中的元素,而索引所代表数据构成一个最大堆。这就是我们要引入索引堆的原因。
我们举一个可能不是很贴切的生活中的例子,我们要给一组学生按照身高进行排序,我们不用把他们全部喊出来让他们从矮到高排好,我们只要让他们报上自己的身高,在纸上做他们身高的比较就可以了。
我还想到一点:现在我们都进入了移动支付时代,我们购买物品不需要把真真实实的钱给商家,这种操作就很像我们引入索引堆的操作,我们通过1、自己账户上的钱减少2、商家用户账上的钱增多,这种方式实现了转账,给我们的生活带来了巨大的方便。一手交钱一首交货的时代已经不存在了,我们只会看到快递小哥把货送到你家,而不会有快递小哥把你的钱寄给卖家。相信很多人像我一样,出门带的现金已经很少很少了,甚至有些时候,我们出门根本可以不带钱。
- 实现要点:
1、引入一个 indexes 数组;
2、比较的时候,使用 indexs 所对应的 data 来进行比较,交换的是 index 的位置,我们内部的实现仍然从 1 号索引开始存放数据,但这一点对外部用户来说是不可知的;
对于我们索引堆的使用者来说,他们只需要知道,这是一个数据结构,可以往里面存入数据,而每一次那出来的数据,都是当前已经存放在这个数据结构中最大的那个元素。
3、我们完全可以直接使用我们之前实现的 MaxHeap 来实现最大堆。
- 索引堆要支持的操作: 在实现的时候,要注意 insert(i,item) 的实现,不是任意位置的 i都可以 insert 的,一般有两种情况:1、insert 到使用者所认为的优先队列的尾部;2、insert 到刚刚出队的那个元素的位置,因为那个位置的数据“已经没有了”,这一点要好好体会。
shiftUp(int k) | 将位于 indexes 数组中的索引为 k 的元素逐个上移。 |
---|---|
shiftDown(int k) | 将位于 indexes 数组中的索引为 k 的元素逐个下。 |
insert(i,item) | 特别注意:这里的 i 是由使用者保证的,是业务相关的,不能完全从程序和语法的角度来判断 i 的合理性。 |
extractMax() | 将此时二叉堆中的最大的那个数据返回。 |
extractMaxIndex() | 将此时二叉堆中的最大的那个数据对应的索引返回。 |
getItem(int i) | 获得索引为 i 的数据,通常这个数据是刚刚出队的索引,是由 extractMaxIndex() 方法来的。 |
change(int i,int item) | 修改索引为 i 的数据的“优先级”。 |
【多说两句】关于索引堆中的索引和数据
https://coding.imooc.com/learn/questiondetail/4945.html
索引堆的优化
索引堆的优化方法
我们想找一找在使用者认为的优先队列中指定索引的数据,在我们的 indexes 数组中,排在第几位,我们使用了遍历,这种做法效率是不高的。
Java 代码:
for (int j = 1; j <= count; j++) {
if (indexes[j] == i) {
// 找到了 j
shiftDown(j);
shiftUp(j);
return;
}
}
我们可以通过引入一个反向查找数组,实现反向查找 indexes 数组中,值为 i 的那个元素排在了 indexes 的第几位,通过对 reverse 数组的维护,就使得我们对反向查找这件事情的时间复杂度降到了 $O(1)$。
reverse[i]
表示索引 i 在 indexes(堆)中的位置。引入 reveres 数组的意义是,可以在执行 change 这个方法的时候,使用O(1)
这个时间复杂度,直接找到。- reverse 数组的性质:
性质1:如果 indexes[i] = j
,那么 reveres[j] = i
;
性质2:indexes[reveres[i]] = i
,reveres[index[i]] = i
。
- 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,表示使用者认为的第 10 号数据,排在了优先队列的第 1 位,即 10 这个数字在 indexes 数组中的索引是 1,故 revers[10] = 1;
indexes[2] = 9,表示使用者认为的第 9 号数据,排在了优先队列的第 9 位,即 9 这个数字在 indexes 数组中的索引是 2,故 revers[9] = 2;
indexes[5] = 8,表示使用者认为的第 8 号数据,排在了优先队列的第 5 位,即 8 这个数字在 indexes 数组中的索引是 5,故 revers[8] = 5;
所以,revers 数组的作用就是:通过使用者认为的索引数据,它在 indexes 数组形成的堆中的位置。
- reverse 数组在 indexes 数组交换位置的时候,应该如何维护
下面我们来分析一下 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 个元素,索引堆不仅仅把我们要的那个数据拿出来了,并且还给出了这个数据在使用者眼里的索引的位置。
- 图论中使用索引堆找到最小生成树
参考资料
图书《算法》(第4版), Algorithms Fourth Edition,作者:[美] Robert Sedgewick,[美] Kevin Wayne 著,谢路云 译,图书配套网站