How to Get Maximum Value From A Priority queue in Java

1. What Is a Priority Queue in Java
2. the Use of Priority Queue in Java
3. Use the PriorityQueue Class in the java.util Package to Get Max Priority Queue in Java
4. Use a Comparator With a Custom Data Structure to Get Max Priority Queue in Java
5. Use a Comparator to Get Maximum Values From a Priority Queue in Java
6. Conclusion

Priority Queue is a data structure in Java in which elements are present according to their natural state, not according to the first-in-first-out order. The elements can also be sorted according to a comparator used in a priority queue.

In Java, a priority queue is a data structure that allows elements to be inserted with an associated priority and retrieved based on that priority. There are various ways to implement a max priority queue in Java, each with its advantages and trade-offs.

This tutorial demonstrates the use of a priority queue and how to get maximum values from a priority queue.

What Is a Priority Queue in Java

In Java, a priority queue is a data structure that stores elements based on their priorities. Unlike a regular queue, where elements are retrieved in the order they were inserted (FIFO - First In, First Out), a priority queue retrieves elements based on their priority.

Elements with higher priority are dequeued (retrieved for processing or removal) before elements with lower priority.

Java’s PriorityQueue class implements a priority queue based on a priority heap. By default, it is a min-heap, meaning the element with the minimum value as per its natural ordering (or a provided comparator) is dequeued first.

However, you can modify it to act as a max priority queue by using a custom comparator.

Key Characteristics of PriorityQueue in Java:

• Priority Ordering: Elements are stored based on their priority, determined by either their natural ordering (if the elements implement the Comparable interface) or a provided custom comparator.
• Heap Structure: Internally, it uses a priority heap, usually a binary heap, to organize elements for efficient retrieval.
• Efficient Operations: Insertion and removal of elements are optimized for quick access to the highest or lowest priority element.
• Not Thread-Safe: The PriorityQueue class is not thread-safe for concurrent operations. For concurrent applications, consider using PriorityBlockingQueue from the java.util.concurrent package.

Common Operations With PriorityQueue:

• add(E e): Inserts an element into the priority queue.
• remove(): Retrieves and removes the highest (or lowest) priority element.
• peek(): Retrieves the highest (or lowest) priority element without removing it.
• size(), isEmpty(): Methods to check the size and emptiness of the priority queue.
• clear(): Removes all elements from the priority queue.

the Use of Priority Queue in Java

As mentioned above, the elements are present in a priority queue in their natural state. Let’s see an example.

This code demonstrates the usage of a PriorityQueue in Java to store strings, add elements, retrieve the head element, and print all elements using an iterator.

package delftstack;
import java.util.*;

public class Priority_Queue {
  public static void main(String args[]) {
    PriorityQueue<String> delftstack_queue = new PriorityQueue<String>();
    // Add the values to the priority queue
    delftstack_queue.add("delftstack3");
    delftstack_queue.add("delftstack2");
    delftstack_queue.add("delftstack1");
    delftstack_queue.add("delftstack4");
    delftstack_queue.add("delftstack5");
    delftstack_queue.add("delftstack6");
    // head of the PriorityQueue
    System.out.println(
        "Head of the PriorityQueue, The minimum value: " + delftstack_queue.element());
    // All Elements of the Priority Queue
    System.out.println("All PriorityQueue Elements:");
    Iterator demo_iterator = delftstack_queue.iterator();
    while (demo_iterator.hasNext()) {
      System.out.print(demo_iterator.next() + " ");
    }
  }
}

The above code will first print the head of the priority queue, which will be the minimum value, and print all the elements.

Output:

Head of the PriorityQueue, The minimum value: delftstack1

All PriorityQueue Elements:
delftstack1 delftstack3 delftstack2 delftstack4 delftstack5 delftstack6

As we can see, the head is the minimum value. Next, we demonstrate how to get maximum values from a priority queue in Java.

Use the PriorityQueue Class in the java.util Package to Get Max Priority Queue in Java

The PriorityQueue class in Java’s java.util package is a commonly used implementation for a priority queue. By default, it is a min-heap, but it can be utilized as a max priority queue by providing a custom comparator.

Example Code:

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

public class MaxPriorityQueueExample1 {
  public static void main(String[] args) {
    // Creating a max priority queue with a custom comparator
    PriorityQueue<Integer> maxPriorityQueue = new PriorityQueue<>(Comparator.reverseOrder());

    // Adding elements to the max priority queue
    maxPriorityQueue.add(20);
    maxPriorityQueue.add(10);
    maxPriorityQueue.add(30);

    // Removing elements in max priority order
    while (!maxPriorityQueue.isEmpty()) {
      System.out.println(maxPriorityQueue.poll());
    }
  }
}

Output:

30
20
10

In this code, the PriorityQueue is instantiated with a custom comparator, Comparator.reverseOrder(), which reverses the natural ordering of elements to achieve a max priority queue. Elements are added using the add() method.

The poll() method is used to retrieve and remove the highest priority (maximum) element until the queue is empty.

Use a Comparator With a Custom Data Structure to Get Max Priority Queue in Java

Another approach is to create a custom data structure and use a comparator to build a maximum priority queue.

Example Code:

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

class MaxPriorityQueueItem {
  int value;

  public MaxPriorityQueueItem(int value) {
    this.value = value;
  }
}

public class MaxPriorityQueueExample2 {
  public static void main(String[] args) {
    // Creating a max priority queue with a custom comparator
    PriorityQueue<MaxPriorityQueueItem> maxPriorityQueue =
        new PriorityQueue<>(Comparator.comparingInt(item -> - item.value));

    // Adding elements to the max priority queue
    maxPriorityQueue.add(new MaxPriorityQueueItem(20));
    maxPriorityQueue.add(new MaxPriorityQueueItem(10));
    maxPriorityQueue.add(new MaxPriorityQueueItem(30));

    // Removing elements in max priority order
    while (!maxPriorityQueue.isEmpty()) {
      System.out.println(maxPriorityQueue.poll().value);
    }
  }
}

Output:

30
20
10

A custom data structure, MaxPriorityQueueItem, is created to hold the value with which priority is associated.

PriorityQueue is instantiated with a comparator using the Comparator.comparingInt() method to sort based on the value in reverse order (-item.value). Elements are added to the priority queue as instances of MaxPriorityQueueItem.

The poll() method is used to retrieve and remove the highest priority (maximum value) element until the queue is empty.

Use a Comparator to Get Maximum Values From a Priority Queue in Java

To get the maximum values from a priority queue, we should first sort them according to descending order. To sort elements in descending order, we can use a comparator to get the maximum value from the priority queue in Java.

The code below sorts the priority queue in descending order to get the maximum value.

package delftstack;
import java.util.*;

public class Priority_Queue {
  public static void main(String args[]) {
    // Initialize a priority queue with a custom comparator to sort the queue in descending order.
    PriorityQueue<Integer> demo_priority_queue =
        new PriorityQueue<Integer>(new Comparator<Integer>() {
          public int compare(Integer left_hand_side, Integer right_hand_side) {
            if (left_hand_side < right_hand_side)
              return +1;
            if (left_hand_side.equals(right_hand_side))
              return 0;
            return -1;
          }
        });
    // add elements
    demo_priority_queue.add(11);
    demo_priority_queue.add(7);
    demo_priority_queue.add(3);
    demo_priority_queue.add(18);
    demo_priority_queue.add(10);
    demo_priority_queue.add(2);
    demo_priority_queue.add(17);
    demo_priority_queue.add(20);
    demo_priority_queue.add(5);
    // display the max PriorityQueue
    System.out.println("The Priority Queue elements in max to min order:");
    Integer val = null;
    while ((val = demo_priority_queue.poll()) != null) {
      System.out.print(val + " ");
    }
  }
}

Output:

The Priority Queue elements in max to min order:
20 18 17 11 10 7 5 3 2

This code initializes a PriorityQueue named demo_priority_queue to store integers in descending order using a custom comparator. The comparator, defined anonymously within the PriorityQueue instantiation, compares integers.

The code then adds several integers to the queue. Finally, it prints the elements in descending order (from max to min) by repeatedly polling the PriorityQueue until it’s empty and displaying each polled element.

The comparator ensures the PriorityQueue organizes elements based on this custom descending order, resulting in the output showing integers in descending sequence.

Here are more ways to sort the priority queue in descending order to get the maximum value.

Example:

package delftstack;
import java.util.*;

public class Priority_Queue {
  public static void main(String args[]) {
    // Initialize a priority queue with a custom comparator to sort the queue in descending order.
    PriorityQueue<Integer> demo_priority_queue =
        new PriorityQueue<Integer>(Collections.reverseOrder());
    // PriorityQueue<Integer> demo_priority_queue = new PriorityQueue<Integer>((a,b) -> b - a);
    // PriorityQueue<Integer> demo_priority_queue = new PriorityQueue<Integer>((a,b) ->
    // b.compareTo(a)); add elements
    demo_priority_queue.add(11);
    demo_priority_queue.add(7);
    demo_priority_queue.add(3);
    demo_priority_queue.add(18);
    demo_priority_queue.add(10);
    demo_priority_queue.add(2);
    demo_priority_queue.add(17);
    demo_priority_queue.add(20);
    demo_priority_queue.add(5);
    // display the max PriorityQueue
    System.out.println("The Priority Queue elements in max to min order:");
    Integer val = null;
    while ((val = demo_priority_queue.poll()) != null) {
      System.out.print(val + " ");
    }
  }
}

Output:

The Priority Queue elements in max to min order:
20 18 17 11 10 7 5 3 2

Collections.reverseOrder() is a built-in comparator to sort the priority queue in descending order. The other two comparators in the comments also perform the same operation, and we can use any of them.

The difference between the manual comparator and built-in is that we can also sort the string with built-in comparators and get the maximum value like the code snippet below.

Example:

package delftstack;
import java.util.*;

public class Priority_Queue {
  public static void main(String args[]) {
    PriorityQueue<String> delftstack_queue = new PriorityQueue<String>(Collections.reverseOrder());
    // Add the values to the priority queue
    delftstack_queue.add("delftstack3");
    delftstack_queue.add("delftstack2");
    delftstack_queue.add("delftstack1");
    delftstack_queue.add("delftstack4");
    delftstack_queue.add("delftstack5");
    delftstack_queue.add("delftstack6");
    // head of the PriorityQueue
    System.out.println(
        "Head of the PriorityQueue, The maximum value: " + delftstack_queue.element());
    // All Elements of the Priority Queue
    System.out.println("All PriorityQueue Elements:");
    Iterator demo_iterator = delftstack_queue.iterator();
    while (demo_iterator.hasNext()) {
      System.out.print(demo_iterator.next() + " ");
    }
  }
}

Output:

Head of the PriorityQueue, The maximum value: delftstack6
All PriorityQueue Elements:
delftstack6 delftstack4 delftstack5 delftstack2 delftstack3 delftstack1

This code creates a PriorityQueue named delftstack_queue to store strings with a custom configuration. The priority queue is initialized with the Collections.reverseOrder() comparator, altering its behavior to act as a max priority queue.

Six strings are added to the queue. The code then retrieves and prints the head (maximum value) of the PriorityQueue using delftstack_queue.element() and displays all elements in the PriorityQueue by iterating through it using an iterator.

This code showcases how to create a max priority queue in Java and perform basic operations like insertion and retrieval of elements in descending order of priority.

Conclusion

In conclusion, a priority queue in Java offers a structured way to manage elements based on their priority, deviating from the typical first-in-first-out order. This data structure enables sorting based on priority using either the natural order of elements or a custom comparator.

Java’s PriorityQueue class, by default, functions as a min-heap, but its behavior can be altered to create a max priority queue by using a reverse comparator or a custom comparator to arrange elements in descending priority. This article covered the fundamental characteristics of a PriorityQueue in Java, including its heap structure, operations, and thread safety considerations.

It also provided various implementations demonstrating how to obtain maximum values from a priority queue using built-in or custom comparators. Whether managing integers, strings, or custom data structures, Java’s priority queue functionality facilitates efficient sorting and retrieval based on priority criteria, making it a versatile tool for diverse programming needs.