java - Java 中的 PriorityQueue 无法按预期工作。具有较高优先级的对象被插入到队列的末尾

Question

package algo5;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

public class prim {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        List<node> g = new ArrayList<node>();

        for (int i = 0; i < 6; i++) {
            node n =new node(i);
            n.name = i;
            g.add(n);
        }
        prim p = new prim();
        p.pushdata(g, 0, 1, 5);
        p.pushdata(g, 0, 2, 6);
        p.pushdata(g, 0, 3, 4);
        p.pushdata(g, 1, 2, 1);
        p.pushdata(g, 1, 3, 2);
        p.pushdata(g, 2, 3, 2);
        p.pushdata(g, 2, 4, 5);
        p.pushdata(g, 2, 5, 3);
        p.pushdata(g, 3, 5, 4);
        p.pushdata(g, 4, 5, 4);

        p.prim(g, g.get(0));

    }

    public void pushdata(List<node> g, int a, int b, int c){
        g.get(a).neighbours.add(g.get(b));
        g.get(b).neighbours.add(g.get(a));
        if (!g.get(a).lenmap.containsKey(b)) {
            g.get(a).lenmap.put(b, c);
        }
        if (!g.get(b).lenmap.containsKey(a)) {
            g.get(b).lenmap.put(a, c);
        }
    }


    public void prim(List<node> g, node s){
        int inf = 10000;
        for (node node : g) {
            node.cost = inf;
            node.prev = null;
            node.visited = false;
        }

        s.cost = 0;

        PriorityQueue<node> myQ = new PriorityQueue<node>();

        myQ.addAll(g);

        List<node> res = new ArrayList<node>();

        node u = null;

        while (!myQ.isEmpty()) {
            u = myQ.poll();
            if (!u.visited) {
                u.visited = true;
                res.add(u);
                for (node n : u.neighbours) {
                    if (n.cost>u.lenmap.get(n.name)) {
                        n.cost = u.lenmap.get(n.name);
                        n.prev = u;
                        myQ.offer(n);
                    }
                }
            }
        }

        for (node node : res) {
            System.out.println(node.name);
        }
    }
}

class node implements Serializable, Comparable{
    int name;
    int cost;
    node prev = null;
    boolean visited = false;
    LinkedList<node> neighbours;
    HashMap<Integer, Integer> lenmap;

    public node(int name){
        this.name = name;
        neighbours = new LinkedList<node>();
        lenmap = new HashMap<Integer, Integer>();
    }

    public boolean equals(node b){
        if (b.name==this.name) {
            return true;
        }
        return false;
    }

    @Override
    public int compareTo(Object a) {
        // TODO Auto-generated method stub
        node b = (node)a;       
        return this.cost-b.cost;
    }
}

在第 68 行，将邻居插入回队列的 while 循环在循环第一次迭代结束时将名称为 3 的节点插入到队列末尾。但由于我使用了优先级队列，我希望将其插入到队列的顶部或头部。但在第二次迭代期间，一旦我轮询队列的头部，名称为 3 的节点就会被移动到队列的顶部。是否有任何命令可以让优先级队列自行重新排序？添加/提供方法应该完成这个任务吗？

Answer 1

JavaDoc for PriorityQueue说

"The head of this queue is the least element with respect to the specified ordering."

听起来您的队列的行为符合设计。如果您想反转顺序，只需翻转 node 类的 compareTo 方法中的条件即可。