PriorityQueue与Collections.sort

Question

当我会永远选Collections.sort()过PriorityQueue，当我知道PQ的会在时间复杂性方面会更好？

Answer 1

有效地轮询a PriorityQueue的所有元素heap sorting。Collections.sort()使用实现merge sorting。就时间复杂度而言，堆排序和合并排序是可比较的。两者都具有最佳情况，最坏情况和平均情况O（n log n）的时间复杂度。

在性能方面，这是维基百科要说的：

Heapsort还与合并排序竞争，后者具有相同的时间范围。合并排序需要？（n）个辅助空间，而堆排序仅需要一个常数。实际上，Heapsort通常在数据缓存较小或较慢的计算机上运行得更快。另一方面，合并排序相对于堆排序具有几个优点：

• 阵列上的合并排序具有更好的数据缓存性能，通常在现代台式机上的表现优于堆排序，因为合并排序经常访问连续的内存位置（良好的引用位置）；heapsort引用分布在整个堆中。
• 堆排序不是稳定的排序；合并排序是稳定的。
• 合并排序可以很好地并行化，并且可以通过简单的实现实现接近线性的加速。对于并行算法，heapsort不是一个明显的候选对象。
• 合并排序可以调整为对具有O（1）额外空间的单链接列表进行操作。可以使Heapsort在仅具有O（1）额外空间开销的情况下对双链表进行操作。
• 合并排序用于外部排序；不是heapsort。引用的位置是问题。

PriorityQueue不是用于排序，而是用于在更改队列中获得最高优先级的元素。它还不会提高性能，也不会使您的代码使用可读以进行排序PriorityQueue。因此，我建议您Collections.sort()在分类时坚持使用。