Coding Patterns + Java Collections

PriorityQueue mental model

A PriorityQueue is still a queue, but elements are popped by priority instead of insertion order. This page explains min heaps, max heaps, comparators, and Top K Frequent Elements.

PriorityQueueHeapComparatorTop KJava

The Short Answer

A PriorityQueue is still a queue, but it does not pop elements in first-in-first-out (FIFO) order like a regular queue.

Instead, it pops the element with the highest priority according to the ordering rule you give it.

In Java, the head of a PriorityQueue is the “least” element according to its natural ordering or supplied Comparator. So the comparator decides what comes out first.

Normal Queue vs PriorityQueue

Normal Queue

offer(5)

offer(1)

offer(9)

poll() returns 5 first

PriorityQueue

offer(5)

offer(1)

offer(9)

poll() returns 1 (smallest value) first

The normal queue cares about insertion order. The priority queue cares about priority order.

Min Heap Mental Model

By default, Java's PriorityQueue behaves like a min heap for numbers.

That means the smallest element is at the head and will be popped first.

Min heap: the minimum element is easiest to access.

java

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

minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(9);

System.out.println(minHeap.poll()); // 1
System.out.println(minHeap.poll()); // 5
System.out.println(minHeap.poll()); // 9

In a min heap, the minimum element according to the comparator is popped first.

Max Heap Mental Model

Java does not have a separate MaxPriorityQueue class. Instead, you create a max heap by reversing the comparator.

Max heap: the maximum element is easiest to access.

java

PriorityQueue<Integer> maxHeap =
        new PriorityQueue<>((a, b) -> b - a);

maxHeap.offer(5);
maxHeap.offer(1);
maxHeap.offer(9);

System.out.println(maxHeap.poll()); // 9
System.out.println(maxHeap.poll()); // 5
System.out.println(maxHeap.poll()); // 1

For simple examples, (a, b) => b - a is common, but in production code prefer:

java

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

In a max heap, the maximum element according to the comparator is popped first.

Important: PriorityQueue Is Not Fully Sorted

A common mistake is thinking that a PriorityQueue stores all elements in sorted order.

It does not. It only guarantees that the head is the next element to be popped.

java

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

pq.offer(5);
pq.offer(1);
pq.offer(9);
pq.offer(2);

System.out.println(pq);       // not guaranteed sorted
System.out.println(pq.peek()); // guaranteed smallest element

If you need a fully sorted list, sort a list. If you repeatedly need the next highest or next lowest priority item, use a PriorityQueue.

Comparator Defines Priority

With objects, you almost always pass a comparator.

java

import java.util.Comparator;
import java.util.PriorityQueue;

public class PriorityQueueWithObjects {
    record Task(String name, int priority) {}

    public static void main(String[] args) {
        PriorityQueue<Task> tasks =
                new PriorityQueue<>(
                        Comparator.comparingInt(Task::priority)
                );

        tasks.offer(new Task("Send email", 3));
        tasks.offer(new Task("Fix production bug", 1));
        tasks.offer(new Task("Update docs", 5));

        while (!tasks.isEmpty()) {
            System.out.println(tasks.poll());
        }
    }
}

Since the comparator compares by priority ascending, the task with priority 1 is popped first.

If you want larger numbers to mean higher priority, reverse the comparator.

java

PriorityQueue<Task> tasks =
        new PriorityQueue<>(
                Comparator.comparingInt(Task::priority).reversed()
        );

Top K Frequent Elements

This is one of the most common PriorityQueue interview patterns.

The trick is to count frequencies first, then keep only the top K elements in a min heap.

For Top K problems, a min heap of size K is often useful. The smallest item among the current top K sits at the top, so when a better item arrives, we remove the weakest current candidate.

java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public class TopKFrequentElements {
    record Entry(int number, int frequency) {}

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;

        List<Integer> result = topKFrequent(nums, k);

        System.out.println(result);
    }

    static List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();

        for (int num : nums) {
            frequencyMap.put(
                    num,
                    frequencyMap.getOrDefault(num, 0) + 1
            );
        }

        PriorityQueue<Entry> minHeap =
                new PriorityQueue<>(
                        (a, b) -> a.frequency() - b.frequency()
                );

        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            minHeap.offer(
                    new Entry(entry.getKey(), entry.getValue())
            );

            // if size goes over k, delete the lowest priority item
            // and bring the size back to k!!
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        List<Integer> result = new ArrayList<>();

        while (!minHeap.isEmpty()) {
            result.add(minHeap.poll().number());
        }

        return result;
    }
}

For the input:

java

int[] nums = {1, 1, 1, 2, 2, 3};
int k = 2;

the two most frequent numbers are:

java

[2, 1]

The order of the final result may vary unless the problem requires a specific order. The important part is that the result contains the top K frequent elements.

Why the Min Heap Works for Top K

This part is the mental model.

Suppose the current heap holds the best K candidates seen so far. The weakest candidate among those K is at the top.

Heap Size K

weakest of top K

stronger

When Size Exceeds K

offer new candidate

poll weakest candidate

heap returns to size K

At the end, the heap contains only K elements, and those are the top K candidates.

When PriorityQueue Is Useful

Top K / Bottom K

Keep only K best candidates instead of sorting the entire input.

Merge sorted streams

Repeatedly pull the smallest current item across multiple sorted lists.

Scheduling

Process the task with the earliest time, highest priority, or smallest cost.

Graph algorithms

Dijkstra's algorithm uses a priority queue to repeatedly process the next closest node.

LeetCode Problems That Often Use PriorityQueue

These are good candidates for future separate pages:

Top K Frequent Elements
Kth Largest Element in an Array
Find Median from Data Stream
Merge K Sorted Lists
K Closest Points to Origin
Task Scheduler
Last Stone Weight
Reorganize String
Dijkstra-style shortest path problems

Common Interview Follow-Ups

Is PriorityQueue FIFO?

No. It is still a queue, but poll() removes the element with the highest priority according to the queue's ordering, not the element inserted earliest.

Is Java PriorityQueue a min heap or max heap?

By default, it behaves like a min heap for naturally ordered values. You can create max-heap behavior by using a reversed comparator.

Is the PriorityQueue fully sorted internally?

No. It only guarantees that peek() and poll() access the current head, which is the least element according to the queue's ordering.

Why use a min heap for Top K largest or Top K frequent?

Because the heap keeps only K candidates. The weakest of the current top K sits at the top, so when the heap grows beyond K, poll() removes the weakest candidate.

When should I not use PriorityQueue?

If you need a fully sorted list, sort the list. If you need fast lookup by key, use a map. PriorityQueue is best when you repeatedly need the next highest-priority item.

Final Takeaway

A PriorityQueue is a queue where the comparator defines what comes out first. Min heaps pop the smallest item first. Max heaps pop the largest item first. For Top K problems, a heap lets you avoid sorting everything and keep only the best K candidates in memory.