索引堆的插入问题、、

Question

今天自己写索引堆的时候突然发现我在构造函数里的写法是这样的：

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]来放入么。

Answer 1

liuyubobobo 2017-06-22 02:32:41

用户指定的索引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算法，使用一个小测试用例，观察索引堆是如何在这两个算法中作用的，进一步理解索引堆。

个人认为透彻理解索引堆还是很有意义的，因为很多算法的优化本质就是使用索引。索引堆就是在堆中使用索引。类似的思路，可以是，比如在排序中使用索引。不去真正交换数组中的元素，而只去交换数组的索引。等等等等。

加油！

• 提问者 易萧 #1

  我跟踪了添加元素的全过程，初始的时候因为堆是空的，所以一开始顺序添加元素，我之前的那种方式好像也是构成了最小堆，毕竟shiftUp没有写错。我之前一直以为任何对于data数组的操作都是需要先透过index来找到应该操作data中的哪一个位置的，而维护的时候只是不去修改data数组。
  所以说我是应该这样理解吗：用户认为的数组就是data数组，而index数组是内部维护时的数组吧，用户指定的操作都是在data上的，通过内部函数获取的元素信息都是通过index索引到的。

• liuyubobobo 回复 提问者 易萧 #2

  之前你提的一个问题我已经提到了。在索引堆中，索引和数据都应该是用户认知的内容。"用户指定的操作都是在data上的" 在这里"用户指定的操作"你具体是指什么操作？事实上，通过代码可以看到，用户指定的操作，比如插入一个新元素，或者extract出新元素，indexes和data两个数组都是变化的。"通过内部函数获取的元素信息都是通过index索引到的"，但其实我们可以看到，我们的索引堆中也有Item getItem( int i )这个方法，用户可以直接通过索引i获取数据。这和之前的第一点是对应的：在索引堆中，索引和数据都应该是用户认知的内容。

• 提问者 易萧 #3

  非常感谢！