老师,最大索引堆听不懂,听了1天,也没听懂怎么办?

Question

老师我不知道为啥你用从数组1索引开始存堆内数据,这种堆做例子进行改进成为索引堆,这样不就没办法用之前从0索引开始存堆内数据直接在原数组中进行排序的优化了吗?
这是我对索引堆理解画的草图,索引堆就是实现用data中的堆内数据做比较,用index中存的data数组的索引值进行交换,其实data堆并没有动,动的只是index存的data的索引,这样就可以实现知道排好序的元素对应的原来data的索引,我怎么感觉这是个假的堆排序呢,而且代码有点太难了,局部变量太多,各种+1或-1,整不明白了,咋办老师

Answer 1

liuyubobobo 2021-05-10 17:06:17

“为啥你用从数组1索引开始存堆内数据,”

完全是因为每个元素的左孩子是 2* i，右孩子是 2 * i + 1，方便而已。如果你喜欢从 0 开始，是完全没问题的，只不过左孩子是 2 * i + 1，右孩子是 2 * i + 2

“用index中存的data数组的索引值进行交换,其实data堆并没有动,动的只是index存的data的索引”

完全正确！

“我怎么感觉这是个假的堆排序呢,而且代码有点太难了”

索引堆的关键不是做堆排序。而是制造了一个堆。但是普通的堆除了堆顶的元素，其他元素访问不了，也修改不了。但索引堆能通过索引任意修改堆中的元素，进而维护堆的性质。

==========

整体而言，索引堆做的事情，就是维持 data[index[i]] 是一个堆（对比普通的堆只是 data[i] 维持了一个堆。）

如果你实在听不懂，可以先简单理解一下索引堆的各个接口返回的是什么，对数据做了怎样的操作，而不用管内部实现。课程后续介绍 prim 算法和 Dijkstra 算法的时候，会具体使用索引堆，届时，可以再理解清楚这两个算法是如何使用索引堆的基础上，回来看能不能理解索引堆内部的实现。

另外，这个课程在这里的介绍，确实比较进阶。因为这个课程最初的定位相对比较进阶。prim 算法和 dijkstra 算法有不使用索引堆的实现方式。复杂度稍微低一些，但是完全在可以承受的范围里。如果对从感兴趣，我的图论算法课程介绍的更充分：https://coding.imooc.com/class/370.html

整体，现在我比较推荐大家学习我的这个课程（真的不是因为贵。。。而是因为介绍的角度更基础，且更全面。。。）：https://class.imooc.com/sale/datastructure

在这个课程的基础上，如果想系统学图论算法，可以看这个课程：https://coding.imooc.com/class/370.html

仅供参考。

继续加油！：）

• 提问者 我会回来的333 #1

  老师还有个问题assert这个东西我还真不知道怎么用?我接触Java半年了从没用过,

• liuyubobobo 回复 提问者 我会回来的333 #2

  assert(x) 相当于 if(!x) 则程序报错中断。

Answer 2

提问者 我会回来的333 2021-05-11 02:03:48

谢谢老师回答我的问题,我也就是画红圈这几点不太理解,也就是您加的这几个特殊操作里面的细节,我左想右想没想出来,我还会继续想,我肯定还是没理解透彻,这次您一个视频讲了很多方法,这个索引堆好像又不是给数组排序用的,然后我不知道怎么测试,我也很难弄清楚我到底哪里不理解,我好像都不知道这个索引堆是干嘛用的,就稀里糊涂学了一边,很奇怪

本来我一开始就是想买那个体系课的,如果那个课666我没准就买了,无奈,无奈,所以我就买了您的这两门便宜的课程,只能走难走的路,不过这对我来说是挑战也是锻炼,实话说我一点不会C++,哈哈,继续加油吧 : )再次谢谢老师

• liuyubobobo #1

  i = index[1] - 1，就是因为 index 中存的索引是从 1 开始的，而对与外界用户来说，存的索引是从 0 开始的。所以减去1，让外界用户获得从 0 开始的索引。注意，最后是 return i；下面 change 的逻辑是，在修改完索引 i 所对应的元素以后，整个堆可能不在是堆了，所以要找到索引 i 在堆中的位置，然后用 shiftUp 和 shiftDown 维护一下堆的性质。