Java - PriorityQueue 与排序 LinkedList

Question

哪种实现不那么“重”：PriorityQueue 还是排序的 LinkedList（使用比较器）？

我想把所有的物品都整理好。插入会非常频繁，有时我必须运行所有列表才能进行一些操作。

Answer 1

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

需要注意的一件事是，PriorityQueue 迭代器不按顺序提供元素；实际上，您必须删除元素（清空队列）才能按顺序迭代其元素。

Answer 2

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

Answer 3

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

在我的列表基准测试中，我测量了从开始填充值到排序结束的时间。对于 PriorityQueue - 从填充开始到轮询所有元素结束（因为元素在 PriorityQueue 中排序，同时按照 erickson 答案中提到的方式删除它们）

Answer 4

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

如果您需要按排序顺序获取所有元素，Collections.sort 总共大约需要 O n log (n) 时间。由于优先级队列中的每个 pol 将花费 O log(n) 时间，因此如果您从队列中获取所有 n 个事物，则将再次花费 O n log(n) 时间。

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

Answer 5

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

Answer 6

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

根据 PriorityQueue 文档：

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

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

Answer 7

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

Answer 8

您需要随时对其进行分类吗？如果是这种情况，您可能需要使用树集（或其他具有快速查找功能的 SortedSet）之类的东西。

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

Answer 9

java.util.PriorityQueue 是

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

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

Answer 10

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

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

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

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

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

Answer 11

恕我直言：如果有 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，我们真的不需要这个类。