How PriorityQueue Works Internally in Java?

1. Introduction

A PriorityQueue in Java is a specialized queue data structure where elements are arranged according to their priority rather than their insertion order. Unlike a regular Queue (which follows FIFO – First In, First Out), a PriorityQueue always ensures that the head of the queue is the element with the highest priority (or the smallest element in natural ordering).

It belongs to the java.util package and was introduced in Java 1.5.

Key Characteristics

Implements: Queue<E> interface.
Internal structure: Uses a binary heap.
Default behavior: Min-Heap (smallest element has the highest priority).
Thread safety: Not synchronized (use PriorityBlockingQueue for concurrent access).
Null elements: Not allowed.
Ordering: Natural ordering (via Comparable) or custom ordering (via Comparator).

2. Internal Data Structure: Binary Heap

The core of PriorityQueue is a binary heap, represented using a dynamic array (Object[] queue internally).

A binary heap is a complete binary tree with the following properties:

Completeness:
Every level, except possibly the last, is completely filled.
The last level is filled from left to right.
Heap Property:
For a min-heap, each parent node is less than or equal to its children.
Thus, the smallest element always resides at the root (index 0).

Array Representation

The heap is stored as an array such that:

For an element at index i:

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

This eliminates the need for explicit tree nodes — everything is handled efficiently using array indices.

Example Heap (Min-Heap)

If we insert: [10, 5, 20, 3, 8]

The binary tree looks like:

And internally stored as array:

[3, 5, 20, 10, 8]

3. Constructors

PriorityQueue offers multiple constructors:

PriorityQueue();                          // Natural ordering, default capacity (11)
PriorityQueue(int initialCapacity);       // Custom capacity
PriorityQueue(Comparator<? super E> c);   // Custom comparator
PriorityQueue(Collection<? extends E> c); // Initialize from another collection

4. Internal Fields (from JDK source)

transient Object[] queue;   // The heap array
private int size = 0;       // Current number of elements
private final Comparator<? super E> comparator; // For custom ordering

The queue array is the heap container, and size tracks the number of active elements.

5. How Insertion Works (`add()` / `offer()`)

When you call add(E e) or offer(E e):

Step 1: Add Element at the End

The element is first added to the end of the heap array (the bottom-most, right-most position).

Step 2: Heapify-Up (Sift-Up)

To maintain the heap property:

Compare the new element with its parent.
If the new element is smaller than the parent (for a min-heap), swap them.
Repeat this process until the element is in the correct position or becomes the root.

Pseudocode:

offer(e):
    queue[size] = e
    siftUp(size)
    size++

Example:

Inserting elements [10, 5, 20, 3]

Step	Operation	Heap Array	Explanation
1	Insert 10	[10]	First element, no parent
2	Insert 5	[10, 5] → swap → [5, 10]	5 < 10
3	Insert 20	[5, 10, 20]	Heap valid
4	Insert 3	[5, 10, 20, 3] → swap → [3, 5, 20, 10]	3 < 5

Time Complexity: O(log n)

Internal Method (JDK Source Simplified)

private void siftUp(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}

6. How Removal Works (`poll()`)

When you call poll(), it removes and returns the root element — the smallest element in a min-heap.

Step 1: Remove the Root

The element at index 0 (root) is removed.

Step 2: Move Last Element to Root

The last element in the array is moved to the root position.

Step 3: Heapify-Down (Sift-Down)

Compare the new root with its children.
Swap it with the smaller child if it violates the heap property.
Continue until the heap property is restored.

Example:

Heap before poll(): [3, 5, 20, 10]

Remove root (3).
Move last element (10) to root → [10, 5, 20]
Compare 10 with children: smallest child = 5
Swap → [5, 10, 20]

Resulting heap after poll: [5, 10, 20]

Time Complexity: O(log n)

Internal Method (JDK Source Simplified)

private void siftDown(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    int half = size >>> 1; // loop while node has at least one child
    while (k < half) {
        int child = (k << 1) + 1; // left child
        Object c = queue[child];
        int right = child + 1;
        if (right < size && ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right];
        if (key.compareTo((E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = key;
}

7. Peeking (`peek()`)

peek() simply returns the element at index 0, i.e., the root element of the heap (the smallest element).

Time Complexity: O(1)

8. Removing a Specific Element (`remove(Object o)`)

If you remove an arbitrary element:

It first finds the element via linear search (O(n)).
Swaps it with the last element.
Decreases the size.
Calls sift-down or sift-up to restore heap order.

Time Complexity: O(n)

9. Heap Construction (Bulk Initialization)

When a collection is passed in the constructor:

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 10, 2, 8));

It calls heapify() once instead of inserting elements one-by-one.

heapify() algorithm (Floyd’s method):

Starts from the last non-leaf node and calls siftDown for each node.
Builds a heap in O(n) time.

10. Internal Array Growth Strategy

Default capacity = 11
When full, grows using the formula:

newCapacity = oldCapacity + (oldCapacity < 64 ? (oldCapacity + 2)
                                              : (oldCapacity >> 1));

That means:

If capacity < 64 → approximately doubles.
Otherwise → grows by 50%.

This ensures efficient memory utilization.

11. Time Complexity Summary

Operation	Average	Worst	Description
`offer()` / `add()`	O(log n)	O(log n)	Insert and heapify-up
`poll()`	O(log n)	O(log n)	Remove min and heapify-down
`peek()`	O(1)	O(1)	Access root element
`remove(Object)`	O(n)	O(n)	Linear search + heapify
`contains(Object)`	O(n)	O(n)	Linear search
`size()`	O(1)	O(1)	Returns count

12. Max-Heap Implementation

By default, PriorityQueue is a min-heap.
To make it a max-heap, pass a reverse comparator:

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

Now the largest element becomes the root.

13. Practical Example

import java.util.*;

public class PriorityQueueDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.add(10);
        pq.add(5);
        pq.add(20);
        pq.add(3);

        System.out.println("Internal Heap: " + pq);
        System.out.println("Peek (smallest): " + pq.peek());

        while (!pq.isEmpty()) {
            System.out.println("Poll: " + pq.poll());
            System.out.println("Heap now: " + pq);
        }
    }
}

Output:

Internal Heap: [3, 5, 20, 10]
Peek (smallest): 3
Poll: 3
Heap now: [5, 10, 20]
Poll: 5
Heap now: [10, 20]
Poll: 10
Heap now: [20]
Poll: 20
Heap now: []

14. Use Cases

Dijkstra’s Shortest Path Algorithm
To extract the node with minimum distance repeatedly.
Huffman Coding Algorithm
To build optimal prefix trees.
Task Scheduling Systems
Execute high-priority tasks first.
A* Search Algorithm
For optimal pathfinding in AI.
Median Maintenance
With two heaps (min and max).

15. Differences Between PriorityQueue and Other Collections

Feature	PriorityQueue	TreeSet	ArrayList	LinkedList
Order	Priority-based	Sorted order	Insertion order	Insertion order
Duplicates	Allowed	Not allowed	Allowed	Allowed
Nulls	Not allowed	Not allowed	Allowed	Allowed
Thread-safe	No	No	No	No
Internal Structure	Binary Heap	Red-Black Tree	Dynamic Array	Doubly Linked List

16. Summary

Aspect	Description
Implementation	Binary Min-Heap
Backing Array	`Object[] queue`
Default Capacity	11
Thread Safety	Not synchronized
Ordering	Natural or custom (`Comparator`)
Null Elements	Not allowed
Root Element	Smallest (min-heap) or largest (max-heap)
Time Complexity	O(log n) for insert/remove
Typical Use Case	Retrieve smallest/largest element quickly

Final Thoughts

The PriorityQueue in Java is one of the most efficient implementations of a binary heap available.
It’s optimized for scenarios where frequent access to the smallest or largest element is required, rather than full sorting.
It provides O(log n) insertion and removal, O(1) access to the top priority element, and a dynamic array-based heap that grows intelligently with data.

How PriorityQueue Works Internally in Java?

1. Introduction

Key Characteristics

2. Internal Data Structure: Binary Heap

Array Representation

Example Heap (Min-Heap)

3. Constructors

4. Internal Fields (from JDK source)

5. How Insertion Works (add() / offer())

Step 1: Add Element at the End

Step 2: Heapify-Up (Sift-Up)

Pseudocode:

Example:

Internal Method (JDK Source Simplified)

6. How Removal Works (poll())

Step 1: Remove the Root

Step 2: Move Last Element to Root

Step 3: Heapify-Down (Sift-Down)

Example:

Internal Method (JDK Source Simplified)

7. Peeking (peek())

8. Removing a Specific Element (remove(Object o))

9. Heap Construction (Bulk Initialization)

10. Internal Array Growth Strategy

11. Time Complexity Summary

12. Max-Heap Implementation

13. Practical Example

14. Use Cases

15. Differences Between PriorityQueue and Other Collections

16. Summary

Final Thoughts

5. How Insertion Works (`add()` / `offer()`)

6. How Removal Works (`poll()`)

7. Peeking (`peek()`)

8. Removing a Specific Element (`remove(Object o)`)