优化prim算法中索引堆的意义？

来源：

马尔克ov

2017-06-07

我的理解是索引堆的意义应该是用人为规定的空间位置规则来维护元素的顺序，方便我们找一个元素的时候不用全扫描。然而在这个算法中我看到只是直接访问堆中的第几个位置，存一个数或者改一个数。这样的话没发现和普通的数组有什么区别？

写回答

1回答

liuyubobobo

2017-06-07

已采纳

首先，你的理解是对的。我们使用索引堆就是为了能够在找一群元素的最小值（或者最大值）时，不用去扫描所有的元素。而在我们的Prim算法的主循环中，每次第一件做的事情，就是拿出当前堆中的权值最小的那条边所对应的节点啊！

int v = ipq.extractMinIndex();

与此同时，我们在后续的计算中，还要针对这个新的节点，去更新数据，就是你所说的存储或者更改新的数据。这部分逻辑都被封装在了课程代码中的visit函数中。

在课程代码中，我们的Prim算法的主体循环就可以表征成是这个样子：

// Prim
while( !ipq.isEmpty() ){
    int v = ipq.extractMinIndex();   // 从最小索引堆中获取最小元素
    ...
    visit( v );    // 根据获取的最小元素更新最小索引堆中的其他元素 
}

看，在这个算法中，我们既要快速获取所有元素的最小值；又要快速插入新的元素，或者更新已有的元素。所以索引堆就是最合适的数据结构啦。

在这个工程的main函数中，我也实际比较了使用索引堆做优化和不使用索引堆，即Lazy Prim之间的性能差异。强烈建议亲自实验一下哦：）

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

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

11187 学习 · 1614 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 2