logo标签列表

Java 优先队列：返回最小元素作为第一个元素

javadata-structures
3
Java中的PriorityQueue类的javadoc中写道： "此队列的头部是根据指定的排序方式来确定最小元素。"
有人知道这个类是否旨在用作堆或者只是碰巧方便地符合堆的描述吗？ 如果它确实是一个堆，那么我对为什么他们选择选择“最小”的元素来通过remove()返回感到困惑 - 为什么“最小”的元素会具有最高优先级或像堆中使用的“最大”或“最老”的元素一样？
提前感谢您的帮助！
1
“最小元素”是一个抽象的术语，就像代数中一样。它指的是您定义的特定排序中的第一个元素。您可以使用各种各样的东西，如最大元素、最常请求的元素等等... - UmNyobe
@iralight，我很高兴我的评论对你有帮助；在做了更多的研究后，我把它移到了答案中。 - Pops
@UmNyobe，你是对的，它是抽象的，但是，如果没有自定义比较器和自然排序，Java会返回最小的整数或具有最小字符值的字符串...所以我很困惑。正如Lord Torgamus和Daniel Fischer所解释的那样，这是因为优先队列选择了最小堆。我正在阅读的基本数据结构书籍没有区分最小堆和最大堆，所以我不知道。再次感谢大家的帮助！ - iralight
4个回答
6
堆不一定返回最大的元素。那些能够这样做的堆被称为最大堆。Java堆是最小堆，它们与最大堆结构完全相同，只是在排序/比较步骤中使用大于号而不是小于号。
在查看 PriorityQueue的源代码/文档和浏览JLS之后，我没有看到任何表明为什么选择最小值而不是最大值的内容。可能只是一个抛硬币的结果，或者值组通常从1到n，其中1是头部并且是最小可能值。
堆只是优先队列抽象的一种实现。 - Louis Wasserman
3

堆有两种类型，最大堆和最小堆。Java的优先队列使用最小堆，因此头部/顶部是最小元素。

谢谢Daniel，这样解释得很清楚。 - iralight
0

一个常见的误解是认为优先队列就是一个堆。一个优先队列是一个抽象概念，就像“列表”或“映射”一样；就像列表可以用链表或数组实现一样，优先队列可以用堆或其他各种方法实现。

0
关于为什么 remove 返回最小元素，从快速浏览文档来看，我会认为这是因为优先级 1 在优先级 2 之前。
这个意思我能理解，但是在这种情况下优先级的定义让我感到困惑，而且是什么促使优先级1成为更小的整数或字母表中的第一个字符串呢？ - iralight
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接