Change priorityQueue to max priorityqueue

Question

I have priority queue in Java of Integers    PriorityQueue lt Integer gt  pq  new PriorityQueue lt Integer gt       When I call pq poll   I get the minimum element   Question  how to change the code to get the maximum element

User · Answer

PriorityQueue lt Integer gt  pq   new PriorityQueue lt Integer gt      new Comparator lt Integer gt           public int compare Integer a  Integer b           return b - a

User · Answer

Here is a sample Max-Heap in Java     PriorityQueue lt Integer gt  pq1  new PriorityQueue lt Integer gt  10  new Comparator lt Integer gt      public int compare Integer x  Integer y    if  x  lt  y  return 1  if  x  gt  y  return -1  return 0        pq1 add 5   pq1 add 10   pq1 add -1   System out println  Peek    pq1 peek       The output will be 10

User · Answer

You can try something like   PriorityQueue lt Integer gt  pq   new PriorityQueue lt  gt   x  y  - gt  -1   Integer compare x  y      Which works for any other base comparison function you might have

User · Answer

Using lamda  just multiple the result with -1 to get max priority queue  PriorityQueue lt  gt  q   new PriorityQueue lt Integer gt                           a b  - gt   -1   Integer compare a  b

User · Answer

This can be achieved by the below code in Java 8 which has introduced a constructor which only takes a comparator   PriorityQueue lt Integer gt  maxPriorityQ   new PriorityQueue lt Integer gt  Collections reverseOrder

User · Answer

In Java 8  you can create a max priority queue via one of these methods    Method 1    PriorityQueue lt Integer gt  maxPQ   new PriorityQueue lt  gt  Collections reverseOrder        Method 2    PriorityQueue lt Integer gt  maxPQ   new PriorityQueue lt  gt   a b  - gt  b - a      Method 3    PriorityQueue lt Integer gt  maxPQ   new PriorityQueue lt  gt   a b  - gt  b compareTo a

User · Answer

I just ran a Monte-Carlo simulation on both comparators on double heap sort min max and they both came to the same result     These are the max comparators I have used    A  Collections built-in comparator   PriorityQueue lt Integer gt  heapLow   new PriorityQueue lt Integer gt  Collections reverseOrder        B   Custom comparator   PriorityQueue lt Integer gt  heapLow   new PriorityQueue lt Integer gt  new Comparator lt Integer gt          int compare Integer lhs  Integer rhs            if  rhs  gt  lhs  return  1          if  rhs  lt  lhs  return -1          return 0

User · Answer

PriorityQueue lt Integer gt  lowers   new PriorityQueue lt  gt   o1  o2  - gt  -1   o1 compareTo o2

User · Answer

This can be achieved by using   PriorityQueue lt Integer gt  pq   new PriorityQueue lt Integer gt  Collections reverseOrder

User · Answer

You can try pushing elements with reverse sign  Eg  To add a 2  amp  b 5 and then poll b 5   PriorityQueue lt Integer gt   pq   new PriorityQueue lt  gt     pq add -a   pq add -b   System out print -pq poll       Once you poll the head of the queue  reverse the sign for your usage  This will print 5  larger element   Can be used in naive implementations  Definitely not a reliable fix  I don t recommend it

User · Answer

You can provide a custom Comparator object that ranks elements in the reverse order   PriorityQueue lt Integer gt  pq   new PriorityQueue lt Integer gt  defaultSize  new Comparator lt Integer gt          public int compare Integer lhs  Integer rhs            if  lhs  lt  rhs  return  1          if  lhs equals rhs   return 0          return -1              Now  the priority queue will reverse all its comparisons  so you will get the maximum element rather than the minimum element   Hope this helps

User · Answer

The elements of the priority queue are ordered according to their natural ordering  or by a Comparator provided at queue construction time   The Comparator should override the compare method   int compare T o1  T o2    Default compare method returns a negative integer  zero  or a positive integer as the first argument is less than  equal to  or greater than the second   The Default PriorityQueue provided by Java is Min-Heap  If you want a max heap following is the code  public class Sample       public static void main String   args            PriorityQueue lt Integer gt  q   new PriorityQueue lt Integer gt  new Comparator lt Integer gt                   public int compare Integer lhs  Integer rhs                    if lhs lt rhs  return  1                  if lhs gt rhs  return -1                  return 0                                    q add 13           q add 4  q add 14  q add -4  q add 1           while   q isEmpty                  System out println q poll                          Reference  https   docs oracle com javase 7 docs api java util PriorityQueue html comparator

User · Answer

You can use MinMaxPriorityQueue  it s a part of the Guava library   here s the documentation  Instead of poll    you need to call the pollLast   method

User · Answer

We can do this by creating our CustomComparator class that implements Comparator interface and overriding its compare method  Below is the code for the same   import java util PriorityQueue  import java util Comparator  public class Main       public static void main String   args            PriorityQueue lt Integer gt  nums   new PriorityQueue lt  gt  new CustomComparator             nums offer 21           nums offer 1           nums offer 8           nums offer 2           nums offer -4           System out println nums peek             class CustomComparator implements Comparator lt Integer gt        Override     public int compare Integer n1  Integer n2           int val   n1 compareTo n2           if val  gt  0             return -1          else if val  lt  0              return 1          else             return 0

User · Answer

You can use lambda expression since Java 8   The following code will print 10  the larger      There is overflow problem when using simple lambda as comparator  as pointed out by                PriorityQueue lt Integer gt  pq   new PriorityQueue lt  gt   x  y  - gt  y - x    PriorityQueue lt Integer gt  pq  new PriorityQueue lt  gt   x  y  - gt  Integer compare y  x     pq add 10   pq add 5   System out println pq peek       The lambda function will take two Integers as input parameters  subtract them from each other  and return the arithmetic result  The lambda function implements the Functional Interface  Comparator lt T gt    This is used in place  as opposed to an anonymous class or a discrete implementation

User · Answer

How about like this   PriorityQueue lt Integer gt  queue   new PriorityQueue lt  gt  10  Collections reverseOrder     queue offer 1   queue offer 2   queue offer 3          Integer val   null  while   val   queue poll       null        System out println val       The Collections reverseOrder   provides a Comparator that would sort the elements in the PriorityQueue in a the oposite order to their natural order in this case

User · Answer

Change PriorityQueue to MAX PriorityQueue Method 1   Queue pq   new PriorityQueue lt   Collections reverseOrder     Method 2   Queue pq1   new PriorityQueue lt    a  b  -  b - a   Let s look at few Examples   public class Example1       public static void main String   args             List lt Integer gt  ints   Arrays asList 222  555  666  333  111  888  777  444           Queue lt Integer gt  pq   new PriorityQueue lt  gt  Collections reverseOrder             pq addAll ints           System out println  Priority Queue   gt      pq           System out println  Max element in the list   gt      pq peek             System out println                                       another way         Queue lt Integer gt  pq1   new PriorityQueue lt  gt   a  b  - gt  b - a           pq1 addAll ints           System out println  Priority Queue   gt      pq1           System out println  Max element in the list   gt      pq1 peek                OUTPUT           Priority Queue   gt   888  444  777  333  111  555  666  222            Max element in the list   gt  888                                             Priority Queue   gt   888  444  777  333  111  555  666  222             Max element in the list   gt  888                          Let s take a famous interview  Problem   Kth Largest Element in an Array using PriorityQueue  public class KthLargestElement 1      public static void main String   args             List lt Integer gt  ints   Arrays asList 222  555  666  333  111  888  777  444           int k   3          Queue lt Integer gt  pq   new PriorityQueue lt  gt  Collections reverseOrder             pq addAll ints           System out println  Priority Queue   gt      pq           System out println  Max element in the list   gt      pq peek             while  --k  gt  0                pq poll                 while         System out println  Third largest   gt      pq peek         Priority Queue   gt   888  444  777  333  111  555  666  222  Max element in the list   gt  888 Third largest   gt  666                Another way     public class KthLargestElement 2       public static void main String   args            List lt Integer gt  ints   Arrays asList 222  555  666  333  111  888  777  444           int k   3           Queue lt Integer gt  pq1   new PriorityQueue lt  gt   a  b  - gt  b - a           pq1 addAll ints           System out println  Priority Queue   gt      pq1           System out println  Max element in the list   gt      pq1 peek             while  --k  gt  0                pq1 poll                 while         System out println  Third largest   gt      pq1 peek                          Priority Queue   gt   888  444  777  333  111  555  666  222             Max element in the list   gt  888            Third largest   gt  666                        As we can see  both are giving the same result

[java] Change priorityQueue to max priorityqueue

Examples related to java

Examples related to collections

Examples related to priority-queue