Using PriorityQueue with any Comparator in Java

Question

Common question: How to use different Comparators of the custom class for sorting sequence its objects in PriorityQueue?

I tried to do that using this comparators in appropriate pairs of priorityqueues and lists of the objects with expected similar sorting results in the next code:

class User{
  private Integer id;
  private String name;
  public User(Integer i, String n){
    this.id=i;
    this.name=n;
  }
  public Integer getId() {return id;}
  public String getName() {return name;}
  @Override
  public boolean equals(Object obj) {
    if (this == obj)return true;
    if (obj == null)return false;
    if (getClass() != obj.getClass())return false;
    User other = (User) obj;
    if(id == null){
      if (other.id != null)return false;
    }else if(!id.equals(other.id))return false;
    return true;
  }
  @Override
  public String toString() {return "[id:" + id + ", name:" + name + "]";}
}

public class MyPriorityQueue {

  public static Comparator<User> cmpId = Comparator.comparingInt(x -> x.getId());
  public static Comparator<User> cmpNameLength = Comparator.comparingInt(x -> x.getName().length());

  public static void main(String[] args) {
    List<User> users = new ArrayList<User>(10);
    users.add(new User(1,"11111"));
    users.add(new User(3,"333"));
    users.add(new User(5,"5"));
    users.add(new User(4,"44"));
    users.add(new User(2,"2222"));

    Queue<User> ids = new PriorityQueue<User>(10, cmpId); //use first comparator
    users.forEach(x-> ids.offer(x));

    Queue<User> names = new PriorityQueue<User>(10, cmpNameLength); //use second comparator
    names.addAll(users);

    System.out.println("Variant_1.1:"); 
    ids.forEach(System.out::println);

    System.out.println("Variant_2.1:"); 
    names.forEach(System.out::println);

    System.out.println("Variant_1.2:"); 
    users.sort(cmpId);  //use first comparator
    users.forEach(System.out::println);

    System.out.println("Variant_2.2:"); 
    users.sort(cmpNameLength);  //use second comparator
    users.forEach(System.out::println);
  }
}

Output:

Variant_1.1: //Failed sorted queue by user.id with using comporator cmpId
  [id:1, name:11111]
  [id:2, name:2222]
  [id:5, name:5]
  [id:4, name:44]
  [id:3, name:333]
Variant_2.1: //Failed sorted queue by length of the user.name with cmpNameLength
  [id:5, name:5]
  [id:4, name:44]
  [id:3, name:333]
  [id:1, name:11111]
  [id:2, name:2222]
Variant_1.2: // OK: correctly sorted list by user.id with cmpId comporator
  [id:1, name:11111]
  [id:2, name:2222]
  [id:3, name:333]
  [id:4, name:44]
  [id:5, name:5]
Variant_2.2: //OK: for list by length of the user.name with cmpNameLength
  [id:5, name:5]
  [id:4, name:44]
  [id:3, name:333]
  [id:2, name:2222]
  [id:1, name:11111]

I expected that the:

results of the variant 1.1 and 2.1;
results of the variant 1.2 and 2.2;

will be same, but they were different.

My questions: What have I done wrong for ordering priorytyqueue/comparator and How to get sorting result for the priorityqueue as for the appropriate list in my example?

Enno Shioji · Accepted Answer · 2017-07-14 18:55:53Z

1

You haven't done anything wrong, it's just that PriorityQueue's iterator is:

not guaranteed to traverse the elements of the priority queue in any particular order (Javadoc)

The forEach method internally uses the iterator, so the same problem exists.

This is because the underlying data structure is such that it "sorts" as you deque items. If the implementor wanted to return items in sorted order, they would have had to first collect the items, and then sort them before returning them. This incurs a performance hit, and so (I presume) it was decided to return it unordered, because PriorityQueue is primarily a queue, rather than a sorted collection, and a user could always sort the item themselves (which is as efficient as it gets).

In order to obtain the elements ordered, do something like:

  while(pq.peek() != null){
      System.out.println(pq.poll());
  }

edited Jul 14, 2017 at 18:55

answered Jul 14, 2017 at 18:34

Enno Shioji

26.9k13 gold badges77 silver badges111 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Chris Nauroth · Accepted Answer · 2017-07-21 18:29:27Z

In your code sample, you are using Iterable#forEach to iterate through the queues.

ids.forEach(System.out::println);

names.forEach(System.out::println);

forEach ultimately delegates into Iterable#iterator. However, it's important to note that the subclass override in PriorityQueue#iterator has different JavaDocs with a special note about ordering.

Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.

In other words, there is no guarantee that iterating over a PriorityQueue will use your Comparator. If instead you changed your code to drain the queue by repeatedly calling PriorityQueue#poll, then I expect you'd see results ordered according to your custom Comparator.

Digging into the OpenJDK source, we can see that the internal data structure inside PriorityQueue is a binary heap. This is backed by an array, and as callers add and remove elements of the queue, the code internally maintains the heap invariant.

/**
 * Priority queue represented as a balanced binary heap: the two
 * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
 * priority queue is ordered by comparator, or by the elements'
 * natural ordering, if comparator is null: For each node n in the
 * heap and each descendant d of n, n <= d.  The element with the
 * lowest value is in queue[0], assuming the queue is nonempty.
 */
transient Object[] queue; // non-private to simplify nested class access

However, the internal Iterator implementation simply uses an integer cursor to scan forward through that array, with no consideration of element priorities or heap layout.

            return (E) queue[lastRet = cursor++];

Thank you for clarifying about the "forEach". After correcting the code "while(!ids.isEmpty())System.out.println(ids.poll());" instead of "ids.forEach(System.out::println);", the expected result was obtained.

Collectives™ on Stack Overflow

Using PriorityQueue with any Comparator in Java

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related