algorithm - 带 Treap 的 Prim 算法

Question

Prim 的算法是否可以通过 treaps 来实现以加快执行速度，因为正常的堆会在更新键的值时产生问题，同时将顶点存储在堆中，否则需要 O(V) 空间来存储堆中顶点的位置？

Answer 1

这不一定会使 Prim 的算法更快。考虑以下退化情况 - 您有 n 个节点 v1、v2、...、vn，它们的优先级为 p(v1) < p(v2) < p(v3) < ... < p(vn)。在这种情况下，treap 将是一个退化的链表，如果您需要在此过程中更新优先级，只需查找树中的节点可能需要时间 Ω(n)。带有额外查找表的标准二进制堆会比这更快。

抱歉，结果为阴性，但我希望这会有所帮助！