java – 带堆或排序算法的Kruskal

这取决于您要解决的确切问题.如果您要实现通用解决方案,只需选择“最快”的排序算法.我怀疑那是不是heapsort.我会默认使用Java正在使用的任何排序算法(如果你正在排序对象,可能是timsort).此外,在某些情况下,排序可以比O(ElogE)更快地完成.假设你的边缘只能有一个小间隔的整数权重,那么你可以选择与countort非常相似的东西.因此,如果您处于其中一种情况,那么堆可能不是一个好选择.此外,我看不出有人会单独在Kruskal算法的上下文中使用堆的任何原因.

要回答你的第二个问题(但你可能已经知道了),使用Disjoint-set data structure对集合上的操作给出了很好的加速.它具有各种优点：易于实现,良好的渐近行为和低常数.

编辑

我已经重新考虑了堆/ heapsort选项,主要是由于我的帖子上的评论.如果只排序直到树完成,使用堆可能会带来巨大的优势. 180度转向我的意见.这就是原因.

考虑Erd?s–Rényi model.现在,这是一个非常简单的模型,其中一个以n个顶点上的空图G(即没有边)开始,并且将每个可能的边以概率p添加到G,独立于任何其他边.这不完全是Kruskal算法在编写树时所做的,但如果G具有二次数的边(就顶点数而言),边缘分布不是“偏向的”和权重赋值,它就像“非常好”一样不是’有偏见’.

现在来到这里有趣的部分.在Erd?s-Rényi模型下,当p约为ln(n)/ n时(即,在向图中添加O(nln(n))边之后“粗略地说”),图形变得连通.结果众所周知(检查here).

虽然Kruskal算法的设置不同,但如果G具有二次边数(就顶点数而言),则边缘分布不是“偏向”且权重分配不是“偏差”,它是在O(nln(n))边缘内可以到达树是合理的.如果确实如此,那么在开始编写树之前,它使用堆并且仅排序直到树完成比使用比较排序方法对整个边集排序更好.

因此,使用堆可能也会使运行时速度提高,并且可能相当大.