Prerequisite: PriorityQueue, Pair
javafx.util.Pair<K,V> class in Java is the combination of two different objects called Key and Value. It basically provides a way to store pair of two heterogeneous data items.
Pair <K, V> pair = new Pair<>(K key, V value)
PriorityQueue<E> is like a normal Queue in which the elements are ordered according to the natural ordering and comparator or lambda expression passed in the constructor.
Mostly used Constructors of Priority Queue
- PriorityQueue<E> pq = new PriorityQueue<E>();
- PriorityQueue<E> pq = new PriorityQueue<E>(Collection<E> c);
- PriorityQueue<E> pq = new PriorityQueue<E>(int initialCapacity);
- PriorityQueue<E> pq = new PriorityQueue(int initialCapacity, Comparator<E> comparator);
PriorityQueue of Pair<K, V> Syntax
- PriorityQueue<Pair<K, V>> = new PriorityQueue<>(initialCapacity, Comparator.comparing(Pair :: getKey))
- PriorityQueue<Pair<K, V>> = new PriorityQueue<>(Comparator.comparing(Pair :: getKey))
Note:
- Since Pair<K, V> class was the part of JavaFX and JavaFX was removed from JDK since JDK 11. So Pairs can be used till JDK 10.
- The below source code might not run on most of the online IDEs, better to try it on offline software.
PriorityQueue Implementing Min Heap Based on Keys of Pair
1. Using Lambda Expression:
Java
import java.util.*;import java.io.*;import javafx.util.Pair; class GFG { public static void main(String[] args) { // Priority Queue implementing min heap of Pairs // Creating instance of PriorityQueue by passing // Lambda expression as a constructor parameter. PriorityQueue<Pair<Integer, String>> pq = new PriorityQueue<>((a, b) -> a.getKey() - b.getKey()); // Adding objects of Pair<K, V> class by passing // keys and values as parameter in Pair constructor pq.add(new Pair<>(8, "fox")); pq.add(new Pair<>(4, "quick")); pq.add(new Pair<>(2, "the")); pq.add(new Pair<>(6, "brown")); // Printing min heap based on the priority while(!pq.isEmpty()){ System.out.print(pq.remove() +" "); } }} |
Output:
2=the 4=quick 6=brown 8=fox
2. Using Comparator : Comparator.comparing()
Java
import java.io.*;import java.util.*;import javafx.util.Pair; class GFG { public static void main(String[] args) { // Priority Queue implementing min heap of Pairs // Creating instance of PriorityQueue by passing // Comparator as a constructor parameter PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(Comparator.comparing(Pair::getKey)); // Adding objects of Pair<K, V> class by passing // keys and values as parameter in Pair constructor pq.add(new Pair<>(8,80)); pq.add(new Pair<>(4,70)); pq.add(new Pair<>(9,40)); pq.add(new Pair<>(2,85)); // Printing min heap based on the priority while(!pq.isEmpty()){ System.out.print(pq.remove() +" "); } }} |
Output:
2=85 4=70 8=80 9=40
PriorityQueue Implementing Max Heap Based on Keys of Pair
Java by default creates PriorityQueue of min heap when we do not specify the type. A little change in the above code can make it behave like a Max heap.
Java
// PriorityQueue implementing Max heapPriorityQueue<Pair<Integer, Integer> > pq = new PriorityQueue<>((a, b) -> b.getKey() - a.getKey()); |
Another way to create a max heap:
- By adding the keys into PriorityQueue after multiplying them with -1.
- But do not forget to convert that into the original format (again multiplying by -1) while removing from the queue and performing operations on them.
PriorityQueue Implementing Max Heap and Min Heap Based on Values of Pair
In order to create PriorityQueue based on values of Pair<K, V> just replace getKey() method with getValue() method.
Java
// PriorityQueue implementing Min heap based on values of Pair<K, V>PriorityQueue<Pair<Integer, Integer> > pq = new PriorityQueue<>((a, b) -> a.getValue() - b.getValue()); // PriorityQueue implementing Max heap based on values of Pair<K, V>PriorityQueue<Pair<Integer, Integer> > pq = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue()); |
