419

How do I get a PriorityQueue to sort on what I want it to sort on?

Also, is there a difference between the offer and add methods?

Just a student
  • 10,560
  • 2
  • 41
  • 69
Svish
  • 152,914
  • 173
  • 462
  • 620

13 Answers13

485

Use the constructor overload which takes a Comparator<? super E> comparator and pass in a comparator which compares in the appropriate way for your sort order. If you give an example of how you want to sort, we can provide some sample code to implement the comparator if you're not sure. (It's pretty straightforward though.)

As has been said elsewhere: offer and add are just different interface method implementations. In the JDK source I've got, add calls offer. Although add and offer have potentially different behaviour in general due to the ability for offer to indicate that the value can't be added due to size limitations, this difference is irrelevant in PriorityQueue which is unbounded.

Here's an example of a priority queue sorting by string length:

// Test.java
import java.util.Comparator;
import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        Comparator<String> comparator = new StringLengthComparator();
        PriorityQueue<String> queue = new PriorityQueue<String>(10, comparator);
        queue.add("short");
        queue.add("very long indeed");
        queue.add("medium");
        while (queue.size() != 0) {
            System.out.println(queue.remove());
        }
    }
}

// StringLengthComparator.java
import java.util.Comparator;

public class StringLengthComparator implements Comparator<String> {
    @Override
    public int compare(String x, String y) {
        // Assume neither string is null. Real code should
        // probably be more robust
        // You could also just return x.length() - y.length(),
        // which would be more efficient.
        if (x.length() < y.length()) {
            return -1;
        }
        if (x.length() > y.length()) {
            return 1;
        }
        return 0;
    }
}

Here is the output:

short

medium

very long indeed

Community
  • 1
  • 1
Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
  • 10
    Hmm... just noticed... priorityQueue.comparator() "Returns the comparator used to order this collection, or null if this collection is sorted according to its elements natural ordering (using Comparable)." Does that mean I could just implement Comparable on my class as well? – Svish Mar 25 '09 at 19:56
  • Yes if you implement comparable in your class that would work as well – zpesk Mar 25 '09 at 20:19
  • 7
    You could, yes. I wouldn't do so unless there's a single natural sort order for your class though. If there is, that's the right thing to do :) – Jon Skeet Mar 25 '09 at 20:20
  • @Jon Skeet My PriorityQueue wont naturally sort when I implement Comparable to the object it contains. I created a @Override compareTo method but it still refuses to sort when objects are added to it. Any ideas? – Trevor Arjeski Apr 17 '11 at 16:44
  • @Trevor: How are you trying to access the sorted list? Just iterating over the list won't do it, I believe. Using the code above (repeatedly removing) should work though. If not, please post a new question with a short but complete example. – Jon Skeet Apr 17 '11 at 16:51
  • @Jon thanks, here is a link to the question: http://stackoverflow.com/questions/5695017/priorityqueue-not-sorting-on-add – Trevor Arjeski Apr 17 '11 at 17:12
  • @JonSkeet Can we combine the 2 if's into an else if? – pratnala Mar 03 '14 at 12:49
  • @pratnala: Sure, if you want to. Adding an `else` has no effect given that the branches `return` anyway. – Jon Skeet Mar 03 '14 at 12:57
  • 10
    Shouldn't the `compare` implementation just be `return x.length() - y.length()`? (Avoids branch prediction) – Franky May 08 '14 at 06:24
  • 8
    @Franky: It could be, yes - although I'd say that's *slightly* harder to understand, and the purpose of the answer is demonstrating how it works. I'll add a comment though. – Jon Skeet May 08 '14 at 12:00
  • Also, priorityQueue does not allow null elements, so the comment about robustness in comparator is irrelevant, isn't it? – Daddy32 Nov 11 '14 at 14:35
  • 1
    @Daddy32: Only if you're creating a comparator *just* for `PriorityQueue`. – Jon Skeet Nov 11 '14 at 14:37
  • Can you guys take a look at my use of a PriorityQueue in http://stackoverflow.com/questions/28800287/how-to-restore-the-priorityqueue-to-its-initial-state-before-the-method-call?noredirect=1#comment45875800_28800287 ? – committedandroider Mar 02 '15 at 00:40
  • PriorityQueue queue = new PriorityQueue(10, comparator);can you help me explain why we can write like this(10,comparator),what does it mean(10,comparator))? – python3 Apr 05 '15 at 18:56
  • @tiandiao123: Did you read the documentation to try to find out? – Jon Skeet Apr 05 '15 at 19:40
  • @JonSkeet : Your example is useful, but a small remark; you have used `.remove()` method from the superclass to get+remove the element from the queue. However the class `PriorityQueue` offers a [`poll()`](http://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html#poll)-method which doesn't throw an exception if no element is found (returns with null instead). Should i use `poll()` or `remove()` ? Or does it matter of the implementation ? – KarelG Apr 12 '15 at 08:04
  • 2
    @KarelG: I don't *think* it matters too much, so long as you're aware of the differences. I think if you're using `add()` for the adding operation, then `remove()` feels sensible; if I were using `offer()` I'd probably use `poll()`... but that's just a personal preference. – Jon Skeet Apr 12 '15 at 11:24
  • @JonSkeet Hi, when I tried to implement your class, an error message poped because of the linke of Comparator comparator = new StringLengthComparator(); – Appalachian Math Sep 01 '16 at 22:47
  • @JonSkeet the error msg says No enclosing instance of type TestStringCom is accessible. Must qualify the allocation with an enclosing instance of type TestStringCom (e.g. x.new A() where x is an instance of TestStringCom). – Appalachian Math Sep 01 '16 at 22:48
  • @AppalachianMath: Then you're trying to use an inner class. My code doesn't do that. – Jon Skeet Sep 02 '16 at 05:07
  • @JonSkeet I found the solution. Your original code was wrong with the static identifier. You cannot compile it if you need to call other class. It works without static. – Appalachian Math Sep 02 '16 at 22:52
  • @AppalachianMath: The code in my answer compiles fine as it is. I don't know what you mean by "with the static identifier" or "you cannot compile it if you need to call other class", but it's fine. I've just compiled it, just now, with simple copy/paste/compile. – Jon Skeet Sep 03 '16 at 06:04
  • @JonSkeet does the java queue support changing the contents of the queue without having to re-insert them into the queue? i.e. a = q.pop(); b = a.neighbours[0]; b.priority = 100 (where a and b are in the q) -- this is pseudocode not real java – Har Nov 15 '16 at 00:13
  • @Har: That's not changing the contents of the queue, because the contents of the queue is just a reference. You can change the data within an object that the contents of the queue refer to, yes. (Assuming the type allows you to, of course.) That's not queue-specific - that's just how reference types work. – Jon Skeet Nov 15 '16 at 07:21
  • @JonSkeet it does not seem to work, if I change the data which the queue refers to, then the queue does not reorder the elements, is there a way to achieve this without having to remove and add them? i.e. if a with a value of 1 is put in the queue, if I change the value of a to be 90 then a will still be the item which is removed first. p.s. I am not using an integer I am actually using my own made up class with an integer in it. – Har Nov 15 '16 at 10:15
  • Okay I found a related question -- http://stackoverflow.com/questions/6952660/java-priority-queue-reordering-when-editing-elements which gives me an answer – Har Nov 15 '16 at 10:20
  • nice way of explanation!! – spandey Jul 23 '18 at 07:04
99

Java 8 solution

We can use lambda expression or method reference introduced in Java 8. In case we have some String values stored in the Priority Queue (having capacity 5) we can provide inline comparator (based on length of String) :

Using lambda expression

PriorityQueue<String> pq=
                    new PriorityQueue<String>(5,(a,b) -> a.length() - b.length());

Using Method reference

PriorityQueue<String> pq=
                new PriorityQueue<String>(5, Comparator.comparing(String::length));

Then we can use any of them as:

public static void main(String[] args) {
        PriorityQueue<String> pq=
                new PriorityQueue<String>(5, (a,b) -> a.length() - b.length());
       // or pq = new PriorityQueue<String>(5, Comparator.comparing(String::length));
        pq.add("Apple");
        pq.add("PineApple");
        pq.add("Custard Apple");
        while (pq.size() != 0)
        {
            System.out.println(pq.remove());
        }
    }

This will print:

Apple
PineApple
Custard Apple

To reverse the order (to change it to max-priority queue) simply change the order in inline comparator or use reversed as:

PriorityQueue<String> pq = new PriorityQueue<String>(5, 
                             Comparator.comparing(String::length).reversed());

We can also use Collections.reverseOrder:

PriorityQueue<Integer> pqInt = new PriorityQueue<>(10, Collections.reverseOrder());
PriorityQueue<String> pq = new PriorityQueue<String>(5, 
                Collections.reverseOrder(Comparator.comparing(String::length))

So we can see that Collections.reverseOrder is overloaded to take comparator which can be useful for custom objects. The reversed actually uses Collections.reverseOrder:

default Comparator<T> reversed() {
    return Collections.reverseOrder(this);
}

offer() vs add()

As per the doc

The offer method inserts an element if possible, otherwise returning false. This differs from the Collection.add method, which can fail to add an element only by throwing an unchecked exception. The offer method is designed for use when failure is a normal, rather than exceptional occurrence, for example, in fixed-capacity (or "bounded") queues.

When using a capacity-restricted queue, offer() is generally preferable to add(), which can fail to insert an element only by throwing an exception. And PriorityQueue is an unbounded priority queue based on a priority heap.

akhil_mittal
  • 23,309
  • 7
  • 96
  • 95
26

Just pass appropriate Comparator to the constructor:

PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

The only difference between offer and add is the interface they belong to. offer belongs to Queue<E>, whereas add is originally seen in Collection<E> interface. Apart from that both methods do exactly the same thing - insert the specified element into priority queue.

dragonfly
  • 1,590
  • 10
  • 14
  • 8
    Specifically, add() throws an exception if capacity restrictions prevent the item from being added to the queue while offer returns false. Since PriorityQueues do not have a maximum capacity, the difference is moot. – James Mar 25 '09 at 19:58
  • That is very clear distinction between add() and offer().. And add() was needed to be implemented anyway! – whitehat Feb 02 '12 at 06:08
19

from Queue API:

The offer method inserts an element if possible, otherwise returning false. This differs from the Collection.add method, which can fail to add an element only by throwing an unchecked exception. The offer method is designed for use when failure is a normal, rather than exceptional occurrence, for example, in fixed-capacity (or "bounded") queues.

Svish
  • 152,914
  • 173
  • 462
  • 620
Peter
  • 5,728
  • 20
  • 23
15

no different, as declare in javadoc:

public boolean add(E e) {
    return offer(e);
}
d1ck50n
  • 1,331
  • 2
  • 16
  • 20
13

Pass it a Comparator. Fill in your desired type in place of T

Using lambdas (Java 8+):

int initialCapacity = 10;
PriorityQueue<T> pq = new PriorityQueue<>(initialCapacity, (e1, e2) -> { return e1.compareTo(e2); });

Classic way, using anonymous class:

int initialCapacity = 10;
PriorityQueue<T> pq = new PriorityQueue<>(initialCapacity, new Comparator<T> () {

    @Override
    public int compare(T e1, T e2) {
        return e1.compareTo(e2);
    }

});

To sort in reverse order, simply swap e1, e2.

James Wierzba
  • 16,176
  • 14
  • 79
  • 120
6

Just to answer the add() vs offer() question (since the other one is perfectly answered imo, and this might not be):

According to JavaDoc on interface Queue, "The offer method inserts an element if possible, otherwise returning false. This differs from the Collection.add method, which can fail to add an element only by throwing an unchecked exception. The offer method is designed for use when failure is a normal, rather than exceptional occurrence, for example, in fixed-capacity (or "bounded") queues."

That means if you can add the element (which should always be the case in a PriorityQueue), they work exactly the same. But if you can't add the element, offer() will give you a nice and pretty false return, while add() throws a nasty unchecked exception that you don't want in your code. If failure to add means code is working as intended and/or it is something you'll check normally, use offer(). If failure to add means something is broken, use add() and handle the resulting exception thrown according to the Collection interface's specifications.

They are both implemented this way to fullfill the contract on the Queue interface that specifies offer() fails by returning a false (method preferred in capacity-restricted queues) and also maintain the contract on the Collection interface that specifies add() always fails by throwing an exception.

Anyway, hope that clarifies at least that part of the question.

Blueriver
  • 3,212
  • 3
  • 16
  • 33
6

In here, We can define user defined comparator:

Below code :

 import java.util.*;
 import java.util.Collections;
 import java.util.Comparator; 


 class Checker implements Comparator<String>
 {
    public int compare(String str1, String str2)
    {
        if (str1.length() < str2.length()) return -1;
        else                               return 1;
    }
 }


class Main
{  
   public static void main(String args[])
    {  
      PriorityQueue<String> queue=new PriorityQueue<String>(5, new Checker());  
      queue.add("india");  
      queue.add("bangladesh");  
      queue.add("pakistan");  
 
      while (queue.size() != 0)
      {
         System.out.printf("%s\n",queue.remove());
      }
   }  
}  

Output :

   india                                               
   pakistan                                         
   bangladesh

Difference between the offer and add methods : link

Community
  • 1
  • 1
rashedcs
  • 3,588
  • 2
  • 39
  • 40
4

As an alternative to using Comparator, you can also have the class you're using in your PriorityQueue implement Comparable (and correspondingly override the compareTo method).

Note that it's generally best to only use Comparable instead of Comparator if that ordering is the intuitive ordering of the object - if, for example, you have a use case to sort Person objects by age, it's probably best to just use Comparator instead.

import java.lang.Comparable;
import java.util.PriorityQueue;

class Test
{
    public static void main(String[] args)
    {
        PriorityQueue<MyClass> queue = new PriorityQueue<MyClass>();
        queue.add(new MyClass(2, "short"));
        queue.add(new MyClass(2, "very long indeed"));
        queue.add(new MyClass(1, "medium"));
        queue.add(new MyClass(1, "very long indeed"));
        queue.add(new MyClass(2, "medium"));
        queue.add(new MyClass(1, "short"));
        while (queue.size() != 0)
            System.out.println(queue.remove());
    }
}
class MyClass implements Comparable<MyClass>
{
    int sortFirst;
    String sortByLength;

    public MyClass(int sortFirst, String sortByLength)
    {
        this.sortFirst = sortFirst;
        this.sortByLength = sortByLength;
    }

    @Override
    public int compareTo(MyClass other)
    {
        if (sortFirst != other.sortFirst)
            return Integer.compare(sortFirst, other.sortFirst);
        else
            return Integer.compare(sortByLength.length(), other.sortByLength.length());
    }

    public String toString()
    {
        return sortFirst + ", " + sortByLength;
    }
}

Output:

1, short
1, medium
1, very long indeed
2, short
2, medium
2, very long indeed
Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
3

I was also wondering about print order. Consider this case, for example:

For a priority queue:

PriorityQueue<String> pq3 = new PriorityQueue<String>();

This code:

pq3.offer("a");
pq3.offer("A");

may print differently than:

String[] sa = {"a", "A"}; 
for(String s : sa)   
   pq3.offer(s);

I found the answer from a discussion on another forum, where a user said, "the offer()/add() methods only insert the element into the queue. If you want a predictable order you should use peek/poll which return the head of the queue."

indiv
  • 17,306
  • 6
  • 61
  • 82
joserey
  • 31
  • 1
1

Priority Queue has some priority assigned to each element, The element with Highest priority appears at the Top Of Queue. Now, It depends on you how you want priority assigned to each of the elements. If you don't, the Java will do it the default way. The element with the least value is assigned the highest priority and thus is removed from the queue first. If there are several elements with the same highest priority, the tie is broken arbitrarily. You can also specify an ordering using Comparator in the constructor PriorityQueue(initialCapacity, comparator)

Example Code:

PriorityQueue<String> queue1 = new PriorityQueue<>();
queue1.offer("Oklahoma");
queue1.offer("Indiana");
queue1.offer("Georgia");
queue1.offer("Texas");
System.out.println("Priority queue using Comparable:");
while (queue1.size() > 0) {
    System.out.print(queue1.remove() + " ");
}
PriorityQueue<String> queue2 = new PriorityQueue(4, Collections.reverseOrder());
queue2.offer("Oklahoma");
queue2.offer("Indiana");
queue2.offer("Georgia");
queue2.offer("Texas");
System.out.println("\nPriority queue using Comparator:");
while (queue2.size() > 0) {
    System.out.print(queue2.remove() + " ");
}

Output:

Priority queue using Comparable:
Georgia Indiana Oklahoma Texas 
Priority queue using Comparator:
Texas Oklahoma Indiana Georgia 

Else, You can also define Custom Comparator:

import java.util.Comparator;

public class StringLengthComparator implements Comparator<String>
{
    @Override
    public int compare(String x, String y)
    {
        //Your Own Logic
    }
}
devDeejay
  • 5,494
  • 2
  • 27
  • 38
1

Here is the simple example which you can use for initial learning:

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

public class PQExample {

    public static void main(String[] args) {
        //PriorityQueue with Comparator
        Queue<Customer> cpq = new PriorityQueue<>(7, idComp);
        addToQueue(cpq);
        pollFromQueue(cpq);
    }

    public static Comparator<Customer> idComp = new Comparator<Customer>(){

        @Override
        public int compare(Customer o1, Customer o2) {
            return (int) (o1.getId() - o2.getId());
        }

    };

    //utility method to add random data to Queue
    private static void addToQueue(Queue<Customer> cq){
        Random rand = new Random();
        for(int i=0;i<7;i++){
            int id = rand.nextInt(100);
            cq.add(new Customer(id, "KV"+id));
        }
    }


    private static void pollFromQueue(Queue<Customer> cq){
        while(true){
            Customer c = cq.poll();
            if(c == null) break;
            System.out.println("Customer Polled : "+c.getId() + " "+ c.getName());
        }
    }

}
KayV
  • 12,987
  • 11
  • 98
  • 148
0
public class Graph {
  public Set<Node> nodes = new HashSet<Node>();
}

public class Node {
  
  public String name;
  public List<Node> shortestPath = new ArrayList<Node>();
  Map<Node, Integer> adjMap = new HashMap<Node, Integer>();
  public Integer weight = Integer.MAX_VALUE;
}

PriorityQueue<Node> unQueriedNodes =
        new PriorityQueue<Node>(graph.nodes.size(), Comparator.comparingInt(o -> o.weight));
prashant.kr.mod
  • 1,178
  • 13
  • 28