Queue, PriorityQueue, Comparator and Comparable

Sorting and ordering are at the heart of almost every real program you will write. Before you can sort a list of custom objects, schedule tasks by priority, or implement Dijkstra's shortest path algorithm, you need to understand four things deeply: the Queue interface, PriorityQueue, and the two comparison mechanisms Java gives you called Comparator and Comparable. These topics show up in interviews constantly because they test whether you genuinely understand how Java's sorting machinery works under the hood, not just whether you memorized a few method names.

The Queue Interface and How It Models Real Life

Think about standing in line at a movie theater. The person who arrived first is at the front and gets their ticket first. New arrivals join at the back. Nobody cuts in the middle. This exact behavior is what a queue data structure gives you: the first item added is the first item removed. Programmers call this FIFO, which stands for first in first out.

In Java, Queue is an interface that extends Collection. Because it extends Collection, every queue automatically inherits all the methods you already know from Collection, like size, isEmpty, contains, and iterator. On top of those, Queue adds six methods specifically designed for queue operations. Understanding these six methods well, and in particular understanding why there are two versions of each operation, will save you from subtle bugs.

Why Two Versions of Every Operation

Queues are frequently bounded. A thread pool might have a maximum of 100 pending tasks. A messaging buffer might hold at most 1000 messages. When a bounded queue is full and you try to add another element, something has to happen. Similarly, when a queue is empty and you try to remove or look at the front element, something has to happen. Java's designers made a clean decision: give developers a choice between a version that throws an exception when something goes wrong and a version that returns a special value instead.

The three operations on a queue are insert, remove, and examine. Each one has an exception throwing version and a quiet version. Here is how they pair up.

For inserting an element at the rear of the queue, you have add and offer. The add method inserts the element and returns true if it succeeds. If insertion fails because the queue is at capacity, add throws an IllegalStateException. The offer method also inserts the element but instead of throwing an exception when the queue is full, it returns false. Most queue implementations, such as PriorityQueue and ArrayDeque, throw a NullPointerException if you insert null. (LinkedList accepts null, but you should not rely on that, for the reason below.)

For removing and retrieving the element at the front of the queue, you have remove and poll. The remove method removes the head element and returns it. If the queue is empty, remove throws NoSuchElementException. The poll method does the same thing but returns null if the queue is empty instead of throwing.

For examining the head element without removing it, you have element and peek. The element method returns the head without removing it and throws NoSuchElementException if the queue is empty. The peek method returns null if the queue is empty instead of throwing.

You can think of it this way: add, remove, and element are the loud versions that make noise when something goes wrong. offer, poll, and peek are the quiet versions that handle failure silently.

import java.util.LinkedList;
import java.util.Queue;

public class QueueDemo {
    public static void main(String[] args) {
        Queue<String> q = new LinkedList<>();

        // offer is the safe way to insert: returns false on failure, never throws
        q.offer("Order_101");
        q.offer("Order_102");
        q.offer("Order_103");

        // peek lets you look at the front without removing it
        System.out.println("Head element: " + q.peek()); // Order_101

        // poll is the safe way to remove: returns null on empty queue, never throws
        while (!q.isEmpty()) {
            System.out.println("Processing: " + q.poll());
        }

        // queue is now empty
        System.out.println("poll on empty: " + q.poll()); // null, no crash

        // This would throw NoSuchElementException:
        // q.remove();
    }
}

The reason null should never be put in a queue is subtle but important. Both poll and peek use null as their sentinel value to communicate "the queue is empty." If null were a valid element you could store in the queue, then when poll returned null, you would not know whether it removed a null element or whether the queue was empty. The prohibition on null keeps the contract clean.

PriorityQueue: Java's Heap Implementation

A standard queue serves elements in the order they arrived. A PriorityQueue serves elements in order of priority, where priority is determined by a comparison rule you define. This is exactly what a heap data structure does, and PriorityQueue is Java's built in heap.

If you are solving data structure problems involving heaps, this is the class you reach for. Top K elements, Dijkstra's shortest path, finding the median of a stream, task scheduling by deadline, all of these use PriorityQueue in Java.

Min Heap by Default

When you create a PriorityQueue without passing any arguments to the constructor, Java uses the natural ordering of the elements. For integers, natural ordering is ascending order, meaning the smallest number has the highest priority and sits at the top of the heap. This gives you a min heap.

import java.util.PriorityQueue;

public class MinHeapDemo {
    public static void main(String[] args) {
        // Empty constructor = min heap using natural ordering
        PriorityQueue<Integer> minPQ = new PriorityQueue<>();

        minPQ.add(5);
        minPQ.add(2);
        minPQ.add(8);
        minPQ.add(1);

        // Internally the heap looks like this after insertions:
        //         1
        //        / \
        //       2   8
        //      /
        //     5
        // The tree always satisfies: parent <= children (min heap property)

        System.out.print("Min heap output: ");
        while (!minPQ.isEmpty()) {
            System.out.print(minPQ.poll() + " "); // 1 2 5 8
        }
        // Elements come out in ascending order because poll always removes the minimum
    }
}

When you call add with 5, then 2, then 8, then 1, Java does not store them in insertion order. Instead, it maintains the heap property at all times. After each insertion, it performs an operation called heapify up, comparing the new element with its parent and swapping upward until the heap property is restored.

When you call poll, Java removes the root (the minimum element), moves the last leaf to the root position, then performs heapify down, swapping downward with the smaller of its two children until the heap property is restored. Both insert and poll run in O(log N) time because the height of a heap with N elements is log N.

The peek operation just reads the root without removing it, which is O(1) because the root is always at index zero of the internal array.

The Internal Array Layout

A heap is stored as an array, not as actual tree objects with left and right pointers. This is much more memory efficient. The mapping between tree positions and array indices follows simple formulas.

Min Heap Tree:              Internal Array:
        1                   Index: 0   1   2   3
       / \                  Value: 1   2   8   5
      2   8
     /
    5

Parent of node at index i:     (i - 1) / 2
Left child of node at index i:  2 * i + 1
Right child of node at index i: 2 * i + 2

For example, the element at index 1 has its parent at index (1 - 1) / 2 = 0, and its left child at index 2 * 1 + 1 = 3. This perfectly describes the tree structure without any pointers.

Max Heap with a Comparator

To get a max heap, you pass a Comparator to the PriorityQueue constructor. The comparator tells PriorityQueue to treat larger numbers as having higher priority.

import java.util.PriorityQueue;

public class MaxHeapDemo {
    public static void main(String[] args) {
        // Pass a comparator to reverse the ordering: largest element gets highest priority
        PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a, b) -> Integer.compare(b, a));

        maxPQ.add(5);
        maxPQ.add(2);
        maxPQ.add(8);
        maxPQ.add(1);

        System.out.print("Max heap output: ");
        while (!maxPQ.isEmpty()) {
            System.out.print(maxPQ.poll() + " "); // 8 5 2 1
        }
        // Elements come out in descending order
    }
}

The key insight is that by passing (a, b) -> Integer.compare(b, a) instead of (a, b) -> Integer.compare(a, b), you flip what the heap considers "smallest." The heap always puts the element that compares as the smallest at the top, but now "smallest" means the one the comparator ranks lowest, which in this reversed comparator is actually the largest integer.

Time Complexity Summary

Operation	Method	Time
Peek root	peek()	O(1)
Insert	add(e) or offer(e)	O(log N)
Remove root	poll() or remove()	O(log N)
Remove arbitrary element	remove(Object o)	O(N)
Build from existing collection	new PriorityQueue<>(collection)	O(N)

Removing an arbitrary element is O(N) because the heap has no index, so Java must scan through all elements to find the one to remove, which takes O(N), then heapify down, which takes O(log N). The dominating term is O(N).

Building a heap from an existing collection using Floyd's algorithm is O(N), which is more efficient than inserting elements one by one which would take O(N log N).

Why Comparator and Comparable Exist

Now you know that PriorityQueue takes a Comparator. You also know that arrays.sort and Collections.sort exist. But why do these sorting tools need Comparator and Comparable at all? Why cannot they just sort things directly?

Here is the problem. Imagine you have a class called Car with a name and a type. You create an array of three Car objects and call Arrays.sort on the array.

class Car {
    String carName;
    String carType;

    Car(String carName, String carType) {
        this.carName = carName;
        this.carType = carType;
    }
}

public class Main {
    public static void main(String[] args) {
        Car[] carArray = new Car[3];
        carArray[0] = new Car("SUV", "Petrol");
        carArray[1] = new Car("Sedan", "Diesel");
        carArray[2] = new Car("Hatchback", "CNG");

        Arrays.sort(carArray); // This crashes!
    }
}

Running this throws a ClassCastException with a message like "Car cannot be cast to Comparable." Why does it crash?

Every sorting algorithm works by repeatedly comparing pairs of elements to decide which one comes first. When Java's sorting algorithm picks up your SUV car and your Sedan car, it needs to answer one question: should SUV come before Sedan, or should Sedan come before SUV? To answer that question, it needs to invoke a comparison method. But what method? Java has no idea whether you want to sort by car name alphabetically, by car type alphabetically, by some numeric ID, or by any other criterion.

For primitive types like int and double, Java knows how to compare them directly. For wrapper objects like Integer and Double, these classes have already told Java how to compare them: numerically in ascending order. But for your custom Car class, you have never told Java anything about ordering. So Java throws an exception.

This is exactly the problem that Comparator and Comparable solve. Both of them define a contract for how to compare two objects. Once you provide that contract, sorting algorithms can do their job.

Understanding the Swap Decision: The Heart of All Sorting

Before diving into Comparator and Comparable separately, you need to understand one fundamental rule that applies to both. Every sorting algorithm, whether it is quicksort, merge sort, timsort, or anything else, boils down to making decisions: for these two elements, are they in the right order, or do they need to be swapped?

A useful way to think about it (the real sorting algorithms are more complex, but the contract is the same): if the comparison method returns a positive number (greater than zero), swap the two elements. If it returns zero, they are equal in ordering. If it returns a negative number (less than zero), do not swap them.

compare(object1, object2) > 0  --> swap  (object1 is "too big", it needs to move right)
compare(object1, object2) == 0 --> no action needed (they are equal)
compare(object1, object2) < 0  --> no swap (they are already in the right order)

This single rule is the engine behind every sorting decision Java makes. Comparator and Comparable are both just ways of telling Java how to produce that positive, zero, or negative number for any two given elements.

The practical formulas follow directly from this rule. If you want ascending order, you want smaller elements to stay in front, so when object1 is smaller you return negative (no swap) and when object1 is larger you return positive (swap). This gives you the formula: compare(object1, object2). If you want descending order, you flip it: compare(object2, object1).

Comparator: External, Flexible, Unlimited

A Comparator is a functional interface in java.util. It has one abstract method with this signature:

int compare(T object1, T object2)

Notice that it takes two parameters. Both the objects being compared are passed in from outside. This means you define a Comparator outside of the class you are comparing, as a separate thing. You can create as many different Comparators as you want for the same class.

Sorting Integers in Ascending and Descending Order

import java.util.Arrays;
import java.util.Comparator;

public class ComparatorDemo {
    public static void main(String[] args) {
        Integer[] numbers = {17, 3, 5, 1, 10, 8};

        // Ascending order: compare(a, b) means a - b direction
        // When a > b, result is positive, so a gets swapped to the right
        Arrays.sort(numbers, (val1, val2) -> Integer.compare(val1, val2));
        System.out.println("Ascending: " + Arrays.toString(numbers));
        // Output: [1, 3, 5, 8, 10, 17]

        // Descending order: flip the arguments
        // Now when val1 > val2, result is negative, so val1 stays in front
        Arrays.sort(numbers, (val1, val2) -> Integer.compare(val2, val1));
        System.out.println("Descending: " + Arrays.toString(numbers));
        // Output: [17, 10, 8, 5, 3, 1]
    }
}

Let us trace through a specific example with the descending comparator. Say the algorithm picks val1 = 9 and val2 = 1. The comparator runs Integer.compare(val2, val1) which is Integer.compare(1, 9) which returns a negative number. The sorting code sees negative and does not swap, so 9 stays in front of 1. Correct for descending order.

Now say val1 = 1 and val2 = 9. The comparator runs Integer.compare(val2, val1) which is Integer.compare(9, 1) which returns a positive number. The sorting code sees positive and swaps, so 9 moves in front of 1. Again correct for descending order.

By simply flipping which argument goes first in Integer.compare, you get descending order without changing the sorting algorithm at all. The algorithm stays fixed. You just change the comparison function.

Sorting Custom Objects with Comparator

Going back to the Car example, you can now sort the car array using a Comparator without touching the Car class at all.

import java.util.Arrays;

class Car {
    String carName;
    String carType;

    Car(String carName, String carType) {
        this.carName = carName;
        this.carType = carType;
    }

    @Override
    public String toString() {
        return carName + "(" + carType + ")";
    }
}

public class CarSortDemo {
    public static void main(String[] args) {
        Car[] carArray = {
            new Car("SUV", "Petrol"),
            new Car("Sedan", "Diesel"),
            new Car("Hatchback", "CNG")
        };

        // Sort by car name in ascending order (lexicographic)
        // String's compareTo returns negative, zero, or positive, fitting the contract perfectly
        Arrays.sort(carArray, (c1, c2) -> c1.carName.compareTo(c2.carName));
        System.out.println("By name ascending: " + Arrays.toString(carArray));
        // Hatchback(CNG), Sedan(Diesel), SUV(Petrol)

        // Sort by car type in descending order
        Arrays.sort(carArray, (c1, c2) -> c2.carType.compareTo(c1.carType));
        System.out.println("By type descending: " + Arrays.toString(carArray));
        // Petrol is last alphabetically, so it comes first in descending order
    }
}

For strings, String.compareTo performs lexicographic (alphabetical) comparison and returns the same kind of negative, zero, or positive result. It plugs directly into the comparator contract.

Three Ways to Write a Comparator

Because Comparator is a functional interface, you have three styles to choose from. A Lambda expression is usually the cleanest. An anonymous class is more verbose but avoids needing Java 8. A named class lets you reuse the comparator in many places.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Collections;

// Named comparator class: reusable, testable, can be in its own file
class CarNameDescendingComparator implements Comparator<Car> {
    @Override
    public int compare(Car o1, Car o2) {
        return o2.carName.compareTo(o1.carName); // descending
    }
}

public class ThreeStyles {
    public static void main(String[] args) {
        List<Car> carList = new ArrayList<>();
        carList.add(new Car("SUV", "Petrol"));
        carList.add(new Car("Sedan", "Diesel"));
        carList.add(new Car("Hatchback", "CNG"));

        // Style 1: Lambda (preferred, most concise)
        Collections.sort(carList, (c1, c2) -> c1.carName.compareTo(c2.carName));

        // Style 2: Anonymous class (no lambda syntax needed)
        Collections.sort(carList, new Comparator<Car>() {
            @Override
            public int compare(Car o1, Car o2) {
                return o1.carName.compareTo(o2.carName);
            }
        });

        // Style 3: Named class (maximum reusability)
        Collections.sort(carList, new CarNameDescendingComparator());
    }
}

Collections.sort on a list uses the same comparison contract as Arrays.sort on an array (it calls list.sort(comparator), which sorts the list's elements using that comparator).

The Power of Multiple Comparators

The real advantage of Comparator over Comparable becomes clear when you need multiple ways to sort the same objects. With Comparator, you define each ordering externally and pick the one you need at the call site. You never touch the Car class.

// One class, many orderings, all defined externally
Comparator<Car> byNameAscending  = (c1, c2) -> c1.carName.compareTo(c2.carName);
Comparator<Car> byNameDescending = (c1, c2) -> c2.carName.compareTo(c1.carName);
Comparator<Car> byTypeAscending  = (c1, c2) -> c1.carType.compareTo(c2.carType);
Comparator<Car> byTypeDescending = (c1, c2) -> c2.carType.compareTo(c1.carType);

// Use whichever one the situation calls for:
carList.sort(byNameAscending);
carList.sort(byTypeDescending);

This flexibility is simply not possible with Comparable.

Comparable: Internal, Fixed, Natural

The Comparable interface lives in java.lang (no import needed). It has one abstract method:

int compareTo(T other)

Notice that it takes only one parameter. The other object being compared is the parameter. The first object, the one you are comparing against, is implicit: it is the object on which you call compareTo, meaning this.

Because you only have access to this and one other parameter inside compareTo, and because the interface is meant to be implemented by the class being compared, Comparable always lives inside the class itself. You modify the class definition to say "this class implements Comparable" and then provide the compareTo method.

Natural Ordering with Comparable

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Car implements Comparable<Car> {
    String carName;
    String carType;

    Car(String carName, String carType) {
        this.carName = carName;
        this.carType = carType;
    }

    @Override
    public int compareTo(Car other) {
        // Natural ordering: by car type, ascending
        // 'this' is object1, 'other' is object2
        return this.carType.compareTo(other.carType);
    }

    @Override
    public String toString() {
        return carName + "(" + carType + ")";
    }

    public static void main(String[] args) {
        List<Car> carList = new ArrayList<>();
        carList.add(new Car("SUV", "Petrol"));
        carList.add(new Car("Sedan", "CNG"));
        carList.add(new Car("Hatchback", "Diesel"));

        // No comparator needed: Collections.sort uses compareTo automatically
        Collections.sort(carList);
        System.out.println(carList);
        // CNG comes before Diesel, Diesel before Petrol alphabetically
        // Output: [Sedan(CNG), Hatchback(Diesel), SUV(Petrol)]
    }
}

When you call Collections.sort without a comparator, the sorting algorithm internally calls compareTo on pairs of elements. It can do this because the class implements Comparable, so Java knows compareTo exists and what it means. The sorting code essentially says "this object, compared to that object" and your compareTo provides the answer.

Why Integer and String Already Sort Correctly

When you sort an array of integers or strings without passing any comparator, it works because Integer implements Comparable<Integer> and String implements Comparable<String>. Both provide compareTo methods. Integer.compareTo sorts numerically in ascending order. String.compareTo sorts alphabetically. These are their natural orderings.

When Java's sorting algorithm on objects gets no comparator, it falls back to calling compareTo. This is why Arrays.sort works on an Integer[] or String[] but fails for your custom Car class unless Car implements Comparable. (A primitive int[] is sorted directly by value, without any compareTo.)

The One Ordering Limitation

The critical limitation of Comparable is that you can only define one compareTo method per class. One class, one natural ordering, forever. If you implement compareTo to sort by car type, you cannot also sort by car name using compareTo. You would have to change compareTo itself, which affects every sorting operation everywhere in your program that relies on the natural ordering.

This is where Comparator wins decisively. If you need to sort cars by name in one part of your program and by type in another part, you must use Comparator for at least one of those orderings. You can still use Comparable to define the most common natural ordering and use Comparator for everything else.

Comparator vs Comparable Side by Side

Feature	Comparable	Comparator
Package	java.lang (no import needed)	java.util (must import)
Method	int compareTo(T other)	int compare(T o1, T o2)
Parameters	One (the other object; this is the first)	Two (both objects passed in)
Location	Inside the class being compared	Outside, as lambda, anonymous class, or named class
Number of orderings	Exactly one natural ordering per class	Unlimited, create as many as you need
Requires modifying the class	Yes	No
Use case	Define the default sort order for a class	Define alternative sort orders without touching the class

How the Comparator Plugs into PriorityQueue

Now that you understand Comparator fully, the max heap line from earlier makes complete sense.

// Min heap: no comparator, uses natural ordering (ascending), smallest at top
PriorityQueue<Integer> minPQ = new PriorityQueue<>();

// Max heap: pass a comparator that reverses natural ordering
// When a = 8 and b = 3: Integer.compare(b, a) = Integer.compare(3, 8) = negative
// Heap sees negative: 8 already has higher priority than 3, no swap needed
// This means larger numbers get higher priority, giving a max heap
PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a, b) -> Integer.compare(b, a));

The PriorityQueue constructor stores your comparator and uses it every time it needs to decide heap ordering. When you add an element, it uses the comparator during heapify up to decide whether the new element should bubble toward the root. When you poll, it uses the comparator during heapify down to find the correct child to swap with. Everything else about PriorityQueue stays the same.

You can also use a Comparator with a PriorityQueue of custom objects.

import java.util.PriorityQueue;

class Task {
    String name;
    int priority; // higher number = more urgent

    Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    @Override
    public String toString() {
        return name + "(priority=" + priority + ")";
    }
}

public class TaskScheduler {
    public static void main(String[] args) {
        // Max heap by priority: most urgent task at the top
        PriorityQueue<Task> taskQueue = new PriorityQueue<>(
            (t1, t2) -> Integer.compare(t2.priority, t1.priority)
        );

        taskQueue.offer(new Task("Send email", 2));
        taskQueue.offer(new Task("Fix production bug", 10));
        taskQueue.offer(new Task("Code review", 5));

        System.out.println("Next task: " + taskQueue.poll()); // Fix production bug(priority=10)
        System.out.println("Next task: " + taskQueue.poll()); // Code review(priority=5)
        System.out.println("Next task: " + taskQueue.poll()); // Send email(priority=2)
    }
}

Putting It All Together: A Complete Working Example

Here is an example that ties together Queue methods, PriorityQueue, Comparable, and Comparator in one place.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

class Student implements Comparable<Student> {
    int rollNumber;
    String name;
    double gpa;

    Student(int rollNumber, String name, double gpa) {
        this.rollNumber = rollNumber;
        this.name = name;
        this.gpa = gpa;
    }

    // Natural ordering: by roll number ascending (Comparable)
    @Override
    public int compareTo(Student other) {
        return Integer.compare(this.rollNumber, other.rollNumber);
    }

    @Override
    public String toString() {
        return name + "(roll=" + rollNumber + ", gpa=" + gpa + ")";
    }
}

public class CompleteDemo {
    public static void main(String[] args) {
        List<Student> students = new ArrayList<>();
        students.add(new Student(103, "Alice", 3.8));
        students.add(new Student(101, "Bob", 3.5));
        students.add(new Student(102, "Charlie", 3.9));
        students.add(new Student(104, "Diana", 3.2));

        // Uses Comparable: natural order is by roll number ascending
        Collections.sort(students);
        System.out.println("By roll number: " + students);
        // Bob(101), Charlie(102), Alice(103), Diana(104)

        // Uses Comparator: sort by GPA descending (external, does not touch Student class)
        students.sort((s1, s2) -> Double.compare(s2.gpa, s1.gpa));
        System.out.println("By GPA descending: " + students);
        // Charlie(3.9), Alice(3.8), Bob(3.5), Diana(3.2)

        // PriorityQueue with Comparator: highest GPA student is always at top (max heap by GPA)
        PriorityQueue<Student> topStudents = new PriorityQueue<>(
            (s1, s2) -> Double.compare(s2.gpa, s1.gpa)
        );
        topStudents.addAll(students);

        System.out.println("Top student: " + topStudents.poll()); // Charlie(3.9)
        System.out.println("Second: " + topStudents.poll());      // Alice(3.8)
    }
}

Check yourself

1. What are the three queue operations, and what is the difference between add/remove/element and offer/poll/peek?
2. Why should you never put null in a queue?
3. What kind of heap does new PriorityQueue<>() give you, and how do you get the opposite?
4. What is the time complexity of peek, offer, poll, and remove(Object) on a PriorityQueue?
5. Why does Arrays.sort on an array of Car objects throw an exception?
6. What do a negative, zero and positive result from compare mean? How do you get descending order?
7. What is the difference between Comparable and Comparator?

Answers

1. Insert, remove, examine. The first set throws an exception on failure (full or empty queue); the second returns false or null instead.
2. poll and peek return null to mean "empty", so a stored null would be indistinguishable from an empty queue.
3. A min heap (natural ordering). Pass a comparator such as (a, b) -> Integer.compare(b, a) for a max heap.
4. peek O(1); offer and poll O(log N); remove(Object) O(N).
5. Java does not know how to compare two Car objects: Car neither implements Comparable nor was a Comparator given, so a ClassCastException is thrown.
6. Negative: keep the order; zero: equal; positive: swap. Use compare(b, a) instead of compare(a, b) for descending.
7. Comparable (java.lang, compareTo(T other)) is implemented inside the class and defines one natural ordering. Comparator (java.util, compare(T a, T b)) is written outside the class, and you can create as many orderings as you need.