java - 如何查看 java.util.PriorityQueue 的尾部？

Question

所以我在玩 java.util.PriorityQueue 的源代码.您可以在这里查看:http://kickjava.com/src/java/util/PriorityQueue.java.htm

我需要查看队列的尾部。这个类只提供窥视队列的头部。有没有一种简单的方法可以修改这个类以允许我选择尾部？

我正在这门课中寻找任何改变/聪明的技巧来让我做到这一点。我的第一次尝试是偷看 queue[size]但它没有用。

Answer 1

Java 的 PriorityQueue 和大多数优先级队列一样，是用堆实现的。

堆是一种数据结构，它只维护所有 parent 都小于他们的 child ，或者所有 parent 都大于他们的 child 的属性。 child 之间没有固有的秩序。

因此，找到尾部的唯一方法是在底层之间进行线性搜索，代价是 O(n)大小的时间 n优先队列。