2回答

liuyubobobo

2021-05-10

已采纳

“为啥你用从数组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

仅供参考。

继续加油！：）

1

2

liuyubobobo

回复

我会回来的333

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

2021-05-11

共2条回复

我会回来的333

提问者

2021-05-11

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

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

0

1

liuyubobobo

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

2021-05-11

共1条回复