从 Java 中的 PriorityQueue 中间检索项目

Question

给定以下代码：

import java.util.*;

class SimpleTest {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.add(1);
        pq.add(2);
        pq.add(3);
        pq.add(4);
        pq.add(5);
        pq.add(6);
        pq.add(7);

        int index = 0;
        int middleNumber = 0;
        Iterator it = pq.iterator();

        //Is number odd
        if(pq.size() % 2 != 0) {
            System.out.println(pq.size());

            //keep removing from queue until we reached queueSize/2 (rounded up)
            while(it.hasNext() && index++ <= ((pq.size() >> 1) + 1)) {
                middleNumber = pq.poll();
            }
            System.out.println("The middle number is: " + (float)middleNumber);
        }       

    }
}

这适用于一些奇数，但不适用于其他，我不明白为什么。

给定一个包含 7 个项目的队列，上面的代码 returns 4 位于队列的中间。

但是如果我尝试使用包含 9 个元素 (1-9) 的队列。它也 returns 4，当它应该是 5 时。

为什么会这样？

Answer 1

PriorityQueue 的迭代器不按优先顺序迭代，只是按基础集合的自然顺序迭代。请参阅 Javadoc。

获得优先顺序的唯一方法是调用 PriorityQueue.remove().

Answer 2

主要问题是这一行：

                middleNumber = pq.poll();

减小队列的大小，这会影响这行的含义：

            while(it.hasNext() && index++ <= ((pq.size() >> 1) + 1)) {

然后是次要问题——while 表达式写错了——我认为这是因为你试图调整 while 以适用于队列以 7 个元素开始的情况，不了解潜在的错误。

相反，您应该预先计算所需的索引，然后轮询到该点：

int indexOfMiddleNumber = pq.size() / 2;
for (int index = 0; index < indexOfMiddleNumber; ++index) {
    pq.poll();
}
int middleNumber = pq.poll();

（请注意，迭代器没有用，在循环中调用 it.hasNext() 实际上是一个非常糟糕的主意，该循环也会修改基础集合。令我惊讶的是 PriorityQueue 不是'为此给你一个ConcurrentModificationException。）

从 Java 中的 PriorityQueue 中间检索项目

Retrieve item from the middle of a PriorityQueue in Java

java

priority-queue