--------------------siwuxie095
索引堆
这里介绍一个比普通堆更加高级的数据结构：索引堆（Index Heap）
首先来看一下普通堆有什么问题 或 缺点：
将一个数组通过 Heapify 构建成一个堆，对于这个数组而言，
在堆构建前和堆构建后，它的元素位置发生了改变，正是因为
元素位置的改变，才使得它被看做是一个堆
但在构建堆的过程中，改变元素的位置将会有一些局限性：
（1）如果元素是非常复杂的结构，如：元素是字符串，那么交换这些元素
本身，消耗就是巨大的
比如说：如果每一个元素都是一篇有十万字的文章，那么对于这些巨型的字
符串，让它们来回交换会产生大量的性能上的消耗
不过这种性能上的消耗，还可以使用技术手段来解决，另一个问题可能相对
就更加致命
（2）由于元素在数组中的位置发生了改变，使得堆建成以后很难索引到它，
当难以索引到元素时，就很难去改变它
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
- |
15 |
17 |
19 |
13 |
22 |
16 |
28 |
30 |
41 |
62 |
比如说：这个数组里的元素表示一个一个的系统任务，可能在初始的
时候，索引表示进程的 ID 号（从 1 开始），元素表示的是优先级
（每一个进程都表示一个系统任务）
可是当把这个表示系统任务的数组构建成堆之后，这些元素的索引和
系统任务之间就不再产生关联了
如果现在想提升原来进程的 ID 号为 6 的那个系统任务的优先级，应
该怎么做？
这个操作就变的非常难，在以前的数组中，可以用 O(1) 的性能效率
直接将这个任务提取出来，但当把它组建成堆以后，元素的位置发生
了改变，索引不到了
有人可能会说，在这个元素里再添加一个属性，来表示 ID 号就好了
这样的确可以解决，但要将整个数组遍历一遍，才能够找到相应的进
程，这个性能也是低效的
为此，就需要引入索引堆来解决这个问题
什么是索引堆？
其实非常简单，对于索引堆来说：
数据 data 和索引 index 这两部分内容分开存储，而真正表征
堆的数组是由索引 index 构建成的
以最大索引堆为例（索引从 1 开始）：
数组在初始情况下：
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
index |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
data |
15 |
17 |
19 |
13 |
22 |
16 |
28 |
30 |
41 |
62 |
当将数组构建成堆以后：
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
index |
10 |
9 |
5 |
7 |
8 |
6 |
2 |
4 |
3 |
1 |
|
data |
15 |
17 |
19 |
13 |
22 |
16 |
28 |
30 |
41 |
62 |
对于 data 域来说，它们没有发生任何改变，真正改变的是 index 域，
这个 index 数组发生了改变，形成了一个堆
这个堆怎么解读呢？堆顶的元素为 10，实际指向的是 10 这个 index
所指向的 data，也就是 62，相应的堆顶元素有左孩子和右孩子，左
孩子的元素为 9，实际指向的是 41，右孩子的元素是 7，实际指向的
是 28 … 依此类推
这样一来，可以观察到索引堆的两个好处：
（1）构建堆的过程只是索引 index 的位置发生交换
索引 index 就是一个简单的 int 型，如果数据 data 是非常复杂的结构，
只交换 int 型的索引 index，交换效率非常高
（2）如果现在想对堆中的数据进行一个操作，如：修改 index 为 7 的
data，也就是 28，修改完后，相应的还要做一些维护的操作来维持堆
的性质，那么维持堆的性质只是根据新的 data 数组来改变 index 数组
即可
简而言之：索引堆比较的是 data，交换的是 index
索引堆的优化
在修改数据 data 时是从外部传入进来一个索引来修改 data 数组，
而在维护索引堆的过程中，要先用 O(n) 的时间来遍历 index 数组
找到传入进来的索引的位置
如果要修改 n 个 data，算法的时间复杂度就是 O(n^2) 级别的
所以可以通过 反向查找 的方式来进行优化，在查找时就可以直接
用 O(1) 的时间找到传入进来的索引在 index 数组中的位置
如果要修改 n 个 data，算法的时间复杂度就是 O(n*lgn) 级别的
以最大索引堆为例（索引从 1 开始）：
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
index |
10 |
9 |
5 |
7 |
8 |
6 |
2 |
4 |
3 |
1 |
|
data |
15 |
17 |
19 |
13 |
22 |
16 |
28 |
30 |
41 |
62 |
|
reverse |
10 |
7 |
9 |
8 |
3 |
6 |
4 |
5 |
2 |
1 |
其中：reverse[i] 表示 index 为 i 的值在堆中的位置
另，有公式如下：
（1）index[i]=j
（2）reverse[j]=i
（3）index[reverse[i]]=i
（4）reverse[index[i]]=i
【made by siwuxie095】