Java’s PriorityQueue is a data structure that allows us to store and retrieve elements in a specific order. This article explores how to use pairs with PriorityQueue and demonstrates how to use Comparator interface to control the sorting order.
1. What is a PriorityQueue?
A PriorityQueue is a queue data structure where elements are ordered based on their priority rather than their insertion order. This data structure is part of the Java Collections Framework and is typically used when processing elements in a specific order, defined by their natural ordering or a custom comparator.
1.1 Ordering
One of the key characteristics of PriorityQueue is its ordering mechanism. Elements are ordered based on their priority. The default priority is determined by the natural ordering of elements (meaning the elements must implement the Comparable interface), or we can define a custom Comparator to specify the order.
1.2 What is a Pair?
The Pair class in Java was a convenient utility class found in JavaFX, which allowed developers to store a pair of values, essentially providing a simple way to return two related objects from a method. A Pair object holds two values, referred to as key and value, and provide methods to access these values. Here is a simple usage example:
import javafx.util.Pair;
Pair<Integer, String> pair = new Pair<>(1, "one");
System.out.println("Key: " + pair.getKey());
System.out.println("Value: " + pair.getValue());
The Pair class (javafx.util.Pair), along with other parts of JavaFX, was decoupled from the JDK in Java 11. The removal of JavaFX from the JDK meant that the Pair class is no longer a built-in part of the standard Java library from Java 11 onwards.
Developers needing Pair functionality now often resort to either custom implementations or third-party libraries such as Apache Commons Lang (org.apache.commons.lang3.tuple.Pair).
2. Using PriorityQueue with a Custom Class
To use PriorityQueue with a Custom class, we will create a class that implements the Comparable interface. Let’s consider an example using a custom class named Book, which includes a title and a publication year.
Book.java
public class Book implements Comparable<Book>{
String title;
int year;
public Book(String title, int year) {
this.title = title;
this.year = year;
}
public String getTitle() {
return title;
}
public int getYear() {
return year;
}
@Override
public int compareTo(Book other) {
// Compare Books based on their year
return Integer.compare(this.year, other.year);
}
@Override
public String toString() {
return title + " (" + year + ")";
}
}
In this example, the Book class implements the Comparable interface.
Next, we create a PriorityQueue of Book objects, add some books to the priority queue and process elements from the PriorityQueue.
PriorityQueueExample1.java
public class PriorityQueueExample1 {
public static void main(String[] args) {
// Create a PriorityQueue and Add Books to the Queue
PriorityQueue<Book> bookQueue = new PriorityQueue<>();
bookQueue.add(new Book("To Kill a Mockingbird", 1960));
bookQueue.add(new Book("1984", 1949));
bookQueue.add(new Book("The Age of Reason", 1794));
bookQueue.add(new Book("The Great Gatsby", 1925));
// Process Books
while (!bookQueue.isEmpty()) {
Book book = bookQueue.poll();
System.out.println(book);
}
}
}
This code will create a PriorityQueue of Book objects, sorted by year in ascending order. The output is:
The Age of Reason (1794)
The Great Gatsby (1925)
1984 (1949)
To Kill a Mockingbird (1960)
3. Using Comparators with PriorityQueue
To customize the sorting order in the PriorityQueue, we can use a Comparator.
3.1 Using Comparator.comparing()
ProrityQueueExample2.java
public class ProrityQueueExample2 {
public static void main(String[] args) {
PriorityQueue<Book> bookQueue = new PriorityQueue<>(Comparator.comparingInt(Book::getYear));
bookQueue.add(new Book("To Kill a Mockingbird", 1960));
bookQueue.add(new Book("1984", 1949));
bookQueue.add(new Book("The Age of Reason", 1794));
bookQueue.add(new Book("The Great Gatsby", 1925));
while (!bookQueue.isEmpty()) {
Book book = bookQueue.poll();
System.out.println(book);
}
}
}
Here, the Books are sorted based on the year element in ascending order. Note that the Book class does not need to implement the Comparable interface for this example.
3.2 Using Lambda Expression
We can also utilize lambda expressions as follows:
public class ProrityQueueExample2 {
public static void main(String[] args) {
// Using Lambda expressions
PriorityQueue<Book> bookQueue = new PriorityQueue<>((Book b1, Book b2) -> Integer.compare(b1.getYear(), b2.getYear()));
bookQueue.add(new Book("To Kill a Mockingbird", 1960));
bookQueue.add(new Book("1984", 1949));
bookQueue.add(new Book("The Age of Reason", 1794));
bookQueue.add(new Book("The Great Gatsby", 1925));
while (!bookQueue.isEmpty()) {
Book book = bookQueue.poll();
System.out.println(book);
}
}
}
3.3 Changing the Sorting Order
To change the sorting order, simply modify the Comparator. For example, the code fragment below shows how to sort Books in descending order based on the year value:
PriorityQueue<Book> bookQueue = new PriorityQueue<>((Book b1, Book b2) -> Integer.compare(b2.getYear(), b1.getYear()));
The output becomes:
To Kill a Mockingbird (1960)
1984 (1949)
The Great Gatsby (1925)
The Age of Reason (1794)
Output demonstrating the use of a comparator to sort a Java PriorityQueue of pairs in descending order
4. Using Apache Commons Pair
The Apache Commons Lang library provides a Pair class which is a simple container to store a pair of objects. Using Apache Commons Pair with Java’s PriorityQueue can enhance the handling of paired data with specific priorities. Here’s an example of combining Apache Commons Pair with PriorityQueue:
ApachePairPriorityQueueExample.java
import java.util.Comparator;
import org.apache.commons.lang3.tuple.Pair;
import java.util.PriorityQueue;
public class ApachePairPriorityQueueExample {
public static void main(String[] args) {
// Example usage of the Pair class with PriorityQueue
// PriorityQueue is initialized with the comparator
PriorityQueue<Pair<String, Integer>> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(Pair::getValue));
// Adding Pairs to the priority queue
priorityQueue.add(Pair.of("Finish Article", 3));
priorityQueue.add(Pair.of("Buy Milk", 1));
priorityQueue.add(Pair.of("Call Mom", 2));
// Polling elements from the priority queue
while (!priorityQueue.isEmpty()) {
Pair<String, Integer> pair = priorityQueue.poll();
System.out.println("Priority " + pair.getValue() + " : " + pair.getKey());
}
}
}
5. Conclusion
In this article, we explored how to use Java’s PriorityQueue with custom classes and the Apache Commons Pair class. We started with an overview of the PriorityQueue and delved into examples demonstrating how to create and manipulate a PriorityQueue with custom pairs, emphasizing how to use Comparator to control the sorting order. We also covered an example using a custom Book class, showcasing how PriorityQueue can be adapted to manage more complex objects. Finally, we demonstrated how to utilize Apache Commons’ Pair class for similar purposes.
Posts
0 comments:
Post a Comment