java - PriorityQueue 与 Collections.sort

Question

我什么时候会选择Collections.sort()在 PriorityQueue ，当我知道 PQ 在时间复杂度方面会更好？

Answer 1

轮询 PriorityQueue它的所有元素都是有效的 heap sorting . Collections.sort()使用 merge sorting 实现.堆排序和归并排序在时间复杂度上是可比的。两者都具有最佳情况、最坏情况和平均情况 O(n log n) 时间复杂度。
在性能方面，这就是 wikipedia不得不说:

Heapsort also competes with merge sort, which has the same time bounds. Merge sort requires Ω(n) auxiliary space, but heapsort requires only a constant amount. Heapsort typically runs faster in practice on machines with small or slow data caches. On the other hand, merge sort has several advantages over heapsort:

• Merge sort on arrays has considerably better data cache performance, often outperforming heapsort on modern desktop computers because merge sort frequently accesses contiguous memory locations (good locality of reference); heapsort references are spread throughout the heap.
• Heapsort is not a stable sort; merge sort is stable.
• Merge sort parallelizes well and can achieve close to linear speedup with a trivial implementation; heapsort is not an obvious candidate for a parallel algorithm.
• Merge sort can be adapted to operate on singly linked lists with O(1) extra space. Heapsort can be adapted to operate on doubly linked lists with only O(1) extra space overhead.[citation needed]
• Merge sort is used in external sorting; heapsort is not. Locality of reference is the issue.

PriorityQueue不是为了排序，而是为了在不断变化的队列中获取最高优先级的元素。它也不会提高性能，也不会使您的代码可读，以便使用 PriorityQueue 进行排序。 .因此，我建议您坚持使用 Collections.sort()说到排序。