Priority Queue<Integer>=k ，不删除 distance[k] 为 min 的 k

Question

int[] distance = new int[100];
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        if (distance[o1] > distance[o2] ) {
            return -1;
        } else if (distance[o1] < distance[o2] ) {
            return 1;
        }
        return 0;
    }
});


for (int i = 0; i < 100; i++) {
    distance[i] =new Random().nextInt(100)+1;
    pq.add(i);
}

distance[10]=0;
int u=pq.poll();

我认为这个比较器应该 return 距离 [k]=MinimumDistance 的元素 k。无法理解为什么这不起作用.. pq.Poll 它不是基于 distance[] 数组。例如这里变量 u 应该是 10.

Answer 1

两个问题：你的比较是反的。应该是

if (distance[o1] > distance[o2] ) {
    return 1;
} else if (distance[o1] < distance[o2] ) {
    return -1;
}

其次，你必须在循环之前设置distance[10]=0，然后不覆盖它。这个比较器只在添加东西时起作用，然后你在位置 10 有一个随机数。

Priority Queue<Integer>=k ，不删除 distance[k] 为 min 的 k

Priority Queue<Integer>=k ,does not remove the k where distance[k] is min

java

priority-queue