Java PriorityQueue返回最小元素作为第一个

Java中的PriorityQueue的javadoc说：该队列的头部相对于指定的排序是最少的元素。Java PriorityQueue返回最小元素作为第一个

有谁知道这个类是打算用作堆还是只是碰巧适合堆描述？如果它应该是堆，那么我很困惑，为什么他们选择通过remove（）返回的'least'元素？为什么'least'元素具有最优先级或者像'最大堆中使用'或'最古老'元素？

在此先感谢

2012-01-24 iralight

谢谢，这说明了它:) – iralight

'最小元素'是一个抽象的术语，就像在代数中一样。它意味着您定义的特定顺序的第一个元素。你可以使用各种各样的东西，最大的元素，最需要的元素，等等...... – UmNyobe

@iralight，我很高兴我的评论帮助你;不过，我在做了一些更多的研究之后，将它转移到了答案上。 – Pops

堆不一定应该返回的最大元素。这样做的堆被称为最大堆。 Java堆是最小堆，除了在排序/比较步骤中使用大于号而不是小于号之外，它们是完全相同的结构。

通过查看source code/documentation for PriorityQueue并略过JLS后，我看不到任何指示min选择超过max的任何内容。它可能只是一个硬币翻转，或者价值群体经常从1到n，1是头部和最小可能值。

2012-01-24 17:13:03 Pops

堆只是一个实现优先队列抽象。 –

堆有两个品种，最大堆和最小堆。 Java PriorityQueue使用最小堆，所以head/top是最小的元素。

2012-01-24 17:04:45

感谢丹尼尔，这也阐明了它 – iralight

至于为何最小元素被删除返回，从文档的快速审阅，我会承担，使优先级1优先级来前2个

2012-01-24 17:07:28 stjohnroe

是有道理的，但我对这种情况下的优先级定义感到困惑，什么动机优先级1是一个较小的整数或字母表的第一个字符串 – iralight

这是一个常见的误解，优先队列是一堆。 A 优先队列是一个抽象的概念，如“一个列表”或“一个地图”;就像列表可以用链表或数组实现一样，优先级队列可以用堆或其他各种方法来实现。

2013-08-21 13:54:16 inter18099

回答