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?

Yes, but when I try to add an element which has a higher priority(In the above case, lower cost), should it not add that element to the head of the queue? Because it works in the first two runs of internal foreach loop where node cost is 5 and 6 and these are inserted according to the comparable property. But in the third run, when an element with cost 4 is added to the queue, it gets inserted at the end. — BreadBoard, Feb 25 '16 at 06:21

score 3 · Answer 1 · answered Feb 25 '16 at 06:18

3

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.

answered Feb 25 '16 at 06:18

nbrooks

18,126
5
54
66

I am not asking this question in case of a tie between two objects. When I add another element with a higher priority, it does not get added to the head of the queue. The least element is being added to the end of the queue. – BreadBoard Feb 25 '16 at 06:24
@BreadBoard The comment from the JavaDocs isn't related to a tie between objects. It means the lowest priority element is added to the head of the queue. It's essentially a min heap in how it functions. If you want to get the highest priority element from the head, rather than the lowest priority, you can use [`Collections.reverseOrder()`](https://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#reverseOrder()) as cited in [this answer](http://stackoverflow.com/a/8349072/803925). – nbrooks Feb 25 '16 at 06:31
A usage of that technique is also shown in [this answer](http://stackoverflow.com/a/11003264/803925), which passes the Collections API comparator into the constructor for the `PriorityQueue`. – nbrooks Feb 25 '16 at 06:34
I understand that we need to use Collections.reverseOrder() for getting elements with highest priority. However, in my question, what I ask is, why is the element with cost=5 is positioned in the head of the queue even after I add another element with cost=4. The comparable should position cost=4 upon the cost=5 when I use the add or offer method. This works when I add cost =6 element and it is positioned below cost=5 element. When I add cost=6 with a queue that has a head of cost=5, it gets positioned after it. But when I add cost=4 to the same, it gets positioned at the end of the queue. – BreadBoard Feb 25 '16 at 06:47
What I mean is, when I expect the order in terms of cost to be 4,5,6, what I am getting is 5,6,4. From what I understand regarding the PriorityQueue, the order should either be 4,5,6 or 6,5,4. – BreadBoard Feb 25 '16 at 06:57
1

@BreadBoard How are you determining the order of the elements? Also from the doc: `"The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order."` You would need to repeatedly call the `poll` method to retrieve elements from the queue, and they will come off in the order 4, 5, 6. – nbrooks Feb 25 '16 at 14:13

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

1 Answers1