Custom Comparator in Priority queue in Java

Question

I am trying to use a priority queue with a custom comparator, However I am not able to achieve my expected functionality.:

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class TestMain {

    public static void main(String[] args) {
        Queue<Node> queue = new PriorityQueue<>(new Comparator<Node>() {
            public int compare(Node a, Node b) {
                if(a.level == b.level) {
                    return a.data - b.data;
                }
                return a.level - b.level;
            }
        });
        
        queue.add(new Node(0,1));
        queue.add(new Node(1,2));
        queue.add(new Node(1,4));
        queue.add(new Node(2,3));
        queue.add(new Node(2,7));
        queue.add(new Node(2,2));
        queue.add(new Node(2,5));
        
        System.out.println(queue);
    }
    
    private static class Node {
        int level;
        int data;
        
        Node(int level, int data) {
            this.level = level;
            this.data = data;
        }
        
        public String toString() {
            return level + ":" + data;
        }
    }
}

Expected output = [0:1, 1:2, 1:4, 2:2, 2:3, 2:5, 2:7] Actual output = [0:1, 1:2, 1:4, 2:3, 2:7, 2:2, 2:5]

I want the elements in the priority queue to be ordered by the level first then by data.

new PriorityQueue<>(Comparator.comparingInt(Node::getLevel).thenComparing(Node::getData)) — chrylis -cautiouslyoptimistic-
– chrylis -cautiouslyoptimistic-, Commented Apr 23, 2021 at 4:40
Thanks, this is helpful, to use lambda instead of anonymous inner class — SRI HARSHA S V S
– SRI HARSHA S V S, Commented Apr 23, 2021 at 5:06

QuentinC · Accepted Answer · 2021-04-23 16:27:13Z

The method toString may not display the elements in retrieval order. So, it doesn't mean that your comparator is incorrect.

The following is written in the javadoc for PriorityQueu (emphasis is mine):

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() and the Spliterator provided in method spliterator() are not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

It isn't written explicitly here, but toString relies on iterators, therefore elements may not be displayed in the expected orther either. The toString method is defined in class Collection, and isn't specificly overridden here.

PriorityQueu is probably implemented using a binary heap in an array. From there, it follows naturally that iteration is made in array order. Displaying elements in the correct order would require removing them from the queue, and is therefore impossible except by sorting a copy somewhere else, what would be too heavy for a simple toString.

SRI HARSHA S V S · Accepted Answer · 2021-04-23 05:05:11Z

1

Actually the logic is correct, only thing is I am trying to do sysout, then it was showing in the order I have inserted, When I used the remove operation on the priority queue data is coming in expected format.

while(!queue.isEmpty()) {
    System.out.println(queue.remove());
}

Output: 0:1 1:2 1:4 2:2 2:3 2:5 2:7

answered Apr 23, 2021 at 5:05

SRI HARSHA S V S

1252 silver badges10 bronze badges

Collectives™ on Stack Overflow

Custom Comparator in Priority queue in Java

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related