Java - 寻找比 PriorityQueue 更快的东西

Question

我正在对大量数据使用 java。

[我尽量简化问题]

实际上我有一个小类(Element)，其中包含一个 int KEY 和一个 double WEIGHT(带有 getters 和 setters)。

我从一个文件中读取了很多这样的对象，我必须得到最好的(最重的)M 个对象。

实际上，我正在使用带有比较器的 PriorityQueue 来比较两个元素，它可以工作，但速度太慢。

你知道(我知道你知道)有什么更快的方法吗？

谢谢

Answer 1

基于堆的优先队列是解决这个问题的一个很好的数据结构。正如健全性检查一样，验证您是否正确使用了队列。

如果您想要最高权重的项目，请使用 min 队列——堆的顶部是最小的项目。将每个项目添加到最大队列并在完成后检查顶部的 M 项目效率不高。

对于每个项目，如果队列中的项目少于M，则添加当前项目。否则，查看堆的顶部。如果它小于当前项，则丢弃它，并添加当前项。否则，丢弃当前项目。处理完所有项目后，队列将包含 M 个权重最高的项目。

有些堆有替换堆顶的快捷API，但Java的Queue没有。即便如此，大 O 复杂度是相同的。