索引堆的插入问题、、
来源：4-8 索引堆(Index Heap)
易萧
2017-06-21
今天自己写索引堆的时候突然发现我在构造函数里的写法是这样的：
for(i=1;i<=capacity;i++) index[i]=i;
然后再insert里面写的：
void insert(int i, Item item)
{
data[index[i+1]] = item;
count++;
shiftUp( i+1 );
}后来索引堆的排序出问题了，很是茫然。回过来看视频，我不知道是不是插入操作导致的，但对于这个视频的代码仍然有问题想不通。用户指定的索引 i 不是一个抽象的数组么，怎么会直接添加到data数组中呢，不是应该通过index[i]来放入么。
1回答
-
用户指定的索引i是添加到indexes数组中的，而不是添加到data数组中的。item才是添加到data数组中的。
当我们使用索引堆的时候，indexes初始是没有值的，表示索引堆为空。如果愿意，初始化时应该附上一个非法值，比如0（索引从1开始计算，0为非法。）在维护堆的性质的时候，我们只改变indexes数组，而不动data。data只用来获取具体的数字，但是不进行重新的排列整理。比如，在最大索引堆中，indexes[0]中存放的是最大元素的索引；而这个最大元素的值是data[indexes[0]]
索引堆确实比较绕，属于高级数据结构，在一般的初等数据结构教材中都不会介绍。在这里做介绍，完全是因为后续的prim算法和dijkstra算法需要索引堆进行优化（在一般初等数据结构教材中，对着两个算法也不会优化）。建议：
1）使用官方程序，和一个随机生成的小样例，比如7个数据，一个一个插入索引堆，再一个一个取出索引堆，跟踪程序，观察每一步indexes数组和data数组是怎么改变的，如何维护的索引堆的性质。
2）结合课程后续的prim算法，和dijkstra算法，使用一个小测试用例，观察索引堆是如何在这两个算法中作用的，进一步理解索引堆。
个人认为透彻理解索引堆还是很有意义的，因为很多算法的优化本质就是使用索引。索引堆就是在堆中使用索引。类似的思路，可以是，比如在排序中使用索引。不去真正交换数组中的元素，而只去交换数组的索引。等等等等。
加油！
132017-06-22
相似问题