How to Use Pair With Java PriorityQueue

1. Overview

The PriorityQueue is one of the most powerful data structures. It’s uncommon in enterprise applications, but we often use it for coding challenges and algorithm implementations.

In this tutorial, we’ll learn how to use Comparators with PriorityQueues and how to change the sorting order in such queues. We’ll then check a more generalized example with a custom class and how we can apply similar logic to a Pair class.

For the Pair class, we’ll use the implementation from Apache Commons. However, numerous options are available, and we can choose the one that best suits our needs.

2. PriorityQueue

First, let’s discuss the data structure itself. This structure’s main superpower is that it maintains the order of the elements while pushing them into the queue.

However, like other queues, it doesn’t provide an API to access the elements inside. We can only access the element in the front of the queue.

At the same time, we have several methods to remove elements from the queue: removeAt() and removeEq(). We can also use a couple of methods from the AbstractCollection. While helpful, they don’t provide random access to the elements.

3. Order

As was mentioned previously, the main feature of the PriorityQueue is that it maintains an order of elements. Unlike LIFO/FIFO, the order doesn’t depend on the order of insertions.

Thus, we should have a general idea of the order of the elements in the queue. We can use it with Comparable elements or provide a custom Comparator while creating a queue.

Because we have these two options, the parametrization doesn’t require the elements to implement the Comparable interface. Let’s check the following class:

public class Book {
    private final String author;
    private final String title;
    private final int publicationYear;

    // constuctor and getters
}

Parametrizing a queue with non-comparable objects is incorrect but won’t result in exceptions:

@ParameterizedTest
@MethodSource("bookProvider")
void givenBooks_whenUsePriorityQueueWithoutComparatorWithoutAddingElements_thenNoExcetption(List<Book> books) {
    PriorityQueue<Book> queue = new PriorityQueue<>();
    assertThat(queue).isNotNull();
}

At the same time, if we try to push such elements into the queue, it won’t be able to identify their natural order and throw ClassCastException:

@ParameterizedTest
@MethodSource("bookProvider")
void givenBooks_whenUsePriorityQueueWithoutComparator_thenThrowClassCastExcetption(List<Book> books) {
    PriorityQueue<Book> queue = new PriorityQueue<>();
    assertThatExceptionOfType(ClassCastException.class).isThrownBy(() -> queue.addAll(books));
}

This is a usual approach for such cases. Collections.sort() behaves similarly while attempting to sort non-comparable elements. We should consider this, as it won’t issue any compile-time errors.

4. Comparator

As was mentioned previously, we can identify the order of the queue in two different ways: implement the Comparable interface or provide a Comparator while initializing a queue.

4.1. Comparable Interface

The Comparable interface is useful when the elements have the idea of natural ordering, and we don’t need to provide it explicitly for our queue. Let’s take the example of the Meeting class:

public class Meeting implements Comparable {
    private final LocalDateTime startTime;
    private final LocalDateTime endTime;  
    private final String title;

    // constructor, getters, equals, and hashCode

    @Override
    public int compareTo(Meeting meeting) {
        return this.startTime.compareTo(meeting.startTime);
    }
}

In this case, the general order would be the starting time of a meeting. This isn’t a strict requirement, and different domains can have different ideas of natural order, but it’s good enough for our example.

We can use the Meeting class directly without additional work from our side:

@Test
void givenMeetings_whenUseWithPriorityQueue_thenSortByStartDateTime() {
    Meeting projectDiscussion = new Meeting(
      LocalDateTime.parse("2025-11-10T19:00:00"),
      LocalDateTime.parse("2025-11-10T20:00:00"),
      "Project Discussion"
    );
    Meeting businessMeeting = new Meeting(
      LocalDateTime.parse("2025-11-15T14:00:00"),
      LocalDateTime.parse("2025-11-15T16:00:00"),
      "Business Meeting"
    );
    PriorityQueue<Meeting> meetings = new PriorityQueue<>();
    meetings.add(projectDiscussion);
    meetings.add(businessMeeting);

    assertThat(meetings.poll()).isEqualTo(projectDiscussion);
    assertThat(meetings.poll()).isEqualTo(businessMeeting);
}

However, if we need to diverge from the default ordering, we should provide a custom Comparator.

4.2. Comparator

While creating a new PriorityQueue, we can pass a Comparator to the constructor and identify the order we want to use. Let’s take the Book class as an example. It created issues previously as it doesn’t implement the Comparable interface or provide no natural ordering.

Imagine we want to order our books by the year to create a reading list. We want to read older ones first to get more insight into the development of science fiction ideas and also understand the influences of the previously published books:

@ParameterizedTest
@MethodSource("bookProvider")
void givenBooks_whenUsePriorityQueue_thenSortThemBySecondElement(List<Book> books) {
    PriorityQueue<Book> queue = new PriorityQueue<>(Comparator.comparingInt(Book::getPublicationYear));
    queue.addAll(books);
    Book previousBook = queue.poll();
    while (!queue.isEmpty()) {
        Book currentBook = queue.poll();
        assertThat(previousBook.getPublicationYear())
          .isLessThanOrEqualTo(currentBook.getPublicationYear());
        previousBook = currentBook;
    }
}

Here, we use the method reference to create a comparator that would sort the books by year. We can add books to our reading queue and pick older books first.

5. Pair

After checking the examples with custom classes, using Pairs with a PriorityQueue is a trivial task. In general, there’s no difference in usage. Let’s consider that our Pairs contain the title and the year of publishing:

@ParameterizedTest
@MethodSource("pairProvider")
void givenPairs_whenUsePriorityQueue_thenSortThemBySecondElement(List<Pair<String, Integer>> pairs) {
    PriorityQueue<Pair<String, Integer>> queue = new PriorityQueue<>(Comparator.comparingInt(Pair::getSecond));

    queue.addAll(pairs);
    Pair<String, Integer> previousEntry = queue.poll();
    while (!queue.isEmpty()) {
        Pair<String, Integer> currentEntry = queue.poll();
        assertThat(previousEntry.getSecond()).isLessThanOrEqualTo(currentEntry.getSecond());
        previousEntry = currentEntry;
    }
}

As we can see, the last two examples are virtually identical. The only difference is that our Comparator uses the Pair class. For this example, we used Pair implementation from Apache Commons. However, there are a bunch of other options.

Also, we can use Map.Entry if none other options are available in our codebase or we don’t want to add new dependencies:

@ParameterizedTest
@MethodSource("mapEntryProvider")
void givenMapEntries_whenUsePriorityQueue_thenSortThemBySecondElement(List<Map.Entry<String, Integer>> pairs) {
    PriorityQueue<Map.Entry<String, Integer>> queue = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));

    queue.addAll(pairs);
    Map.Entry<String, Integer> previousEntry = queue.poll();
    while (!queue.isEmpty()) {
        Map.Entry<String, Integer> currentEntry = queue.poll();
        assertThat(previousEntry.getValue()).isLessThanOrEqualTo(currentEntry.getValue());
        previousEntry = currentEntry;
    }
}

At the same time, we can easily create a new class to represent a pair. Optionally, we can use an array or a List parametrized by Object, but it’s not recommended as this breaks the type safety.

The combination of a Pair and a PriorityQueue is quite common for graph traversal algorithms, such as Dijkstra’s. Other languages, like JavaScript and Python, can create data structures on the fly. In contrast, Java requires some initial setup with additional classes or interfaces.

6. Conclusion

The PriorityQueue is an excellent data structure to implement more performant and straightforward algorithms. It allows customization with Comparators so that we can provide any sorting rules based on our domain requirements.

Combining PriorityQueue and Pairs helps us write more robust and easy-to-understand code. However, it’s often considered a more advanced data structure, and not all developers are fluent with its API.