How do I use a PriorityQueue

Question

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

User · Answer

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

User · Answer

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 lt MyClass gt  queue   new PriorityQueue lt MyClass gt             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 lt MyClass gt        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

User · Answer

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 lt String gt  pq                      new PriorityQueue lt String gt  5  a b  - gt  a length   - b length       Using Method reference  PriorityQueue lt String gt  pq                  new PriorityQueue lt String gt  5  Comparator comparing String  length      Then we can use any of them as   public static void main String   args            PriorityQueue lt String gt  pq                  new PriorityQueue lt String gt  5   a b  - gt  a length   - b length               or pq   new PriorityQueue lt String gt  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 lt String gt  pq   new PriorityQueue lt String gt  5                                Comparator comparing String  length  reversed       We can also use Collections reverseOrder   PriorityQueue lt Integer gt  pqInt   new PriorityQueue lt  gt  10  Collections reverseOrder     PriorityQueue lt String gt  pq   new PriorityQueue lt String gt  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 lt T gt  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

User · Answer

Use the constructor overload which takes a Comparator lt   super E gt  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 lt String gt  comparator   new StringLengthComparator            PriorityQueue lt String gt  queue   new PriorityQueue lt String gt  10  comparator           queue add  quot short quot            queue add  quot very long indeed quot            queue add  quot medium quot            while  queue size      0                System out println queue remove                           StringLengthComparator java import java util Comparator   public class StringLengthComparator implements Comparator lt String gt         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    lt  y length                  return -1                    if  x length    gt  y length                  return 1                    return 0           Here is the output   short medium very long indeed

User · Answer

I was also wondering about print order   Consider this case  for example   For a priority queue   PriorityQueue lt String gt  pq3   new PriorityQueue lt String gt       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

User · Answer

Just pass appropriate Comparator to the constructor   PriorityQueue int initialCapacity  Comparator lt   super E gt  comparator    The only difference between offer and add is the interface they belong to  offer belongs to Queue lt E gt   whereas add is originally seen in Collection lt E gt  interface  Apart from that both methods do exactly the same thing - insert the specified element into priority queue

User · Answer

Pass it a Comparator  Fill in your desired type in place of T  Using lambdas  Java 8     int initialCapacity   10  PriorityQueue lt T gt  pq   new PriorityQueue lt  gt  initialCapacity   e1  e2  - gt    return e1 compareTo e2         Classic way  using anonymous class   int initialCapacity   10  PriorityQueue lt T gt  pq   new PriorityQueue lt  gt  initialCapacity  new Comparator lt T gt             Override     public int compare T e1  T e2            return e1 compareTo e2                To sort in reverse order  simply swap e1  e2

User · Answer

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 lt Customer gt  cpq   new PriorityQueue lt  gt  7  idComp           addToQueue cpq           pollFromQueue cpq              public static Comparator lt Customer gt  idComp   new Comparator lt Customer gt               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 lt Customer gt  cq           Random rand   new Random            for int i 0 i lt 7 i                 int id   rand nextInt 100               cq add new Customer id   KV  id                          private static void pollFromQueue Queue lt Customer gt  cq           while true               Customer c   cq poll                if c    null  break              System out println  Customer Polled     c getId          c getName

User · Answer

no different  as declare in javadoc   public boolean add E e        return offer e

User · Answer

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 lt String gt         public int compare String str1  String str2                if  str1 length    lt  str2 length    return -1          else                               return 1             class Main        public static void main String args                  PriorityQueue lt String gt  queue new PriorityQueue lt String gt  5  new Checker             queue add  quot india quot            queue add  quot bangladesh quot            queue add  quot pakistan quot              while  queue size      0                   System out printf  quot  s n quot  queue remove                          Output      india                                                   pakistan                                             bangladesh   Difference between the offer and add methods   link

User · Answer

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 lt String gt  queue1   new PriorityQueue lt  gt     queue1 offer  Oklahoma    queue1 offer  Indiana    queue1 offer  Georgia    queue1 offer  Texas    System out println  Priority queue using Comparable     while  queue1 size    gt  0        System out print queue1 remove             PriorityQueue lt String gt  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    gt  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 lt String gt         Override     public int compare String x  String y                  Your Own Logic

User · Answer

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

[java] How do I use a PriorityQueue?

Examples related to java

Examples related to priority-queue