PriorityQueue in Java does not work as expected. Objects with higher priority are inserted at end of the queue

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;
    }
}

At line 68, the while loop which inserts neighbours back in to the queue inserts the node with name 3 at the end of queue during the end of first iteration of the loop. But as I have used a priority queue, I expect it to be inserted at the top or head of the queue. But during the second iteration, as soon as I poll the head of the queue, the node with name 3 is moved to the top of the queue. Is there any command to give Priority Queue to re-sort itself? The add/offer methods should accomplish this right?

Answer 1

The JavaDoc for PriorityQueue says

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

So it sounds like your queue is behaving as designed. If you'd like to reverse the ordering, simply flip around the condition in your node class' compareTo method.