Algorithms and Problem Solving with Java

Heaps and `PriorityQueue

ReadingPreview

আপনি একটি free preview lesson দেখছেন।

Lesson Overview

আগের lesson-এ আমরা worklist হিসেবে ব্যবহার করেছি:

Queue
Stack
Deque

Queue বলে:

Oldest pending item first

Stack বলে:

Newest pending item first

কিন্তু কিছু problem-এ আমরা চাই:

Most important item first

Example:

Critical task
High priority task
Normal task
Low priority task

এখানে arrival order সবসময় main concern নয়।

আমাদের দরকার:

Priority-based processing

Java-তে এর জন্য গুরুত্বপূর্ণ abstraction হলো:

PriorityQueue<E>

এর ভিতরের core data-structure idea হলো:

Heap

এই lesson-এ আমরা শিখব:

What priority-based processing means
What a heap is
Complete binary tree intuition
Min Heap
Max Heap
Heap property
Heap stored inside an array
Parent and child indexes
Heap insertion
Heapify up
Heap removal
Heapify down
Heap complexity
Java PriorityQueue
Default min-priority behavior
Max-priority queues
offer()
poll()
peek()
Custom objects with Comparator
Priority scheduling
Top-K problems
Common mistakes

Why FIFO Is Not Always Enough

Suppose support tickets arrive:

Ticket A → NORMAL
Ticket B → CRITICAL
Ticket C → LOW

A normal FIFO Queue processes:

A
B
C

But the business rule may require:

CRITICAL first
then NORMAL
then LOW

So desired order:

B
A
C

This is not FIFO।

It is:

Priority ordering

What Is a Priority Queue?

A priority queue stores multiple values but removes the value considered:

highest priority

or:

lowest priority

according to an ordering rule।

It does not primarily answer:

Which item arrived first?

Instead:

Which item should be processed next
according to priority?

Java `PriorityQueue`

Java provides:

java.util.PriorityQueue

Example:

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

By default, smaller values have higher priority।

So:

numbers.offer(
        30
);

numbers.offer(
        10
);

numbers.offer(
        20
);

Then:

numbers.poll();

returns:

Important Difference from FIFO Queue

Insertion order:

30
10
20

Removal order:

10
20
30

because priority is based on natural numeric ordering।

Basic Example

import java.util.PriorityQueue;

public class Main {

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

        numbers.offer(
                30
        );

        numbers.offer(
                10
        );

        numbers.offer(
                20
        );

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

Output:

10
20
30

What Is a Heap?

A Heap is a tree-based data structure designed to efficiently maintain access to an extreme value such as:

minimum

or:

maximum

Two common types:

Min Heap
Max Heap

Min Heap

In a Min Heap:

Every parent is <= its children

Example:

The smallest value is always at the root:

Max Heap

In a Max Heap:

Every parent is >= its children

Example:

The largest value is at the root:

Heap Is Not Fully Sorted

This is extremely important।

Consider Min Heap:

This is valid because:

10 <= 20
10 <= 15
20 <= 40
20 <= 30

But notice:

is less than:

even though it appears in another branch।

A heap guarantees:

parent-child ordering

not:

complete global sorted order

Heap Property

For a Min Heap:

parent <= children

For a Max Heap:

parent >= children

That local property is enough to guarantee that the root contains the minimum or maximum value।

Complete Binary Tree

Heaps are commonly represented as:

Complete Binary Trees

A complete binary tree fills levels from:

top to bottom

and:

left to right

before starting a new level।

Example:

This is complete।

Why Completeness Matters

Because a complete binary tree can be stored efficiently inside an array without explicit child references।

Example heap:

Array representation:

[10, 20, 30, 40, 50, 60]

Heap Stored in an Array

Using zero-based indexing:

Index:  0   1   2   3   4   5
Value: 10  20  30  40  50  60

Tree:

        10(0)
       /     \
   20(1)     30(2)
   /  \       /
40(3) 50(4) 60(5)

Parent and Child Index Formulas

For index:

left child:

2 * i + 1

right child:

2 * i + 2

parent:

(i - 1) / 2

using integer division।

Example

For index:

left child:

2 * 1 + 1
= 3

right child:

2 * 1 + 2
= 4

Parent of index 4:

(4 - 1) / 2
= 3 / 2
= 1

Why Array Representation Is Useful

We do not need each heap node to store:

left reference
right reference
parent reference

The structure is implied by indexes।

That gives compact storage and good locality।

Heap Height

Because the tree remains complete, its height is approximately:

log₂ n

This is why inserting and removing from a heap can be:

O(log n)

Min Heap Insertion

Suppose heap:

Array:

[10, 20, 30, 40]

Insert:

First place it at the next available position:

But:

15 < 20

so Min Heap property is violated।

Heapify Up

Swap 15 with its parent:

Now:

10 <= 15
15 <= 40
15 <= 20

Heap property restored।

This upward repair process is often called:

heapify up

or:

sift up

Insertion Process

General Min Heap insertion:

1. Add new value at the end.
2. Compare with parent.
3. If smaller than parent, swap.
4. Continue upward.
5. Stop when heap property is satisfied.

Why Insertion Is `O(log n)`

The new value moves only upward through the tree height।

Heap height:

O(log n)

Therefore insertion:

O(log n)

Removing the Minimum

In a Min Heap, the minimum is at the root।

Suppose:

We want to remove:

If we simply remove the root, we leave a hole।

Replace Root with Last Value

Take last value:

Move it to root:

Now heap property is violated।

Heapify Down

Compare:

with children:

20
30

Choose smaller child:

Swap:

Still:

50 > 40

Swap again:

Heap restored।

Removal Process

General Min Heap removal:

1. Save root.
2. Move last element to root.
3. Remove last slot.
4. Compare root with children.
5. Swap with smaller child if necessary.
6. Continue downward.

This is:

heapify down

or:

sift down

Removal Complexity

The value may travel from root to leaf।

Tree height:

O(log n)

Therefore removal:

O(log n)

Inspecting the Root

The root is stored at index:

So reading the minimum or maximum value is:

O(1)

This is one of the most important heap properties।

Heap Complexity Summary

For a typical binary heap:

Peek root:
O(1)

Insert:
O(log n)

Remove root:
O(log n)

Compare with Sorted List

Suppose we keep a normal array fully sorted।

Finding minimum:

O(1)

But inserting into the correct middle position may require shifting many values:

O(n)

Heap allows efficient insertion:

O(log n)

while still providing immediate root access।

Heap Tradeoff

A heap is excellent when the primary requirement is:

Repeatedly get the next minimum/maximum
while values are being added and removed.

It is not designed for:

Fast arbitrary search

or:

Fully sorted traversal without removals

Java `PriorityQueue`

Java's PriorityQueue uses heap-based semantics।

Default:

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

behaves as a:

Min Priority Queue

for natural numeric ordering।

Core Operations

offer(...)
poll()
peek()

Same names we learned with Queue।

But removal order now follows:

priority

instead of:

arrival order

`offer()`

queue.offer(
        30
);

Insertion is typically:

O(log n)

`peek()`

Integer next =
        queue.peek();

returns the current highest-priority element without removing it।

For default integer ordering:

smallest value

Complexity:

O(1)

`poll()`

Integer next =
        queue.poll();

removes the highest-priority element।

Typical complexity:

O(log n)

Empty PriorityQueue

Like Queue:

peek()

returns:

null

when empty।

And:

poll()

returns:

null

when empty।

`remove()` and `element()`

The exception-based alternatives also exist:

remove()
element()

On empty queue they throw:

NoSuchElementException

For normal processing loops:

poll()
peek()

are often simpler।

Default Min Priority

Example:

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

scores.offer(
        90
);

scores.offer(
        60
);

scores.offer(
        80
);

scores.offer(
        70
);

Poll sequence:

PriorityQueue Iteration Is Not Sorted Traversal

This is a critical rule।

Suppose:

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

queue.offer(
        30
);

queue.offer(
        10
);

queue.offer(
        20
);

This:

for (
        int value
        : queue
) {
    System.out.println(
            value
    );
}

is not guaranteed to produce:

10
20
30

Heap internal iteration order is not the same as repeated priority removal order।

To Get Priority Order

Use:

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

This consumes the queue and returns values according to priority।

Preserve the PriorityQueue

If you need priority-order output but must preserve the original queue:

PriorityQueue<Integer> copy =
        new PriorityQueue<>(
                queue
        );

Then poll from:

copy

Max Priority Queue

Suppose larger integers should come first।

We need a Max Heap-like ordering।

Use:

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

Max Priority Example

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

queue.offer(
        30
);

queue.offer(
        10
);

queue.offer(
        20
);

Poll order:

30
20
10

Priority Is Defined by Comparator

A useful way to think:

Comparator decides
which value belongs at the front.

The value considered "smallest" according to the comparator becomes:

peek()

and:

poll()

result।

PriorityQueue of Objects

Suppose:

record Task(
        long id,
        String description,
        int priority
) {
}

We want smaller priority number to mean more urgent:

1 → CRITICAL
2 → HIGH
3 → NORMAL
4 → LOW

Custom Comparator

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

Example

tasks.offer(
        new Task(
                1,
                "Generate report",
                3
        )
);

tasks.offer(
        new Task(
                2,
                "Fix production outage",
                1
        )
);

tasks.offer(
        new Task(
                3,
                "Send email",
                4
        )
);

Poll order:

Fix production outage
Generate report
Send email

Complete Example

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

public class Main {

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

        tasks.offer(
                new Task(
                        1,
                        "Generate report",
                        3
                )
        );

        tasks.offer(
                new Task(
                        2,
                        "Fix production outage",
                        1
                )
        );

        tasks.offer(
                new Task(
                        3,
                        "Send welcome email",
                        4
                )
        );

        tasks.offer(
                new Task(
                        4,
                        "Investigate failed payment",
                        2
                )
        );

        while (
                !tasks.isEmpty()
        ) {
            Task task =
                    tasks.poll();

            System.out.println(
                    task.priority()
                    + " - "
                    + task.description()
            );
        }
    }

    record Task(
            long id,
            String description,
            int priority
    ) {
    }
}

Output:

1 - Fix production outage
2 - Investigate failed payment
3 - Generate report
4 - Send welcome email

Equal Priorities

Suppose two tasks both have:

priority = 1

Does PriorityQueue guarantee FIFO between them?

Do not assume so।

If equal-priority processing order matters, include a tie-breaker।

Tie-Breaker Comparator

Suppose:

record Task(
        long sequence,
        String description,
        int priority
) {
}

Use:

Comparator<Task> ordering =
        Comparator.comparingInt(
                Task::priority
        ).thenComparingLong(
                Task::sequence
        );

Now:

lower priority number first
then earlier sequence first

Why Tie-Breakers Matter

Without an explicit secondary ordering:

Equal priority values

may come out in an order you should not depend on।

If business rules require:

Critical first
and among critical tasks FIFO

encode both rules।

Priority Enum

Instead of raw numbers, a domain may use:

enum Priority {
    CRITICAL,
    HIGH,
    NORMAL,
    LOW
}

Enum natural ordering follows declaration order।

So:

Comparator.comparing(
        Task::priority
)

would prioritize:

CRITICAL
HIGH
NORMAL
LOW

if declared in that order।

Example with Enum

enum Priority {
    CRITICAL,
    HIGH,
    NORMAL,
    LOW
}

Task:

record Task(
        long sequence,
        String description,
        Priority priority
) {
}

Comparator:

Comparator<Task> ordering =
        Comparator.comparing(
                Task::priority
        ).thenComparingLong(
                Task::sequence
        );

This is clearer than magic numbers such as:

Priority Queue Is Not a Sorted List

This distinction is essential।

A PriorityQueue guarantees:

The next highest-priority item
is available efficiently.

It does not guarantee:

Every element is stored in globally sorted sequence.

When to Use PriorityQueue

Use it when the recurring operation is:

Add item
Get best-priority item
Remove best-priority item
Repeat

Examples:

Job scheduling
Event simulation
Top-K tracking
Shortest-path algorithms
Merging sorted streams
Task prioritization

When Not to Use PriorityQueue

If you need:

Fast search by ID

use something like:

Map

If you need:

Unique membership

use:

Set

If you need:

Fully sorted random-access list

a sorted collection/list approach may be more appropriate।

Searching a PriorityQueue

Suppose:

queue.contains(
        value
);

A heap is not optimized for arbitrary lookup।

contains() may require scanning values:

O(n)

Do not confuse:

fast access to root

with:

fast access to every value

Removing an Arbitrary Value

Removing:

queue.poll()

removes the root efficiently:

O(log n)

But removing a specific arbitrary object may first require locating it:

O(n)

and then repairing the heap।

So PriorityQueue is optimized around:

the head

not arbitrary positions।

Top-K Problems

A very common heap use case is:

Keep the K largest or smallest values
while processing many values.

Suppose we have millions of scores but only need:

Top 3

We do not necessarily need to sort every value।

Top 3 Largest Values

We can maintain a Min Heap of at most:

3 values

Why Min Heap?

Because among the current top 3, we need fast access to:

the smallest of those top 3

so we can replace it when a better candidate arrives।

Example Algorithm

Values:

Keep heap size:

Process each value:

Add value

If heap size > 3:
    remove smallest

At the end, the heap contains the three largest values।

Top-K Implementation

static PriorityQueue<Integer> topLargest(
        int[] values,
        int k
) {
    if (
            k <= 0
    ) {
        throw new IllegalArgumentException(
                "k must be positive."
        );
    }

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

    for (
            int value
            : values
    ) {
        heap.offer(
                value
        );

        if (
                heap.size() > k
        ) {
            heap.poll();
        }
    }

    return heap;
}

Why This Works

Suppose heap contains:

70
90
100

The root is:

which is the weakest member of the current top three।

If new value:

arrives:

Remove minimum:

Remaining:

80
90
100

Exactly the new top three।

Top-K Complexity

For each of n values:

offer into heap of size at most k

cost:

O(log k)

Possibly:

poll

also:

O(log k)

Total:

O(n log k)

Space:

O(k)

Compare with Full Sorting

Sort all n values:

O(n log n)

then take top k।

Heap approach:

O(n log k)

When:

k << n

this can be much more efficient।

Example

Suppose:

n = 10,000,000
k = 10

A heap only stores:

10 values

while scanning the entire dataset।

This is a very useful streaming-style technique।

Top K Smallest

To keep the k smallest values, use a Max Heap of size k।

Why?

Because among the current smallest k, you want the largest candidate at the root so it can be removed when a better smaller value arrives।

Max Heap for K Smallest

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

Process:

heap.offer(
        value
);

if (
        heap.size() > k
) {
    heap.poll();
}

Now the heap retains the smallest k values।

Choosing Min Heap vs Max Heap for Top-K

This often confuses beginners।

Remember:

Need K largest
→ maintain Min Heap of size K

Need K smallest
→ maintain Max Heap of size K

Why?

Because the root should be:

the easiest current candidate to discard.

Priority Scheduling

Suppose a worker processes:

CRITICAL
HIGH
NORMAL
LOW

A PriorityQueue is a natural in-memory scheduling structure।

But real distributed job processing introduces additional concerns:

Durability
Concurrency
Retries
Fairness
Starvation
Multiple consumers
Persistence

A Java PriorityQueue alone does not solve these।

Starvation

Priority scheduling can create a problem।

Suppose high-priority tasks arrive continuously।

Low-priority tasks may wait indefinitely।

This is called:

starvation

Priority algorithms often need fairness rules such as:

aging
quotas
priority adjustment

depending on the system।

Heap Sort Connection

A heap can also be used to sort data।

Conceptually:

Build heap
Repeatedly remove root

If using a Min Heap:

poll repeatedly

produces ascending order।

PriorityQueue-Based Sort

static int[] heapSortedCopy(
        int[] values
) {
    PriorityQueue<Integer> queue =
            new PriorityQueue<>();

    for (
            int value
            : values
    ) {
        queue.offer(
                value
        );
    }

    int[] result =
            new int[
                    values.length
            ];

    for (
            int i = 0;
            i < result.length;
            i++
    ) {
        result[i] =
                queue.poll();
    }

    return result;
}

Complexity

Insert n values individually:

O(n log n)

Poll n values:

O(n log n)

Overall:

O(n log n)

Extra space:

O(n)

Is This Java's Heap Sort?

Not exactly।

This demonstrates heap-based sorting using PriorityQueue, but a traditional in-place Heap Sort works directly inside an array and has different space characteristics।

We do not need to implement full Heap Sort in this course।

Building a Heap

A heap can be built from existing data more efficiently than inserting each value one by one using specialized heap-construction techniques।

That operation can be:

O(n)

rather than:

O(n log n)

for repeated insertion।

This is a deeper heap detail。

For now, understand that heap construction can be optimized beyond naive repeated insertion।

Heap Is Not a Binary Search Tree

Both are trees, but their guarantees are different।

Heap:

Parent-child priority relationship

Binary Search Tree:

Left values ordered relative to node
Right values ordered relative to node

A heap is optimized for:

minimum/maximum access

A Binary Search Tree is designed for different searching and ordering operations।

We'll study BST fundamentals later।

Heap vs Sorted Array

Heap

peek best:
O(1)

insert:
O(log n)

remove best:
O(log n)

arbitrary search:
O(n)

Sorted Array

binary search:
O(log n)

best element:
O(1)

insert while preserving sort:
O(n)

Different structures optimize different operations।

Heap vs HashMap

Heap:

What is highest-priority item?

HashMap:

What value belongs to this key?

Do not choose one based only on which complexity sounds faster।

They solve different access problems।

Heap vs Queue

Queue:

Arrival order

PriorityQueue:

Priority order

Example:

Arrival:
A(priority 5)
B(priority 1)
C(priority 3)

FIFO Queue:

A
B
C

PriorityQueue:

B
C
A

assuming smaller number means higher priority।

Heap vs Stack

Stack:

Most recently added first

PriorityQueue:

Best according to comparator first

Again, different processing policies।

PriorityQueue and Null

PriorityQueue does not permit:

null

Do not insert null values।

Priority comparison requires meaningful elements।

Mutable Priority Fields Are Dangerous

Suppose:

record Task(
        ...
)

is replaced by a mutable class and you change its priority after insertion।

Example conceptually:

Task inserted with priority 5
↓
priority changed to 1

The PriorityQueue does not automatically know that its heap ordering must be repaired।

Important Rule

Do not mutate fields that affect ordering while an object is stored inside a PriorityQueue।

Safer approach:

Remove object
Change ordering field
Insert again

or use immutable queued values।

Comparator Must Be Consistent Enough

A comparator should define predictable ordering।

Bad comparator behavior such as:

A < B
B < C
C < A

can make sorting and priority behavior unreliable।

Comparators should follow a coherent ordering contract।

Common Mistake 1 — Expecting FIFO

PriorityQueue is not a normal FIFO Queue।

Insertion order does not determine processing order।

Common Mistake 2 — Thinking Iteration Is Sorted

This:

for (
        T value
        : priorityQueue
)

does not guarantee priority-sorted traversal।

Use repeated:

poll()

for priority order।

Common Mistake 3 — Forgetting Default Is Min Priority

new PriorityQueue<Integer>()

returns smaller numbers first।

If larger number means higher priority, use:

Comparator.reverseOrder()

Common Mistake 4 — Equal Priority Without Tie-Breaker

If equal-priority FIFO behavior matters, encode arrival sequence explicitly।

Do not rely on unspecified ordering।

Common Mistake 5 — Using PriorityQueue for Arbitrary Search

The root is fast।

Searching arbitrary elements is not।

Use the data structure that matches the access pattern।

Common Mistake 6 — Thinking Heap Is Fully Sorted

Only the root and parent-child relationships are guaranteed।

Internal representation is not a sorted sequence।

Common Mistake 7 — Mutating Priority After Insertion

Changing ordering fields while an item remains inside the PriorityQueue can invalidate expected ordering behavior।

Common Mistake 8 — Wrong Heap for Top-K

Remember:

K largest
→ Min Heap size K

K smallest
→ Max Heap size K

Common Mistake 9 — Treating Priority as Complete Scheduling

A PriorityQueue solves in-memory ordering।

It does not automatically solve:

Retries
Persistence
Concurrency
Distributed ownership
Fairness

Common Mistake 10 — Ignoring Starvation

Always processing highest priority can leave low-priority work waiting indefinitely।

Priority systems may need fairness policies।

Practical Example — Priority Enrollment Review

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

public class Main {

    public static void main(String[] args) {
        PriorityQueue<ReviewRequest> requests =
                new PriorityQueue<>(
                        Comparator.comparing(
                                ReviewRequest::priority
                        ).thenComparingLong(
                                ReviewRequest::sequence
                        )
                );

        requests.offer(
                new ReviewRequest(
                        1,
                        "Sakib",
                        Priority.NORMAL
                )
        );

        requests.offer(
                new ReviewRequest(
                        2,
                        "Subu",
                        Priority.CRITICAL
                )
        );

        requests.offer(
                new ReviewRequest(
                        3,
                        "Sumu",
                        Priority.HIGH
                )
        );

        requests.offer(
                new ReviewRequest(
                        4,
                        "Nur",
                        Priority.CRITICAL
                )
        );

        while (
                !requests.isEmpty()
        ) {
            ReviewRequest request =
                    requests.poll();

            System.out.println(
                    request.priority()
                    + " - "
                    + request.learner()
            );
        }
    }

    enum Priority {
        CRITICAL,
        HIGH,
        NORMAL,
        LOW
    }

    record ReviewRequest(
            long sequence,
            String learner,
            Priority priority
    ) {
    }
}

Output:

CRITICAL - Subu
CRITICAL - Nur
HIGH - Sumu
NORMAL - Sakib

Among equal CRITICAL requests:

sequence

preserves the intended order।

Practice 1 — Default PriorityQueue

Given:

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

queue.offer(
        30
);

queue.offer(
        10
);

queue.offer(
        20
);

What does:

queue.peek()

return?

Answer

Practice 2 — Poll Order

For the same queue, repeated poll() returns:

Answer

10
20
30

Practice 3 — Max PriorityQueue

Create a PriorityQueue where larger integers come first।

Solution

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

Practice 4 — Heap Property

Is this a valid Min Heap?

Answer

Yes।

Every parent is less than or equal to its children।

Practice 5 — Not Fully Sorted

Is this valid Min Heap?

        5
       / \
     20   10

Answer

Yes।

The structure does not require:

20 <= 10

because they are siblings।

Only parent-child relationships matter।

Practice 6 — Complexity

Heap root inspection:

Answer

O(1)

Practice 7 — Complexity

Heap insertion:

Answer

O(log n)

Practice 8 — Complexity

Removing heap root:

Answer

O(log n)

Practice 9 — Top 10 Largest

Which bounded heap should be maintained?

Answer

Min Heap of size 10

because the smallest member of the current top 10 should be easiest to discard।

Practice 10 — Top 10 Smallest

Which heap?

Answer

Max Heap of size 10

Practice 11 — Equal Priority

Two tasks have the same priority and FIFO ordering between them matters।

What should you add?

Answer

A secondary ordering such as:

sequence number
creation time

and include it with:

thenComparing(...)

Practice 12 — Choose Structure

Need:

Fast ID → Course lookup

PriorityQueue or HashMap?

Answer

HashMap

PriorityQueue is designed around priority access, not key lookup।

Practice 13 — Iteration

Does iterating a PriorityQueue guarantee sorted output?

Answer

No।

Practice 14 — Mutation

Why is changing a queued object's priority dangerous?

Answer

Because the queue's internal heap structure was built using the old ordering value and is not automatically repaired after arbitrary field mutation।

True or False

PriorityQueue always follows FIFO.
Java's default PriorityQueue<Integer> returns smaller values first.
A heap is always globally sorted.
A Min Heap keeps its minimum at the root.
A Max Heap keeps its maximum at the root.
Heap insertion is typically O(log n).
Heap root inspection is O(1).
Heap root removal is typically O(log n).
Iterating a PriorityQueue guarantees priority order.
poll() removes the current priority head.
Comparator.reverseOrder() can create max-style integer priority.
PriorityQueue allows null.
Top-K problems are a common heap use case.
K largest values can be maintained using a Min Heap of size K.
Arbitrary PriorityQueue search is optimized to O(log n).

Answers

1. False
2. True
3. False
4. True
5. True
6. True
7. True
8. True
9. False
10. True
11. True
12. False
13. True
14. True
15. False

Knowledge Check

Question 1

What problem does a PriorityQueue solve?

Question 2

What is a Min Heap?

Question 3

What is a Max Heap?

Question 4

Why does a heap not need to be completely sorted?

Question 5

Why can heap insertion be O(log n)?

Question 6

How is the root removed while preserving the complete-tree structure?

Question 7

What is heapify up?

Question 8

What is heapify down?

Question 9

What does Java's default PriorityQueue<Integer> prioritize?

Question 10

Why is PriorityQueue iteration not necessarily sorted?

Question 11

Why is a Min Heap useful for finding the K largest values?

Question 12

Why should ordering fields generally remain unchanged while an item is inside a PriorityQueue?

Knowledge Check Answers

Answer 1

A PriorityQueue efficiently stores pending items and provides access to the next item according to an ordering or priority rule rather than simple arrival order।

Answer 2

A Min Heap is a complete binary tree where each parent is less than or equal to its children, making the minimum value available at the root।

Answer 3

A Max Heap is a complete binary tree where each parent is greater than or equal to its children, making the maximum value available at the root।

Answer 4

The primary requirement is only that the best-priority value stays at the root and that parent-child heap relationships remain valid. Full global ordering would require unnecessary additional work।

Answer 5

A new element is added at the bottom and can move upward only along one path whose length is proportional to the heap height:

O(log n)

Answer 6

The root is saved, the final heap element is moved into the root position, the last slot is removed, and the replacement value is moved downward until heap order is restored।

Answer 7

Heapify up moves a newly inserted element upward by comparing and swapping with its parent until the heap property is restored।

Answer 8

Heapify down moves a replacement root downward by comparing and swapping with the appropriate child until heap order is restored।

Answer 9

Natural ascending ordering, so the smallest integer has the highest removal priority।

Answer 10

The heap only guarantees the priority element at the root and valid parent-child relationships. Its internal array is not a fully sorted representation।

Answer 11

The heap stores only K candidates, and its root represents the smallest value among the current K largest. A new larger candidate can replace that weakest member efficiently।

Answer 12

Because PriorityQueue does not automatically reorganize itself when an object's comparison-relevant state changes after insertion।

Practical Decision Guide

Use:

Queue

when:

Oldest work should be processed first.

Use:

Deque as Stack

when:

Newest work should be processed first.

Use:

PriorityQueue

when:

Best-priority work should be processed first.

Use:

HashMap

when:

Lookup by key is the main operation.

Use:

HashSet

when:

Fast membership checking is the main operation.

Heap Complexity Cheat Sheet

For a binary heap:

peek root
→ O(1)

insert
→ O(log n)

remove root
→ O(log n)

arbitrary search
→ O(n)

Top-K with a bounded heap:

Time
→ O(n log k)

Space
→ O(k)

Core Mental Model

A Queue asks:

Who arrived first?

A Stack asks:

Who arrived last?

A PriorityQueue asks:

Who is most important according
to the ordering rule?

And a Heap makes that last question efficient by maintaining:

the best-priority value at the root
without fully sorting everything.

Lesson Summary

এই lesson-এ আমরা heap এবং priority-based processing-এর foundation শিখেছি।

We learned:

PriorityQueue processes according to priority rather than arrival order
A heap is a complete binary tree with a parent-child ordering property
Min Heap keeps the minimum at the root
Max Heap keeps the maximum at the root
A heap is not globally sorted
Complete binary trees can be efficiently stored in arrays
Parent and child positions can be calculated from indexes
Insertion adds at the end and uses heapify up
Root removal replaces the root with the last value and uses heapify down
Heap root access is O(1)
Heap insertion and root removal are O(log n)
Java's PriorityQueue uses heap-style priority semantics
Default PriorityQueue<Integer> returns smaller values first
Max-style priority can be created with a reversed comparator
Custom objects can use Comparator
Equal-priority ordering should use an explicit tie-breaker when required
PriorityQueue iteration is not guaranteed to be sorted
Arbitrary lookup is not what a heap optimizes
Top-K problems can be solved efficiently with bounded heaps
K largest typically uses a Min Heap of size K
K smallest typically uses a Max Heap of size K
Mutable priority fields can break expected queue ordering
Priority scheduling may need fairness rules to avoid starvation

The central heap idea is:

Do not fully sort everything.

Maintain just enough structure
to know which item should come next.

Next Lesson

পরবর্তী lesson:

Hashing and Fast Lookup

আমরা শিখব:

What hashing means
Hash functions
Hash tables
Buckets
Collisions
HashMap
HashSet
Average O(1) lookup
Worst-case intuition
Load factor and resizing intuition
equals() and hashCode()
Why equal objects need equal hash codes
Mutable keys
Hash-based duplicate detection
Fast membership and key-based lookup
When hashing is better than linear or binary search

Lesson Overview

Why FIFO Is Not Always Enough

What Is a Priority Queue?

Java PriorityQueue

Important Difference from FIFO Queue

Basic Example

What Is a Heap?

Min Heap

Max Heap

Heap Is Not Fully Sorted

Heap Property

Complete Binary Tree

Why Completeness Matters

Heap Stored in an Array

Parent and Child Index Formulas

Example

Why Array Representation Is Useful

Heap Height

Min Heap Insertion

Heapify Up

Insertion Process

Why Insertion Is O(log n)

Removing the Minimum

Replace Root with Last Value

Heapify Down

Removal Process

Removal Complexity

Inspecting the Root

Heap Complexity Summary

Compare with Sorted List

Heap Tradeoff

Java PriorityQueue

Core Operations

offer()

peek()

poll()

Empty PriorityQueue

remove() and element()

Default Min Priority

PriorityQueue Iteration Is Not Sorted Traversal

To Get Priority Order

Preserve the PriorityQueue

Max Priority Queue

Max Priority Example

Priority Is Defined by Comparator

PriorityQueue of Objects

Custom Comparator

Example

Complete Example

Equal Priorities

Tie-Breaker Comparator

Why Tie-Breakers Matter

Priority Enum

Example with Enum

Priority Queue Is Not a Sorted List

When to Use PriorityQueue

When Not to Use PriorityQueue

Searching a PriorityQueue

Removing an Arbitrary Value

Top-K Problems

Top 3 Largest Values

Example Algorithm

Top-K Implementation

Why This Works

Top-K Complexity

Compare with Full Sorting

Example

Top K Smallest

Max Heap for K Smallest

Choosing Min Heap vs Max Heap for Top-K

Priority Scheduling

Starvation

Heap Sort Connection

PriorityQueue-Based Sort

Complexity

Is This Java's Heap Sort?

Building a Heap

Heap Is Not a Binary Search Tree

Heap vs Sorted Array

Heap

Java `PriorityQueue`

Why Insertion Is `O(log n)`

Java `PriorityQueue`

`offer()`

`peek()`

`poll()`

`remove()` and `element()`