algorithm - 哪种实现最适合 Prim 的算法，使用 Set 还是 Priority Queue？为什么？

Question

我知道这两种数据结构的实现，我想知道考虑时间复杂度哪个更好。

Answer 1

两者具有相同的插入和删除复杂度 O(log n)，而 get min 对于两者都是 O(1)。

优先级队列只允许您按排序顺序访问一个元素，即，您可以获得最高/最低优先级的项目，当您删除它时，您可以获得下一个，依此类推。集合允许您按排序顺序进行完全访问，例如，在集合中间某处找到两个元素，然后按顺序从一个元素遍历到另一个元素。

在优先级队列中，您可以拥有多个具有相同优先级值的元素，而在集合中则不能。

Set一般由二叉树支持，而优先级队列是堆。

那么问题是什么时候应该使用二叉树而不是堆？

在我看来，你不应该使用它们。检查二项式和斐波那契堆。对于质数算法，它们将具有更好的性能。

如果您坚持使用其中之一，我会选择优先队列，因为它占用的内存更小，并且可以有多个具有相同优先级值的元素。