如何配置 Java 优先级队列以忽略重复项？

Question

我以为 add() 应该忽略重复项，但我的输出有重复项。如何不存储重复项？

我还想知道优先队列如何检查两个元素是否重复。我猜它正在使用比较器等于，但我只是想确定一下。

谢谢

原文由 sgarg 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

这是 PriorityQueue Javadoc 的一部分：

此队列根据构造时指定的顺序对元素进行排序，该顺序根据元素的自然顺序（请参阅 Comparable）或根据 Comparator 指定，具体取决于使用的构造函数。

所以是的，PriorityQueue 使用 Comparator（如果您将其指定为构造函数参数）或使用 compareTo(…) 方法（元素必须实现 Comparable 接口）。

PriorityQueue 允许重复。所以如果你想避免这种情况，你需要实现你自己的 Queue 版本。您可以在 第 85 页的“Effective Java” 中找到非常优雅的方法，如何做到这一点。或者，您可以扩展 PriorityQueue 类并覆盖 add 方法（这是放置 contains(…) 检查的完美位置）。

原文由 Sebastian Łaskawiec 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

Java 中的 PriorityQueue 对重复元素没有任何限制。如果你想确保两个相同的项目永远不会同时出现在优先级队列中，最简单的方法是维护一个单独的 Set 与优先级队列并行。每次你想将一个元素插入优先级队列时，你可以检查集合是否已经包含它，如果没有，则将它添加到集合和优先级队列中。每当您从优先级队列中删除一个元素时，也只需从集合中删除该元素。

或者，根据您打算在优先级队列上执行哪些操作，以及在您的情况下如何定义相等性，将它替换为单个 TreeSet 可能是可行的，因为这仍然允许您执行您可以在优先级队列中访问的所有重要操作，同时它也不允许重复。

原文由 Jiddo 发布，翻译遵循 CC BY-SA 3.0 许可协议