Heaps and Priority Queues

Introduction

Many computing tasks repeatedly need the item with the greatest or smallest priority: a scheduler selects the next job, a simulation processes the next event, and a graph algorithm selects the next closest vertex. A linear search can find such an item in O(n) time, while a sorted list can make selection fast but makes insertion expensive. Heaps provide a balanced compromise: they support priority-based access in logarithmic time and can often be implemented compactly in an array.

This chapter develops binary and d-ary heaps, heap construction, heap sort, and priority queues. It also examines applications in operating systems, discrete-event simulation, streaming analytics, and top-k queries.

Learning Objectives

By the end of this chapter, you should be able to:

• Explain the heap-order and complete-tree properties.
• Represent binary and d-ary heaps in arrays.
• Implement insertion, inspection, deletion, and key-update operations.
• Construct a heap efficiently from an unsorted array.
• Use heaps to implement heap sort and priority queues.
• Select an appropriate branching factor and priority-queue design.
• Apply heaps to scheduling, simulation, streaming, and top-k analytics.
• Analyze correctness, complexity, and practical limitations.

1. Priority Queues and Heap Structure

A priority queue is an abstract data type containing entries with priorities. Its principal operations are:

A min-priority queue treats the smallest key as most urgent; a max-priority queue treats the largest key as most urgent. A priority queue does not necessarily preserve the ordering of all elements. It guarantees only the ordering needed to identify the next item.

A binary heap is a nearly complete binary tree satisfying a heap-order property. A complete tree has every level full except possibly the last, and the last level is filled from left to right. The heap property is:

• Min-heap: every parent key is less than or equal to each child key.
• Max-heap: every parent key is greater than or equal to each child key.

The property is local, but it implies that the root contains a global minimum or maximum. It does not imply that siblings are ordered or that an in-order traversal is sorted.

Array representation

Because a complete tree has no gaps, it can be stored efficiently in an array. With zero-based indexing, the binary heap relations are:

Here, i is an array index and ⌊ ⌋ denotes the floor function. A child index is valid only if it is less than the heap size. With one-based indexing, the corresponding relations are parent(i) = ⌊i/2⌋, left(i) = 2i, and right(i) = 2i + 1.

For a d-ary heap using zero-based indexing, node i has children:

Its parent is ⌊(i − 1)/d⌋ for i > 0. The parameter d is an integer at least 2. Increasing d reduces tree height but increases the number of children examined during some operations.

2. Fundamental Heap Operations

The following pseudocode uses a min-heap. A max-heap is obtained by reversing comparisons.

Insertion: sift up

To insert an item, append it at the next available array position. This preserves completeness. If its key is smaller than its parent's key, exchange it with the parent. Continue until the heap property is restored.

insert(H, x):
    append x to H
    i ← last index
    while i > 0 and key(H[i]) < key(H[parent(i)]):
        swap H[i], H[parent(i)]
        i ← parent(i)

The new item moves along one root-to-leaf path. Since a binary heap of n items has height ⌊log₂ n⌋, insertion takes O(log n) time and O(1) additional space when performed in place.

Minimum inspection and extraction

The minimum is always at index 0, so peek-min takes O(1) time. To remove it, move the last element to the root, reduce the heap size, and sift that element downward.

extract-min(H):
    if H is empty: report underflow
    result ← H[0]
    H[0] ← last element of H
    remove last position
    sift-down(H, 0)
    return result

For a min-heap, sift-down compares a node with its children and swaps it with the smaller child when necessary. The process stops when the node is no larger than either child or becomes a leaf.

sift-down(H, i):
    while i has at least one child:
        j ← index of the smallest child of i
        if key(H[i]) ≤ key(H[j]): break
        swap H[i], H[j]
        i ← j

Extraction takes O(log n) time. The root is removed, and only one path is repaired.

Decrease-key and increase-key

In a min-heap, decreasing a key may violate the property with its parent, so the item is sifted up. Increasing a key may violate the property with its children, so it is sifted down. These operations require locating the item; a practical implementation may store a handle or a map from item identifiers to heap indices.

If arbitrary searching is required before changing a key, locating the item may take O(n). With a maintained index map, the repair itself takes O(log n), but every swap must update the map.

Complexity summary

The d-ary extraction bound includes up to d child comparisons at each of approximately log_d n levels. The asymptotic notation assumes constant-time key comparison and array access.

3. Maintaining the Invariant

Heap algorithms are best understood through invariants. During sift-up, every subtree except possibly the path containing the newly inserted item is already a heap. Each exchange moves the offending item closer to the root and preserves completeness. During sift-down, every subtree below the current position is already a heap; exchanging with the smallest child moves the item downward while preserving the invariant below it.

For a min-heap, selecting the smallest child is essential. Swapping with an arbitrary child can leave a smaller child below the new parent and therefore fail to restore the heap property.

Duplicate keys cause no difficulty. A stable ordering among equal-priority records is not guaranteed. If stability matters, represent each entry as (priority, sequence number, payload), and compare sequence numbers when priorities are equal.

4. Building a Heap

There are two standard construction methods.

Repeated insertion

Start with an empty heap and insert the n input elements one at a time. Each insertion costs O(log n), giving O(n log n) worst-case time. This method is useful when items arrive incrementally.

Bottom-up construction

Place all input elements in array order, which immediately creates a complete tree. Leaves already satisfy the heap property because they have no children. Starting with the last internal node and proceeding toward the root, apply sift-down.

For a zero-based binary heap, the last internal node is at index ⌊n/2⌋ − 1. Pseudocode is:

build-heap(A):
    for i ← floor(length(A)/2) − 1 down to 0:
        sift-down(A, i)

Although an individual sift-down can cost O(log n), bottom-up construction costs O(n), not O(n log n). The reason is that most nodes are near the leaves and can move only a short distance. More formally, if h is a node's height, the number of nodes of height h decreases geometrically as h increases, so the total work is bounded by a convergent linear sum.

Worked example

Consider the array [9, 4, 7, 1, 3, 6, 2]. The last internal index is 2. Sifting down index 2 exchanges 7 with 2, producing [9, 4, 2, 1, 3, 6, 7]. Sifting down index 1 exchanges 4 with 1, producing [9, 1, 2, 4, 3, 6, 7]. Finally, sifting down index 0 exchanges 9 with 1 and then with 3, producing:

[1, 3, 2, 4, 9, 6, 7]

Every parent is now no greater than its children, so the result is a valid min-heap.

5. Heap Sort

Heap sort uses a max-heap to sort an array in ascending order. First build a max-heap. The maximum is at index 0. Exchange it with the last element in the active heap, reduce the active heap size by one, and sift down the new root. Repeat until one element remains.

heap-sort(A):
    build-max-heap(A)
    for end ← length(A) − 1 down to 1:
        swap A[0], A[end]
        sift-down(A, 0, end)

The build phase costs O(n), and n − 1 extractions cost O(n log n), so total time is O(n log n). Heap sort uses O(1) auxiliary space beyond the input array and has a worst-case O(n log n) guarantee. Its disadvantages are relatively poor cache locality and lack of stability. In many practical applications, an optimized quicksort or merge sort is faster, but heap sort remains valuable when predictable worst-case time and in-place operation are priorities.

6. d-Ary Heaps

A d-ary heap generalizes the binary heap. Its height is approximately log_d n. Insertion can be faster because an item has fewer levels to climb. Extraction can be slower because each level may require scanning d children to find the best one.

The branching factor should reflect the workload. If insertions and decrease-key operations dominate, a larger d may reduce height. If extractions dominate, a smaller d may reduce child comparisons. Hardware also matters: contiguous arrays, cache behavior, branch prediction, and comparison cost can outweigh asymptotic differences.

For example, with n = 1,000,000, a binary heap has about log₂(1,000,000) ≈ 20 levels, while a 4-ary heap has about log₄(1,000,000) ≈ 10 levels. However, a 4-ary extraction may inspect up to four children per level rather than two. The best choice should therefore be measured under representative workloads.

7. Priority Queues in Practice

A priority queue entry usually contains a priority, a payload, and possibly metadata such as an insertion sequence number or cancellation flag. Common implementation decisions include:

• Min versus max: determined by whether lower or higher values represent urgency.
• Tie breaking: use a sequence number, deadline, or explicit secondary key.
• Mutable priorities: use handles and an index map, or insert a replacement record and lazily discard stale records.
• Capacity: dynamic arrays simplify growth; bounded queues require an overflow policy.
• Concurrency: shared queues require locking or a concurrent priority-queue design.

A heap is not appropriate when the application requires efficient ordered traversal, range queries, or frequent membership tests. A balanced search tree may be preferable in those cases. If priorities are small bounded integers, bucket queues can outperform comparison-based heaps.

8. Applications

Scheduling

A job scheduler may assign each task a deadline, priority class, or estimated cost. The queue returns the most urgent ready task. A production scheduler must also address starvation, fairness, aging, cancellation, and priority inversion. A simple heap orders tasks efficiently, but policy determines whether that order is socially and operationally acceptable.

For deadline scheduling, a task record might be ordered lexicographically by (deadline, arrival sequence). The sequence number ensures deterministic behavior for equal deadlines. Priority values should not be trusted blindly when submitted by users; authorization and quotas are needed to prevent every client from assigning maximum priority.

Discrete-event simulation

In a simulation, each future event has a timestamp. The event with the smallest timestamp is extracted, processed, and may generate new future events. A min-heap supports insertion and extraction in O(log n), making it suitable for large event calendars.

The simulator must maintain the invariant that event timestamps are not processed out of order. Events scheduled for the same timestamp require a defined tie-breaking rule. Cancellation can be handled with an event identifier and lazy deletion, avoiding an expensive arbitrary removal operation.

Streaming top-k analytics

To maintain the k largest values in a stream, use a min-heap of size k. For each incoming value x:

1. Insert x if the heap contains fewer than k items.
2. Otherwise compare x with the heap minimum.
3. Replace the minimum if x is larger.

The heap minimum is the cutoff: any retained item is at least as large as it. For n stream elements, time is O(n log k), space is O(k), and the result is exact. This is preferable to storing and sorting all n values when k is much smaller than n.

For the k smallest values, use a max-heap of size k. For approximate analytics over massive or distributed streams, specialized sketches may use less memory, but they introduce estimation error and require explicit accuracy guarantees.

9. Detailed Applied Case: Cloud Batch Scheduling

Background

Consider an illustrative cloud platform that receives data-processing jobs from several departments. Each job has a deadline, estimated execution time, customer, and resource requirement. Workers repeatedly request the next eligible job.

Problem

The platform must select jobs efficiently while preventing low-priority jobs from waiting indefinitely. Jobs can be cancelled, and a department may submit many jobs with identical priority.

Analysis

A heap provides fast selection of the next job, but a single numeric priority is insufficient. The scheduler uses the key:

(priority class, effective deadline, arrival sequence)

Lower tuples are selected first. An aging rule gradually improves the effective priority of jobs that have waited beyond a threshold. The queue stores a handle for each active job, while a separate map connects job identifiers to heap positions.

Approach and solution

When a job arrives, it is validated against resource quotas and inserted into a min-heap. Cancellation marks the job inactive and removes its identifier from the map. If immediate arbitrary deletion is undesirable, the scheduler can leave a tombstone in the heap and discard it whenever it reaches the root. Workers call extract-min and then verify resource availability; a job that cannot run is deferred or moved to a compatible resource queue.

Outcome

Insertion and selection remain O(log n), while inspection of the next job is O(1). The design scales better than scanning all waiting jobs for every worker request. However, resource compatibility may require multiple queues or a more specialized scheduler.

Learning points

The heap solves ordering, not the entire scheduling problem. Fairness, cancellation, capacity, observability, failure recovery, and security policies must be designed around it. In operational systems, deterministic tie breaking and metrics such as queue wait time are as important as asymptotic complexity.

10. Correctness, Limitations, and Best Practices

A heap implementation should be tested with empty heaps, one-element heaps, duplicate keys, already sorted input, reverse-sorted input, negative keys, very large inputs, and repeated equal priorities. A useful validation routine checks every index i and confirms that each valid child satisfies the heap relation.

Common errors include confusing heap order with sorted order, using the wrong child formula, forgetting to reduce the active size after extraction, selecting the wrong child during sift-down, and modifying a key without repairing the appropriate direction. Integer overflow can affect computed indices in low-level languages; use a sufficiently wide index type and validate bounds.

Heaps expose metadata such as job priorities and event times. Access controls, audit logs, and input validation are therefore relevant. A scheduler should not reveal confidential job information through priority ordering. In AI and data-processing systems, top-k selection can amplify bias when ranking scores reflect biased data; the data structure is neutral, but the ranking policy is not.

Contemporary systems often combine heaps with asynchronous runtimes, distributed queues, persistent logs, and telemetry. A local heap provides no distributed consensus, durability, or exactly-once processing by itself. These properties require additional protocols and storage mechanisms.

Chapter Summary

A heap is a complete tree governed by a local ordering rule. Array representation makes parent and child navigation efficient and avoids pointer overhead. Binary heaps support constant-time root inspection and logarithmic-time insertion and extraction. Bottom-up construction builds a heap in O(n), while repeated insertion costs O(n log n). Heap sort offers O(n log n) worst-case time and O(1) auxiliary space but is not stable.

A d-ary heap reduces height while increasing the number of children considered during downward repair. Priority queues built from heaps support scheduling, event simulation, and streaming top-k analytics. Correct implementation depends on preserving completeness, selecting the appropriate child, handling ties and mutable priorities, and validating boundary cases. In professional systems, algorithmic performance must be combined with fairness, security, cancellation, observability, and workload-specific design.

Key Terms

Heap: A complete tree satisfying a heap-order property.

Binary heap: A heap in which each node has at most two children.

d-ary heap: A heap in which each internal node has at most d children.

Min-heap: A heap whose root contains the minimum key.

Max-heap: A heap whose root contains the maximum key.

Heap property: The rule relating each parent key to its child keys.

Complete tree: A tree filled level by level, with the final level left-aligned.

Priority queue: An abstract data type that removes entries according to priority.

Sift-up: Moving an item toward the root to restore heap order.

Sift-down: Moving an item toward the leaves to restore heap order.

Heapify: The operation that repairs heap order at a specified node.

Bottom-up construction: Building a heap by heapifying internal nodes from the bottom upward.

Heap sort: An in-place sorting algorithm based on repeated root extraction.

Decrease-key: Lowering a key in a min-heap and repairing upward.

Increase-key: Raising a key in a min-heap and repairing downward.

Tie breaking: A rule for ordering entries with equal primary priorities.

Lazy deletion: Marking an entry removed and discarding it when encountered.

Top-k: The k largest or smallest elements according to a ranking criterion.

Heap handle: A reference or index used to locate an entry efficiently.

Starvation: Indefinite postponement of a task in a priority-based system.

Review Questions

Short Answer Questions

1. What two structural properties define a binary min-heap?
2. Why does peek-min have O(1) time complexity?
3. State the zero-based array formulas for the children of binary-heap index i.
4. Why is bottom-up heap construction O(n) rather than O(n log n)?
5. What data structure is useful for maintaining the k largest items in a stream?

Long Answer Questions

1. Explain insertion and extract-min, including their invariants and time complexities.
2. Compare binary and d-ary heaps in terms of height, insertion, and extraction.
3. Describe heap sort and evaluate its advantages and disadvantages.
4. Explain how a priority queue can support discrete-event simulation.
5. Discuss the design issues involved in implementing a production scheduling queue.

Analytical / Application Questions

1. Design a priority-queue key for a scheduler that must consider urgency, deadline, and fair treatment of equal-priority jobs. Justify the tie-breaking rule.
2. A stream contains millions of values, but only the 100 largest are needed. Select an appropriate heap, give the time and space complexity, and explain why sorting the complete stream is less memory-efficient.
3. An implementation extracts from a min-heap by swapping the root with the last element but never sifts down. Give a counterexample and explain precisely which invariant fails.

Multiple Choice Questions with Answers

Question 1

Which property guarantees that a binary heap can be stored compactly in an array?

A. The tree is complete

B. The tree is a binary search tree

C. All keys are distinct

D. The tree is perfectly balanced

Correct Answer: A. The tree is complete

Question 2

In a zero-based binary heap, what is the left child of index i?

A. 2i

B. 2i + 1

C. i + 1

D. ⌊i/2⌋

Correct Answer: B. 2i + 1

Question 3

What is the worst-case time complexity of inserting an item into a binary heap?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

Correct Answer: B. O(log n)

Question 4

Which operation returns the minimum of a min-heap without removing it?

A. Sift-up

B. Build-heap

C. Peek-min

D. Heap sort

Correct Answer: C. Peek-min

Question 5

What is the time complexity of bottom-up construction of a binary heap from n items?

A. O(log n)

B. O(n)

C. O(n log n)

D. O(n²)

Correct Answer: B. O(n)

Question 6

To sort an array in ascending order using heap sort, which heap is normally built first?

A. Min-heap

B. Max-heap

C. Ternary heap only

D. Unordered tree

Correct Answer: B. Max-heap

Question 7

A min-heap is most suitable for which task?

A. Selecting the smallest timestamped future event

B. Finding whether two keys are equal

C. Performing a range query on all keys

D. Maintaining insertion order exactly

Correct Answer: A. Selecting the smallest timestamped future event

Question 8

To maintain the k largest values in a stream, which structure is appropriate?

A. A min-heap of at most k values

B. A max-heap containing every stream value

C. A stack of at most k values

D. A queue containing only the first k values

Correct Answer: A. A min-heap of at most k values

Question 9

In a min-heap, after increasing an item's key, which repair direction is generally required?

A. Toward the root

B. Toward the leaves

C. Horizontally among siblings only

D. No repair is ever required

Correct Answer: B. Toward the leaves

Question 10

What is a principal trade-off of increasing d in a d-ary heap?

A. Greater height and fewer child comparisons

B. Lower height but potentially more child comparisons per level

C. Loss of the complete-tree property

D. Constant-time extraction for all n

Correct Answer: B. Lower height but potentially more child comparisons per level