最大优先级队列函数

Question

我定义了一个最大优先级队列如下：

    PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

    queue.add(25);
    queue.add(3);
    queue.add(1);
    queue.add(3);
    queue.add(4);

我需要了解这是如何工作的，尤其是当 1 仅获得 2（而非 4）的索引时？

谢谢。

Answer 1

它没有保证顺序（https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/PriorityQueue.html）：

The Iterator provided in method iterator() and the Spliterator provided in method spliterator() are not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

通常您使用 poll() 方法根据自然顺序检索元素，例如：

 while (!queue.isEmpty()) {
     var element = queue.poll();
     ...
 }

编辑：

如果你想看看class的内部结构，this part of the code可能是相关的（它基本上使用堆数据结构）：

/**
 * Priority queue represented as a balanced binary heap: the two
 * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
 * priority queue is ordered by comparator, or by the elements'
 * natural ordering, if comparator is null: For each node n in the
 * heap and each descendant d of n, n <= d.  The element with the
 * lowest value is in queue[0], assuming the queue is nonempty.
 */
transient Object[] queue;

Answer 2

这个 class 使用名为 Heap 的结构，并将其存储在数组中。

当您 poll 时，您将按正确的顺序收到物品。

最大优先级队列函数

Maximum priority queue functions

java

priority-queue