Java PriorityQueue Quick Reference Cheat Sheet

Handy reference on how to use PriorityQueue in Java, most useful data structure for coding interview questions.

PriorityQueue is a part of the Java Collections Framework (under java.util package). It's an unbounded queue based on a priority heap, and elements are ordered based on their natural order or a provided comparator.

Initialization

Default initialization (uses natural order):

PriorityQueue<Integer> pq = new PriorityQueue<>();

Initialization with a custom comparator:

PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Comparator.reverseOrder());

Initialization with initial capacity and custom comparator:

PriorityQueue<Integer> maxPQ = new PriorityQueue<>(10, Comparator.reverseOrder());

Basic Operations

Add: Adds an item to the queue.

pq.add(5);

Poll: Removes and returns the head of the queue (smallest element for min heap).

Integer item = pq.poll();

Peek: Returns (without removing) the head of the queue.

Integer item = pq.peek();

Size: Returns the number of elements in the queue.

int size = pq.size();

Contains: Check if the queue contains an element.

boolean exists = pq.contains(5);

Remove: Removes a specific object from the queue.

pq.remove(5);

Iteration

While PriorityQueue does not guarantee any specific order over its elements other than its head, you can still iterate over its elements:

for (Integer item : pq) {
    System.out.println(item);
}

Caution

• PriorityQueue is not synchronized. For a thread-safe variant, consider using PriorityBlockingQueue.
• Avoid using methods like remove(Object) or contains(Object) excessively on large heaps, as they can be slow (O(n) time complexity).

Custom Comparators

For Integers (Max Heap):

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

For Strings:

a. Based on Length:

PriorityQueue<String> strPQByLength = new PriorityQueue<>((s1, s2) -> s2.length() - s1.length());

b. Lexicographical Order (Ascending):

PriorityQueue<String> strPQLexi = new PriorityQueue<>();

c. Lexicographical Order (Descending):

PriorityQueue<String> strPQLexiDesc = new PriorityQueue<>(Comparator.reverseOrder());

For Complex Objects:

class Person {
    String name;
    int age;
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
}

// Based on age in descending order
PriorityQueue<Person> personPQ = new PriorityQueue<>((p1, p2) -> p2.age - p1.age);

If you insert complex objects into a PriorityQueue without providing a custom comparator, the objects must implement the Comparable interface. Otherwise, you'll encounter a ClassCastException at runtime when you try to insert an object into the queue.

The PriorityQueue will use the natural ordering of the objects, as defined by their compareTo method, to determine their priority.

Here’s an example to illustrate:

Let’s consider a Person class:

class Person implements Comparable<Person> {
    String name;
    int age;

    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(Person other) {
        return Integer.compare(this.age, other.age);
    }

    @Override
    public String toString() {
        return name + ": " + age;
    }
}

In this example, the Person class implements the Comparable interface, and the compareTo method defines the natural ordering of Person objects based on their age.

If you insert Person objects into a PriorityQueue:

PriorityQueue<Person> queue = new PriorityQueue<>();
queue.add(new Person("Alice", 30));
queue.add(new Person("Bob", 25));
queue.add(new Person("Charlie", 35));

System.out.println(queue.poll());  // Outputs: Bob: 25
System.out.println(queue.poll());  // Outputs: Alice: 30
System.out.println(queue.poll());  // Outputs: Charlie: 35

As you can see, the PriorityQueue orders the Person objects based on their age in ascending order (youngest to oldest), as defined by the compareTo method.

Java’s PriorityQueue, the contains method

In Java’s PriorityQueue, the contains method is not optimized for priority queues. Instead, it works in a linear fashion, iterating through all the elements in the queue until it finds a match or reaches the end. The complexity of this operation is O(n) where n is the number of elements in the queue.

When you use the contains method with a complex object, it relies on the equals method of that object to determine if the object is present in the queue.

For instance, if you have a class like:

class Person {
    String name;
    int age;

    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age && Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

When you invoke the contains method on a PriorityQueue<Person>, it will rely on the equals method of the Personclass to check for the presence of a specific Person object in the queue.

However, it’s essential to be aware that for the equals method to function correctly and consistently, it should be overridden alongside the hashCode method.

If this content was helpful, please follow me on Medium. More to come!

Further Learning at DSAGuide.com
For an in-depth exploration of data structures, algorithms, and coding interview solutions, I invite you to visit DSAGuide.com. Elevate your understanding with our detailed guides on essential data structures, algorithms and coding interview problem solving.