منشورBEG-042-L05

الكومات (Heaps) وPriorityQueue

الدرس 5 من 6
12 دقيقة قراءة
مبتدئ

في هذا الدرس 11 موضوعات

Lesson Overview
Learning Objectives
Written Explanation
Examples
Backend Insight
Common Mistakes
Exercises
Mini Challenge
Summary & Next Lesson
References
التطبيق

هذا الدرس متاح حاليًا باللغة الإنجليزية فقط، ولم تُنشر نسخته العربية بعد.

Lesson Overview

A binary search tree answers "is this value here?" and "what are all the values in order?". Sometimes you need something much narrower: "what is the next most urgent item?" A hospital emergency desk and a task scheduler both work this way: the next one served is the most urgent, not the first to arrive.

The structure built for this question is the heap, and Java ships one as the PriorityQueue class. A heap is also a binary tree, but with a different rule than a BST. It does not keep everything sorted. It keeps only enough order to hand you the smallest item instantly, and that is cheaper to maintain.

By the end of this lesson you will be able to trace a min-heap by hand, use PriorityQueue with natural order and with your own Comparator, and tell a heap from a BST.

Why this matters: priority queues sit inside schedulers, job systems, "top k" reports, and shortest-path algorithms. They are a daily tool.

This lesson builds on Lessons 1 to 4 (trees, height, balance), on Queue and PriorityQueue from the collections module, and on Comparator and method references from the sorting and lambdas modules.

Learning Objectives

By the end of this lesson you will be able to:

State the min-heap rule and explain that a heap is not a sorted structure.
Describe how a heap is stored in an array, with parent and child positions.
Trace add (sift up) and poll (sift down) on a small heap.
Use PriorityQueue with add, peek, poll, and a Comparator.
Give the cost of peek, add, poll, and contains.
Name two differences between a heap and a BST, and say why iterating or printing a PriorityQueue is not sorted.

Written Explanation

The min-heap rule

A min-heap is a binary tree with two properties:

Shape: it is a complete binary tree. Every level is full except possibly the last, and the last level is filled from the left, with no gaps.
Order: every node's value is less than or equal to its children's values.

The consequence: the smallest value is always at the root. Nothing else is promised. Siblings are in no particular order, and a node in one subtree can be larger or smaller than a node in another. This is a partial order. A max-heap is the mirror image.

text

This is a valid min-heap. Check each parent: 2 is at most 5 and 6; 5 is at most 8 and 7. Note that 8 and 7 are not in sorted order, and 6 (right of the root) is larger than 5 but smaller than 8, which sits in the other subtree. A BST would reject this shape. A heap does not care.

Stored in an array

Because the shape is complete, there are no gaps, so a heap fits neatly into an array with no node objects and no references. Read the tree above level by level, left to right, and you get [2, 5, 6, 8, 7].

With positions counted from 0, a node at position i has:

left child at 2*i + 1,
right child at 2*i + 2,
parent at (i - 1) / 2 (integer division).

For [2, 5, 6, 8, 7], position 1 (value 5) has children at positions 3 and 4 (values 8 and 7), and its parent is position 0. Position arithmetic replaces pointers. This is the representation the OpenDSA textbook uses.

Adding: sift up

To add a value, place it in the first free position at the end of the array (so the shape stays complete). It might be smaller than its parent, which would break the order. So compare it with its parent and swap upward while it is smaller. It stops when the parent is not larger or when it reaches the root. A value moves up at most one step per level, so the cost is at most the height: O(log n).

Removing the smallest: sift down

The smallest value is at position 0. To poll it:

Save the root value to return.
Move the last element of the array into position 0 and shrink the array by one (the shape stays complete).
That element is probably too large for the top. Compare it with its two children and swap with the smaller child. Repeat until it is not larger than its children or it is a leaf.

Again, at most one step per level: O(log n). Looking at the smallest without removing it (peek) just reads position 0: O(1).

PriorityQueue in Java

java.util.PriorityQueue is a queue built on this heap. The JDK documentation says that the head of the queue is the least element with respect to the ordering. The ordering is the natural one (Comparable, such as numbers and strings) or a Comparator passed to the constructor. Its documented costs:

Operation	Cost
`peek()`, `size()`	O(1)
`add(x)` / `offer(x)`	O(log n)
`poll()`	O(log n)
`contains(x)`, `remove(x)`	O(n)

It does not accept null (it throws NullPointerException), and poll() and peek() return null when the queue is empty.

java

PriorityQueue<Integer> pq = new PriorityQueue<>();            // min-heap
PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());   // max-heap

The big surprise: it is not sorted

The documentation is clear that the iterator does not visit elements in any particular order. Printing a PriorityQueue shows the internal array, which looks nearly sorted but is not. Only repeated poll() hands the items out in order. If you need sorted output, drain the queue or use a different structure.

Heap versus BST

	BST	Heap
Rule	left smaller, right larger	parent at most children
Smallest item	follow left links, O(height)	at the root, O(1)
Find an arbitrary value	O(height)	O(n), no useful order for search
Sorted output	in-order traversal	drain by repeated `poll`
Storage	linked nodes	array

Pick a heap when you only ever need the extreme item. Pick a BST (TreeMap) when you need to search or walk in order.

Examples

Example 1: a heap by hand (simple)

Add 8, 5, 6, 2, 7 to an empty min-heap, then poll twice. The arrays below are what a real PriorityQueue printed on JDK 21. Its internal array is an implementation detail, so treat it as a teaching aid, not a contract.

text

add 8 -> [8]
add 5 -> [5, 8]
add 6 -> [5, 8, 6]
add 2 -> [2, 5, 6, 8]
add 7 -> [2, 5, 6, 8, 7]

Adding 5 puts it at position 1 under 8, and it swaps up. Adding 6 stays, since 5 is smaller. Adding 2 lands at position 3 under 8: it swaps with 8, then with 5. Adding 7 lands at position 4 under 5, which is smaller, so it stays.

Now poll. The root 2 is returned. The last value (7) moves to the root: [7, 5, 6, 8]. Its children are 5 and 6; swap with the smaller, 5: [5, 7, 6, 8]. Position 1 now has one child, 8, and 7 is not larger, so it stops. The second poll returns 5 and leaves [6, 7, 8]. Real output of the polls:

text

poll 2 -> [5, 7, 6, 8]
poll 5 -> [6, 7, 8]
drain: 6 7 8
poll on empty: null, peek on empty: null

Example 2: a task scheduler with a Comparator (practical)

A scheduler should always run the most urgent task. Priority 1 is the most urgent. When two tasks share a priority, we want a stable, predictable choice, so we order by name second. The JDK says ties are broken arbitrarily, which is exactly why the second key matters.

java

record Task(int priority, String name) {}

PriorityQueue<Task> sched = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority).thenComparing(Task::name));
sched.add(new Task(2, "backup"));
sched.add(new Task(1, "send-invoice"));
sched.add(new Task(3, "cleanup"));
sched.add(new Task(1, "alert-oncall"));
sched.add(new Task(2, "report"));
while (!sched.isEmpty()) System.out.println(sched.poll());

Here record is only a compact data holder. Output (compiled and run with JDK 21):

text

Task[priority=1, name=alert-oncall]
Task[priority=1, name=send-invoice]
Task[priority=2, name=backup]
Task[priority=2, name=report]
Task[priority=3, name=cleanup]

Equal priorities come out alphabetically. A task added later is just another add and takes its place automatically. This is the core of the module lab.

Example 3: the top 3 values of a large stream (realistic)

"Give me the 3 largest values" over millions of values does not require sorting everything. Keep a min-heap of size 3: add each value, and whenever the heap grows past 3, remove the smallest. The three survivors are the three largest values seen.

java

static List<Integer> topK(int[] data, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int v : data) {
        heap.add(v);
        if (heap.size() > k) heap.poll();       // drop the smallest
    }
    List<Integer> out = new ArrayList<>(heap);
    out.sort(Comparator.reverseOrder());
    return out;
}

Calling topK(new int[]{12, 5, 31, 8, 27, 3, 19}, 3) printed (compiled and run with JDK 21):

text

[31, 27, 19]

Every value costs one add and at most one poll on a heap of size k, so the work is about n times log k, and memory holds only k values. The final sort only orders the k survivors for display.

Backend Insight

Schedulers and job queues. A job system takes the most urgent or the earliest-due job next. A PriorityQueue with a comparator on priority and then time is the in-memory version. Real queue systems (a later module covers message queues) add durability and many workers.
Top-k. "Top 10 customers by spend" uses the size-k heap pattern from Example 3.
Algorithms. Shortest-path algorithms keep a priority queue of the closest unvisited places.
Caveats. A PriorityQueue is not thread-safe, and it lives in RAM, so a restart loses it. remove(x) is O(n), so changing a priority means removing and re-adding.

Common Mistakes

Mistake 1: Confusing a heap with a BST

A heap does not keep left smaller than right. Searching a heap for an arbitrary value means looking at every element. If you need ordered traversal or lookup, use TreeMap or TreeSet.

Mistake 2: Expecting sorted output when iterating or printing

java

System.out.println(pq);     // [2, 5, 6, 8, 7]   not sorted
for (int x : pq) ...        // no guaranteed order

Use poll() in a loop when you need the items in order, which empties the queue.

Mistake 3: Elements that cannot be compared

If the elements are not Comparable and no Comparator is given, add fails with a ClassCastException. Real output from adding a plain Object to a default queue on JDK 21:

text

ClassCastException: class java.lang.Object cannot be cast to class java.lang.Comparable (java.lang.Object and java.lang.Comparable are in module java.base of loader 'bootstrap')

Pass a Comparator or make your class Comparable. Adding null also fails, with NullPointerException.

Exercises

Try each exercise yourself before opening the solutions.

Level A: Foundation

A1. Add 10, 3, 8, 1, 6, 4, in this order, to an empty min-heap. Write the final array.

أظهر الحل A1

A1. Adds: [10]; 3 swaps up: [3, 10]; [3, 10, 8]; 1 goes to position 3 and swaps with 10, then with 3: [1, 3, 8, 10]; 6 stays under 3: [1, 3, 8, 10, 6]; 4 goes to position 5, swaps with its parent 8: [1, 3, 4, 10, 6, 8] (verified with a real PriorityQueue, JDK 21).

A2. What do the first three poll() calls return from that heap?

أظهر الحل A2

A2. 1, then 3, then 4. The smallest remaining value always comes out first.

A3. In the array [1, 3, 4, 10, 6, 8], which positions are the children of position 1, and what is the parent of position 5?

أظهر الحل A3

A3. The children of position 1 are positions 3 and 4 (2*1+1 and 2*1+2). The parent of position 5 is position (5-1)/2 = 2.

Level B: Application

B1. Starting from [1, 3, 4, 10, 6, 8], do one poll() by hand and write the array afterwards.

أظهر الحل B1

B1. The root 1 is removed. The last value, 8, moves to the root: [8, 3, 4, 10, 6]. Its children are 3 and 4; swap with 3: [3, 8, 4, 10, 6]. At position 1, the children are 10 and 6; swap with 6: [3, 6, 4, 10, 8]. This matches the real queue's output.

B2. A PriorityQueue<String> should hand out shorter words first, and words of equal length alphabetically. Write the constructor call, and the output order for pear, fig, banana, kiwi, apple.

أظهر الحل B2

B2.

java

PriorityQueue<String> q = new PriorityQueue<>(
    Comparator.comparing(String::length).thenComparing(Comparator.naturalOrder()));

Order: fig, kiwi, pear, apple, banana (verified, JDK 21).

B3. Name one task for which a heap is better than a BST, and one for which a BST is better than a heap.

أظهر الحل B3

B3. A heap is better for "always run the most urgent task next" (O(1) peek, O(log n) poll). A BST (TreeMap) is better for "list all values between two limits" or "is this value present?".

Level C: Challenge

C1. Write static int kthLargest(int[] data, int k) using a size-k min-heap. Hint: after processing all values, what sits at the head?

أظهر الحل C1

C1.

java

static int kthLargest(int[] data, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int v : data) {
        heap.add(v);
        if (heap.size() > k) heap.poll();
    }
    return heap.peek();     // the smallest of the k largest
}

For {12, 5, 31, 8, 27, 3, 19} and k = 3, the heap ends holding 31, 27, and 19, and the head is 19. The method assumes data has at least k values.

C2. Why is contains O(n) on a PriorityQueue even though the heap has structure? Why does that make "change a task's priority" awkward?

أظهر الحل C2

C2. A heap only knows where the smallest item is. An arbitrary value could be anywhere, so contains must scan the array, which takes O(n). To change a task's priority you need to find it first (O(n)), remove it, and add it again with the new priority (O(log n) each), so the whole update is O(n).

Mini Challenge

Extend the scheduler from Example 2. Add a long arrivalOrder counter (a field you increase for each submitted task) to Task, and change the comparator to order by priority, then by arrival order. Submit five tasks, two of them with the same priority but different names, and check that tasks of equal priority run in the order they arrived rather than alphabetically.

Check your work: the output is sorted by priority first; within one priority, the task submitted earlier prints first, whatever its name.

Summary & Next Lesson

Key takeaways

A min-heap is a complete binary tree where every parent is at most its children, so the smallest item is at the root. It is not sorted and not a BST.
A heap is stored in an array: for position i, children are at 2i+1 and 2i+2, the parent is at (i-1)/2.
add sifts a value up and poll sifts the last value down from the root, each O(log n); peek is O(1); contains and remove(x) are O(n).
PriorityQueue is a min-heap by default; pass a Comparator for another order (for example Comparator.reverseOrder() for a max-heap). It does not accept null, and iterating it is not sorted.
Use a heap for "most urgent next" and for top-k problems.

Next lesson

The next lesson, "Demo: BST insert and traversals, step by step", puts the module together: you build a BST from scratch, make the planned mistake and fix it, print all four traversals, and see the chain problem once more. It prepares you for the lab, where the scheduler from this lesson joins your BST.

Self-check

Where is the smallest item of a min-heap?
Why is a heap easy to store in an array?
What does poll() do when a PriorityQueue is empty?
Does printing a PriorityQueue show its elements in sorted order?
Give one difference between a heap and a BST.

أظهر الإجابات

At the root, position 0 of the array.
Its shape is complete, with no gaps, so child and parent positions follow from simple arithmetic and no node objects are needed.
It returns null.
No. The iteration order is not specified; only repeated poll() returns items in order.
For example: a heap only guarantees parent at most children and cannot be searched or walked in order, while a BST keeps left smaller and right larger and supports ordered traversal.

References

Oracle Java SE 21 API: PriorityQueue. It documents the heap-based queue, natural or Comparator ordering, the head as the least element, O(log n) for add and poll, O(1) for peek and size, O(n) for remove(Object) and contains, no null elements, arbitrary tie-breaking, unspecified iteration order, and no thread safety.
OpenDSA (Virginia Tech): Heaps and Priority Queues. It defines the heap property and complete shape, the array positions for parent and children, the sift-up and sift-down procedures, their log-time cost, and that a heap is for finding the extreme value rather than searching.
The statement that the JDK class stores its heap in an array, and that its printed form matches the array, comes from running it on JDK 21, not from the documentation. Every Java example above was compiled and run with JDK 21 and the output is copied from the real run.

التطبيق

طبّق هذا الدرس بمختبر الوحدة وتمارينها واختبارها.

المختبر والتمارين الاختبار

تعليم الدرس كمكتمل اختياري ويمكنك التراجع عنه في أي وقت. يبقى تقدمك محفوظًا في هذا المتصفح.

تابع إلى الدرس التالي