Java – PriorityQueue与已排序的LinkedList
哪个实现不那么“重”：PriorityQueue或排序的LinkedList（使用Comparator）？
我希望将所有项目排序。 插入将是非常频繁和偶尔我将必须运行所有列表来进行一些操作。
LinkedList是最糟糕的选择。 使用ArrayList （或更一般地， RandomAccess实现者）或PriorityQueue 。 如果使用列表，则只在迭代其内容之前对其进行排序，而不是在每次插入之后对其进行排序。
需要注意的一点是， PriorityQueue迭代器不按顺序提供元素; 你实际上必须删除元素（清空队列）以按顺序迭代它的元素。
您应该实现两者，然后对实际数据进行性能测试，以查看哪些在您的特定情况下效果最佳。
我在这个问题上做了一个小基准。 如果您希望在所有插入结束后对列表进行排序，那么PriorityQueue和LinkedList之间几乎没有区别（LinkedList更好一点，在我的机器上快5到10％），但是如果你使用ArrayList，你会得到排序比PriorityQueue快2倍。
在我的列表基准测试中，我测量了从填充值到排序结束的时间。 对于PriorityQueue – 从填充开始到轮询结束所有元素（因为元素在PriorityQueue中排序，同时删除它们，如erickson回答中所述）
如果你使用LinkedList ，你需要在每次添加一个项目时使用这些项目，因为插入是频繁的，我不会使用LinkedList 。 所以在这种情况下，我会使用PriorityQueue ‘s如果您只将唯一元素添加到列表中，我建议使用SortedSet （一个实现是TreeSet ）。
这两种数据结构之间存在根本区别，它们并不像您想象的那样容易互换。
根据PriorityQueue文档：
方法iterator（）中提供的迭代器不保证以任何特定顺序遍历优先级队列的元素。
只有在迭代列表之前，才使用ArrayList并在其上调用Collections.sort（）。
PriorityQueue的问题是您必须清空队列才能按顺序获取元素。 如果这是你想要的那么它是一个很好的选择。 否则，您可以使用仅在需要排序结果时排序的ArrayList ，或者，如果项目是不同的（相对于比较器），则使用TreeSet 。 TreeSet和ArrayList在空间方面都不是很“重”; 哪个更快取决于用例。
将对象添加到优先级队列将是O log（n）并且对于每个pol都是相同的。 如果您经常在非常大的队列上进行插入，那么这可能会影响性能。 插入到ArrayList的顶部是不变的，因此总的来说，所有这些插入在ArrayList上的速度要比在优先级队列上快。
如果您需要按排序顺序获取所有元素，则Collections.sort将在大约O n log（n）时间内工作。 其中来自优先级队列的每个pol将是O log（n）时间，因此如果你从队列中获取所有n个东西，那将再次是O n log（n）。
优先级队列获胜的用例是，如果您尝试在任何给定时间查找队列中的最大值。 要使用ArrayList执行此操作，您必须在每次想要了解最大列表时对整个列表进行排序。 但是通过优先级队列，它始终知道最大的价值是什么。
你需要一直排序吗？ 如果是这种情况，您可能希望使用类似树集（或其他具有快速查找的SortedSet）。
如果您只需要偶尔对其进行排序，请使用链接列表并在需要访问时对其进行排序。 当您不需要访问权限时，请将其分类。
java.util.PriorityQueue是
“基于优先级堆的无界优先级队列”
。 堆数据结构比链表更有意义
我可以看到两个选项，哪个更好取决于您是否需要能够拥有重复的项目。
如果您不需要在列表中维护重复项，我将使用SortedSet（可能是TreeSet）。
如果您需要维护重复的项目，我会使用LinkedList并以正确的顺序将新项目插入到列表中。
除非您希望在执行操作时删除项目，否则PriorityQueue不适合。
与其他人一起使用，请确保使用性能分析以确保为特定问题选择正确的解决方案。
恕我直言：如果有LinkedList，我们不需要PriorityQueue。 我可以使用LinkedList对队列进行排序，而不是使用PriorityQueue。 例如
Queue list = new PriorityQueue(); list.add("1"); list.add("3"); list.add("2"); while(list.size() > 0) { String s = list.poll().toString(); System.out.println(s); }
我相信这段代码的工作时间太长，因为每次添加元素都会对元素进行排序。 但如果我将使用下一个代码：
Queue list = new LinkedList(); list.add("1"); list.add("3"); list.add("2"); List lst = (List)list; Collections.sort(lst); while(list.size() > 0) { String s = list.poll().toString(); System.out.println(s); }
我认为这段代码只会排序一次，使用PriorityQueue会更快。 所以，在任何情况下，我可以在使用它之前对LinkedList进行一次排序，它会更快地运行。 即使它在同一时间排序我并不真正需要PriorityQueue，我们真的不需要这个类。