关于prim算法最小索引堆的问题

来源：8-4 Prim算法的优化

HERTION

2019-10-13

老师，我个人感觉使用最小索引堆来存储最短路径权值，好像没有体现出最小索引堆的特点。是否就可以使用一个普通的数组来代替，数组的索引就是节点的编号，对应的内容就是当前求出的最小权值。

写回答

2回答

liuyubobobo

2019-10-13

已采纳

使用最小索引堆的原因是：

1）快速取出最小值

2）快速更新

如果只使用数组，无法做到快速得到最小值。自己使用数组的方式编代码试试看？

继续加油！：）

Cooper_s_code

2020-12-05

我理解老师的意思是，数组的下标是相应的代表节点，这样通过最小索引堆就可以找出最小边，每次有比当前边小的更新时要进行一次shift up。索引堆相当于一个找小边的查找器，数据存储还是用一个数组来存储，你可能只看到数组没有看到索引数组，老师也没有展示索引的维护过程，其实索引数组一直在变化。

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 2