Understanding Priority Queues in Java

Hey everyone!
In this post, I’m sharing what I learned about Priority Queues from my Coding Ninjas course. I’m keeping it simple and using my own words.

What is a Priority Queue?
A priority queue is a data structure where each element has a priority.
The element with the highest priority is removed first.
If two elements have the same priority, they are served in the order they were inserted.

Time Complexity of Priority Queue Operations

• Insertion: O(log N)
• Deletion: O(log N)
• Access Min/Max (peek): O(1)

How to Implement Priority Queue in Java
Java provides a built-in class PriorityQueue which is based on a heap — a special kind of binary tree.

Declaration:

PriorityQueue pq = new PriorityQueue<>(); // min heap by default
PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // max heap

Basic Operations

• peek() — returns the top element without removing it
• poll() — removes and returns the top element
• add() — inserts an element

Max Heap and Min Heap

Min heap: The smallest number is at the root.

Max heap: The largest number is at the root.

Priority Queue Operations Summary

• Insert
• Get Max or Get Min
• Remove Max or Remove Min

How a Heap Works
A heap is a complete binary tree — all levels are filled except maybe the last, which is filled from left to right.

The heap order property means:

1. In a min heap, every parent is less than or equal to its children.
2. In a max heap, every parent is greater than or equal to its children.

Array Representation of a Heap

1. Parent index = (i - 1) / 2
2. Left child index = 2 * i + 1
3. Right child index = 2 * i + 2

Insertion and Heapify

• New elements are added at the end of the heap (array).
• To maintain the heap property, we heapify:
  • Compare the new element with its parent.
  • If the heap property is broken, swap and repeat up the tree.

Heap Sort and Complexity
Heap sort uses a heap to sort elements:

• Build a heap from the data (O(n))
• Repeatedly extract the max or min element and place it at the end
• Total time complexity: O(n log n)
• Space complexity: O(1) (in-place sorting)

Java PriorityQueue Functionalities

• add()/offer() — add elements (O(log n))
• peek() — look at the smallest element without removing it (O(1))
• poll() — remove and return the smallest element (O(log n))
• isEmpty() — check if the queue is empty (O(1))

Example Problem: K Largest Elements
Here is a simple Java program using a min heap to find the k largest elements in an array:

Coding:
import java.util.*;

public class Solution {
public static ArrayList kLargest(int input[], int k) {
PriorityQueue pq = new PriorityQueue<>();
for (int num : input) {
pq.add(num);
if (pq.size() > k) {
pq.poll();
}
}
ArrayList result = new ArrayList<>(pq);
Collections.sort(result);
return result;
}
}
Explanation:
The goal is to find the k largest numbers from an array of numbers.
Example:

Input array: [3, 1, 5, 12, 2, 11]
k = 3

Start with an empty min heap.

Add 3 → heap = [3]

Add 1 → heap = [1, 3]

Add 5 → heap = [1, 3, 5]

Add 12 → heap = [1, 3, 5, 12] → size > 3, remove smallest (1) → heap = [3, 12, 5]

Add 2 → heap = [2, 3, 5, 12] → size > 3, remove smallest (2) → heap = [3, 12, 5]

Add 11 → heap = [3, 11, 5, 12] → size > 3, remove smallest (3) → heap = [5, 11, 12]

At the end, the heap contains [5, 11, 12] — the 3 largest numbers.

That’s all for now! Hope I have did my best in understanding this concept .This simple explanation helps you understand priority queues better.
Thanks for reading!!