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的节点就会移动到队列的顶部。有没有任何命令可以让优先级队列重新排序自己？add/offer方法应该可以做到这一点？