PriorityQueue custom sorting

Admin 1
Viewed 1261

I have implemented a custom comparator for my priority queue of nodes but for some reason it is not working. Any help is appreciated. I also get the same result if my Node class implements comparable.

Queue<Node> queue = new PriorityQueue<>(new Comparator<Node>()
{

        public int compare(Node node1, Node node2)
        {
            if (node1.getCost() < node2.getCost())
            {
                return -1;
            }
            else if (node1.getCost() < node2.getCost())
            {
                return 1;
            }

            return 0;
        }
});

    Node node1 = new Node(initState, null,0);
    node1.setCost(20);
    Node node2 = new Node(initState, null,0);
    node2.setCost(15);
    Node node3 = new Node(initState, null,0);
    node3.setCost(10);
    Node node4 = new Node(initState, null,0);
    node4.setCost(5);
    Node node5 = new Node(initState, null,0);
    node5.setCost(4);
    Node node6 = new Node(initState, null,0);
    node6.setCost(3);

    for (Node node : queue)
    {
        System.out.println(node.getCost());
    }

Output

3

5

4

20

10

15

comparator priority-queue java
2 Answers

Your Comparator class has a mistake. "if" as well as "else if" checks the same condition. Check below for corrected version.

new Comparator<Node>()
{

    public int compare(Node node1, Node node2)
    {
        if (node1.getCost() < node2.getCost())
        {
            return -1;
        }
        else if (node1.getCost() > node2.getCost())
        {
            return 1;
        }

        return 0;
    }
}

I assume you are familiar with the Comparator concept, and above was a typo. If that is not the case, you might be able to learn more on that here.

user_25811280

Browsing your collection with a "foreach" uses the Iterator resulting from PriorityQueue.iterator().

The javadoc of this method mentions that

The iterator does not return the elements in any particular order.

You will have to use another way to iterate over your PriorityQueue.

The following should work :

while(!queue.isEmpty()) {
    Node currentNode = queue.poll();
    // ...
}
user_16783620
Related