Java - PriorityQueue 与排序的 LinkedList

Java - PriorityQueue vs sorted LinkedList

提问by msr

Which implementation is less "heavy": PriorityQueue or a sorted LinkedList (using a Comparator)?

哪个实现不那么“重”：PriorityQueue 或已排序的 LinkedList（使用比较器）？

I want to have all the items sorted. The insertion will be very frequent and ocasionally I will have to run all the list to make some operations.

我想对所有项目进行排序。插入将非常频繁，有时我将不得不运行所有列表以进行一些操作。

回答by erickson

A LinkedListis the worst choice. Either use an ArrayList(or, more generally, a RandomAccessimplementor), or PriorityQueue. If you do use a list, sort it only before iterating over its contents, not after every insert.

ALinkedList是最差的选择。要么使用ArrayList（或更一般地说，RandomAccess实现者），要么使用PriorityQueue。如果确实使用了列表，请仅在迭代其内容之前对其进行排序，而不是在每次插入之后对其进行排序。

One thing to note is that the PriorityQueueiterator does notprovide the elements in order; you'll actually have to remove the elements (empty the queue) to iterate over its elements in order.

有一点要注意的是，PriorityQueue迭代器不提供顺序的元素; 您实际上必须删除元素（清空队列）以按顺序迭代其元素。

回答by nohat

You should implement both and then do performance testing on actual data to see which works best in your specific circumstances.

您应该同时实现这两种方法，然后对实际数据进行性能测试，以查看哪种方法最适合您的特定情况。

回答by maks

I have made a small benchmark on this issue. If you want your list to be sorted after the end of allinsertions then there is almost no difference between PriorityQueueand LinkedList(LinkedList is a bit better, from 5 to 10 percents quicker on my machine), however if you use ArrayList you will get almost 2 times quicker sorting than in PriorityQueue.

我在这个问题上做了一个小基准。如果您希望在所有插入结束后对您的列表进行排序，那么PriorityQueue和之间几乎没有区别LinkedList（LinkedList 好一点，在我的机器上快 5% 到 10%），但是如果您使用 ArrayList，您将获得几乎 2排序比 PriorityQueue 快几倍。

In my benchmark for lists I measured time from the beginning of filling it with values till the end of sorting. For PriorityQueue - from the beginning of filling till the end of polling all elements(because elements get ordered in PriorityQueue while removing them as mentioned in ericksonanswer)

在我的列表基准测试中，我测量了从开始填充值到排序结束的时间。对于 PriorityQueue - 从填充开始到轮询所有元素结束（因为元素在 PriorityQueue 中被排序，同时如ericksonanswer 中提到的那样删除它们）

回答by greta

adding objects to the priority queue will be O log(n) and the same for each pol. If you are doing inserts frequently on very large queues then this could impact performance. Inserting into the top of an ArrayList is constant so on the whole all those inserts will go faster on the ArrayList than on the priority queue.

将对象添加到优先级队列将是 O log(n) 并且对于每个 pol 都是相同的。如果您经常在非常大的队列上执行插入操作，那么这可能会影响性能。插入到 ArrayList 的顶部是恒定的，因此总的来说，所有这些插入在 ArrayList 上的速度比在优先级队列上要快。

If you need to grab ALL the elements in sorted order the Collections.sort will work in about O n log (n) time total. Where as each pol from the priority queue will be O log(n) time, so if you grab all n things from the queue that will again be O n log (n).

如果您需要按排序顺序获取所有元素，则 Collections.sort 将在大约 O n log (n) 的总时间内工作。因为优先级队列中的每个 pol 都是 O log(n) 时间，所以如果你从队列中获取所有 n 东西，这将再次是 On log (n)。

The use case where priority queue wins is if you are trying to find what the biggest value in the queue is at any given time. To do that with the ArrayList you have to sort the whole list each time you want to know the biggest. But with the priority queue it always knows what the biggest value is.

优先队列获胜的用例是，如果您试图找到任何给定时间队列中的最大值。要使用 ArrayList 做到这一点，每次您想知道最大的列表时，您都必须对整个列表进行排序。但是对于优先级队列，它总是知道最大的值是什么。

回答by Jeff Storey

If you use a LinkedList, you would need to resort the items each time you added one and since inserts are frequent, I wouldn't use a LinkedList. So in this case, I would use a PriorityQueue's If you will only be adding unique elements to the list, I recommend using a SortedSet(one implementation is the TreeSet).

如果您使用 a LinkedList，则每次添加项目时都需要重新使用这些项目，并且由于插入频繁，我不会使用LinkedList. 因此，在这种情况下，我将使用 a PriorityQueue's 如果您只将唯一元素添加到列表中，我建议使用 a SortedSet（一个实现是TreeSet）。

回答by Tim Bender

There is a fundamental difference between the two data structures and they are not as easily interchangeable as you might think.

这两种数据结构之间存在根本区别，它们并不像您想象的那样容易互换。

According to the PriorityQueue documentation:

根据 PriorityQueue 文档：

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order.

方法 iterator() 中提供的 Iterator 不保证以任何特定顺序遍历优先级队列的元素。

Use an ArrayList and call Collections.sort() on it only before iterating the list.

使用 ArrayList 并仅在迭代列表之前对其调用 Collections.sort() 。

回答by Kathy Van Stone

The issue with PriorityQueueis that you have to empty the queue to get the elements in order. If that is what you want then it is a fine choice. Otherwise you could use an ArrayListthat you sort only when you need the sorted result or, if the items are distinct (relative to the comparator), a TreeSet. Both TreeSetand ArrayListare not very 'heavy' in terms of space; which is faster depends on the use case.

问题PriorityQueue在于您必须清空队列才能按顺序获取元素。如果这就是您想要的，那么这是一个不错的选择。否则，您可以ArrayList仅在需要排序结果时使用排序，或者，如果项目不同（相对于比较器），则使用TreeSet. 双方TreeSet并ArrayList在空间上不是很“重”; 哪个更快取决于用例。

回答by deterb

I can see two options, which one is better depends on whether you need to be able to have duplicate items.

我可以看到两个选项，哪个更好取决于您是否需要能够拥有重复项。

If you don't need to maintain duplicate items in your list, I would use a SortedSet (probably a TreeSet).

如果您不需要维护列表中的重复项，我会使用 SortedSet（可能是 TreeSet）。

If you need maintain duplicate items, I would go with an LinkedList and insert new items into the list in the correct order.

如果您需要维护重复的项目，我会使用 LinkedList 并以正确的顺序将新项目插入列表中。

The PriorityQueue doesn't really fit unless you want to remove the items whenever you do operations.

PriorityQueue 并不真正适合，除非您想在执行操作时删除这些项目。

Going along with the others, make sure you use profiling to make sure you're picking out the correct solution for your particular problem.

与其他人一起，确保使用分析来确保为您的特定问题选择正确的解决方案。

回答by corsiKa

Do you need it sorted at all times? If that's the case, you might want to go with something like a tree-set (or other SortedSet with a fast lookup).

你需要一直排序吗？如果是这种情况，您可能想要使用树集（或其他具有快速查找功能的 SortedSet）之类的东西。

If you only need it sorted occasionally, go with a linked list and sort it when you need access. Let it be unsorted when you don't need access.

如果您只是偶尔需要对其进行排序，请使用链表并在需要访问时对其进行排序。当您不需要访问时，让它不排序。

回答by ring bearer

java.util.PriorityQueueis

java.util.PriorityQueue是

"An unbounded priority queue based on a priority heap"

“基于优先级堆的无界优先级队列”

. The heap data structure make much more sense than a linked list

. 堆数据结构比链表更有意义