Priority Queue Intro - Learning Module

Loading content...

0/276

Implementation Preview — Heaps (Coming Later)

From Interface to Implementation

We've thoroughly explored what a priority queue does—its operations, semantics, and use cases. But we haven't answered an equally important question: How does it work?

Somehow, a priority queue maintains the invariant that the minimum (or maximum) element is always accessible in O(1), while supporting O(log n) insertion and extraction. This seems almost magical. Where does the logarithmic complexity come from? Why not O(1) or O(n)?

The answer lies in a beautifully elegant data structure called a heap. Specifically, the binary heap—a complete binary tree stored in an array that maintains a simple property allowing efficient priority queue operations.

This page provides a conceptual preview of heaps, building intuition before you encounter the detailed Heaps chapter. You'll understand why heaps work for priority queues, even if we defer the how of implementation to later study.

What You Will Learn

By the end of this page, you will understand what a heap is conceptually, why it's the ideal structure for priority queue implementation, and how its properties enable logarithmic operations. You'll be prepared for the detailed Heaps chapter with a solid mental foundation.

Why Not Simpler Structures?

Before diving into heaps, let's understand why simpler data structures fall short for priority queue implementation. This analysis reveals the constraints that heaps elegantly satisfy.

Attempt 1: Unsorted Array

Insert: O(1) — Just append to the end
Extract minimum: O(n) — Must scan entire array to find min

Problem: Extraction is too slow. For n operations, total time is O(n²).

Attempt 2: Sorted Array

Insert: O(n) — Must find position and shift elements
Extract minimum: O(1) — Minimum is at the beginning (or end)

Problem: Insertion is too slow. Same O(n²) total time.

Attempt 3: Linked List (Unsorted)

Insert: O(1) — Insert at head
Extract minimum: O(n) — Must traverse to find min

Same problem as unsorted array.

Attempt 4: Linked List (Sorted)

Insert: O(n) — Must find correct position
Extract minimum: O(1) — Minimum is at head

Same problem as sorted array.

Priority Queue Implementation Options
Structure	Insert	Extract Min	Peek	Total for n ops
Unsorted Array	O(1)	O(n)	O(n)	O(n²)
Sorted Array	O(n)	O(1)	O(1)	O(n²)
Unsorted Linked List	O(1)	O(n)	O(n)	O(n²)
Sorted Linked List	O(n)	O(1)	O(1)	O(n²)
Binary Search Tree (balanced)	O(log n)	O(log n)	O(log n)	O(n log n)
Binary Heap	O(log n)	O(log n)	O(1)	O(n log n)

The Pattern:

Notice that simple linear structures force us to choose between fast insertion OR fast extraction, but not both. We need a structure that:

Maintains partial ordering (not full sort)
Allows O(log n) reorganization after changes
Keeps the extreme element accessible in O(1)

Both balanced BSTs and heaps achieve O(n log n) for n operations. But heaps have advantages:

Simpler implementation
Better cache locality (array-based)
O(1) peek (vs O(log n) for BST to reach leftmost/rightmost)

Partial Ordering is Key

The crucial insight is that priority queues don't need full sorting. We only need to quickly find the extreme element. A heap maintains just enough structure for this—no more. This minimality translates directly to efficiency.

What is a Heap?

A heap is a specialized tree-based data structure that satisfies the heap property. For a min-heap:

Every parent node has a value less than or equal to its children.

For a max-heap, the inequality is reversed: every parent is greater than or equal to its children.

Key Properties:

Heap Structural Properties

•Complete Binary Tree — A heap is a complete binary tree: all levels are fully filled except possibly the last, which is filled left to right. This ensures the tree is as balanced as possible.
•Heap Property — Every parent is better than (or equal to) its children with respect to priority. For min-heap: parent ≤ children. For max-heap: parent ≥ children.
•Root is Extreme — The root of the heap is always the minimum (min-heap) or maximum (max-heap) element. This enables O(1) peek.
•Partial Ordering Only — Siblings are NOT ordered relative to each other. The left child might be greater than, less than, or equal to the right child. Only parent-child relationships are constrained.
•Height is O(log n) — Due to completeness, a heap with n elements has height ⌊log₂(n)⌋. This bounds the work for bubbling up/down.

Visual Intuition:

Imagine a pyramid where each block must be lighter than the block directly above it. The lightest block naturally rises to the top. Blocks at the same level have no relationship—they could be in any order.

Min-Heap Example:

         1
       /   \
      3     2
     / \   /
    7   4 5

Valid: Each parent ≤ children
Root (1) is the minimum
Note: 3 > 2 is fine (siblings unordered)

This is NOT a binary search tree! In a BST, the left child would be less than the parent, and the right child greater. In a heap, both children are greater than (or less than, for max-heap) the parent.

Heap ≠ Binary Search Tree

A common misconception is that heaps and BSTs are similar. They're fundamentally different! BSTs maintain a left-right ordering for efficient search of arbitrary elements. Heaps maintain a parent-child ordering for efficient access to the extreme element. BSTs can find any element in O(log n); heaps can only efficiently find the min/max.

The Ingenious Array Representation

One of the most elegant aspects of binary heaps is that they can be stored in a simple array—no pointers or complex node structures needed. The tree relationship is implicit in array indices.

The Mapping:

For a node at index i (0-indexed):

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

For 1-indexed arrays (some implementations prefer this):

Parent index: ⌊i / 2⌋
Left child index: 2i
Right child index: 2i + 1

heap-array-mapping
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Heap array index calculations (0-indexed)
 */
 
// Given index i, find relatives
function parent(i: number): number {
    return Math.floor((i - 1) / 2);
}
 
function leftChild(i: number): number {
    return 2 * i + 1;
}
 
function rightChild(i: number): number {
    return 2 * i + 2;
}
 
// Example: Heap as array
//
// Tree structure:        Array representation:
//        1               [1, 3, 2, 7, 4, 5]
//       / \              
//      3   2             Index: 0  1  2  3  4  5
//     / \ /              
//    7  4 5              
//
// Verification:
// - Index 0 (value 1): children at 1, 2 (3, 2) ✓
// - Index 1 (value 3): parent at 0 (1), children at 3, 4 (7, 4) ✓
// - Index 2 (value 2): parent at 0 (1), children at 5 (5), right child out of bounds ✓
// - Index 3 (value 7): parent at 1 (3), no children (indices 7, 8 out of bounds) ✓
 
console.log(`Parent of index 3: ${parent(3)}`);      // 1
console.log(`Children of index 1: ${leftChild(1)}, ${rightChild(1)}`); // 3, 4

Why This Works:

The array representation leverages the completeness property of heaps. Because the tree is complete:

No gaps — Elements are placed level by level, left to right, with no missing nodes.
Predictable positions — Given an index, we can compute parent and children positions with simple arithmetic.
Contiguous storage — All elements sit contiguously in memory, enabling excellent cache performance.

Advantages of Array Representation:

Benefits of Array-Based Heaps

•Memory Efficiency — No storage overhead for pointers. Each node stores only the element itself.
•Cache Locality — Contiguous memory access patterns. Modern CPUs love this—fetching one element often brings neighbors into cache.
•Simple Implementation — No node allocation, pointer manipulation, or memory management. Just array operations.
•Fast Indexing — Parent and child lookups are O(1) arithmetic operations, not pointer dereferences.
•Easy Serialization — The array can be directly written to disk or sent over a network. No pointer reconstruction needed.

Dynamic Array Considerations

In languages with dynamic arrays (JavaScript, Python, Java ArrayList), the underlying array can grow as needed. This adds amortized O(1) cost to insertions. In languages requiring fixed-size arrays (C with raw arrays), you must manage resizing explicitly or use a dynamic array wrapper.

How Heap Operations Work (Conceptually)

Let's develop intuition for how heaps maintain their properties during insert and extract operations. We won't implement the full code here—that's for the Heaps chapter—but understanding the concepts now will help.

Insert (Bubble Up / Sift Up / Heapify Up):

When inserting a new element:

Place at end — Add the new element at the next available position (maintaining completeness)
Bubble up — Compare with parent. If the heap property is violated (new element is more important than parent), swap them.
Repeat — Continue comparing and swapping upward until the heap property is restored or we reach the root.

Worst case: The new element bubbles all the way to the root, visiting log(n) levels.

insert-concept
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * Conceptual insert for min-heap
 * 
 * Starting heap: [1, 3, 2, 7, 4, 5]
 * 
 *        1
 *       / \
 *      3   2
 *     /\   /
 *    7  4 5
 * 
 * Insert 0 (should become new minimum):
 */
 
// Step 1: Add at end
// [1, 3, 2, 7, 4, 5, 0]  <- 0 added at index 6
//
//        1
//       / \
//      3   2
//     /\  / \
//    7  4 5  0  <- New element
 
// Step 2: Compare with parent (index 2, value 2)
// 0 < 2, so swap
// [1, 3, 0, 7, 4, 5, 2]
//
//        1
//       / \
//      3   0   <- 0 moved up
//     /\  / \
//    7  4 5  2
 
// Step 3: Compare with parent (index 0, value 1)
// 0 < 1, so swap
// [0, 3, 1, 7, 4, 5, 2]
//
//        0      <- 0 is now root (minimum)
//       / \
//      3   1
//     /\  / \
//    7  4 5  2
 
// Step 4: At root, done!
// Final heap: [0, 3, 1, 7, 4, 5, 2]
 
function insert(heap: number[], value: number): void {
    heap.push(value);             // Add at end
    bubbleUp(heap, heap.length - 1);
}
 
function bubbleUp(heap: number[], i: number): void {
    while (i > 0) {
        const p = Math.floor((i - 1) / 2);
        if (heap[i] >= heap[p]) break;  // Heap property satisfied
        
        [heap[i], heap[p]] = [heap[p], heap[i]];  // Swap
        i = p;  // Move up
    }
}

Extract Min (Bubble Down / Sift Down / Heapify Down):

When extracting the minimum:

Save the root — The minimum is at index 0; save it for return
Move last to root — Take the last element and place it at the root (maintaining completeness)
Bubble down — Compare with children. Swap with the smaller child if it's smaller than the current node.
Repeat — Continue comparing and swapping downward until the heap property is restored or we reach a leaf.

Worst case: The replacement element bubbles all the way down, visiting log(n) levels.

extract-concept
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**
 * Conceptual extract-min for min-heap
 * 
 * Starting heap: [0, 3, 1, 7, 4, 5, 2]
 * 
 *        0
 *       / \
 *      3   1
 *     /\  / \
 *    7  4 5  2
 * 
 * Extract 0 (the minimum):
 */
 
// Step 1: Save root (0), move last element (2) to root
// [2, 3, 1, 7, 4, 5]  <- 2 is now at root
//
//        2      <- 2 moved from last position
//       / \
//      3   1
//     /\  /
//    7  4 5
 
// Step 2: Compare with children (3 and 1)
// Smaller child is 1 (index 2)
// 2 > 1, so swap
// [1, 3, 2, 7, 4, 5]
//
//        1
//       / \
//      3   2   <- 2 moved down
//     /\  /
//    7  4 5
 
// Step 3: Compare 2 with its children (5, no right child)
// 2 < 5, heap property satisfied
// Done!
 
// Final heap: [1, 3, 2, 7, 4, 5]
// Returned: 0
 
function extractMin(heap: number[]): number | undefined {
    if (heap.length === 0) return undefined;
    
    const min = heap[0];
    const last = heap.pop()!;
    
    if (heap.length > 0) {
        heap[0] = last;
        bubbleDown(heap, 0);
    }
    
    return min;
}
 
function bubbleDown(heap: number[], i: number): void {
    const n = heap.length;
    
    while (true) {
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        let smallest = i;
        
        // Find smallest among node and its children
        if (left < n && heap[left] < heap[smallest]) {
            smallest = left;
        }
        if (right < n && heap[right] < heap[smallest]) {
            smallest = right;
        }
        
        if (smallest === i) break;  // Heap property satisfied
        
        [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
        i = smallest;
    }
}

The O(log n) Intuition

Both operations visit at most one node per level. A complete binary tree with n nodes has approximately log₂(n) levels. Hence, both insert and extract are O(log n). The heap's balanced structure (guaranteed by completeness) ensures this bound always holds—no degenerate cases like unbalanced BSTs.

Heap Variants: Beyond Binary Heaps

While binary heaps are the most common implementation, several variants exist with different trade-offs. A brief awareness of these variants helps you understand that "heap" is a broader concept.

Binary Heap (Standard)

The heap we've discussed: binary tree, array-based, O(log n) insert and extract.

Pros: Simple, cache-efficient, great for most use cases
Cons: O(log n) decrease-key operation

D-ary Heap

Generalization where each node has d children instead of 2.

Lower tree height: log_d(n) instead of log₂(n)
More comparisons per level (d children to check)
Optimal d depends on cache line size and comparison cost
Sometimes used for Dijkstra when decrease-key is frequent

Heap Variant Comparison
Heap Type	Insert	Extract	Decrease Key	Merge Two Heaps	Notes
Binary Heap	O(log n)	O(log n)	O(log n)*	O(n)	Simple, practical default
D-ary Heap	O(log_d n)	O(d log_d n)	O(log_d n)*	O(n)	Sometimes faster in practice
Binomial Heap	O(log n)†	O(log n)	O(log n)	O(log n)	Mergeable heaps
Fibonacci Heap	O(1)†	O(log n)†	O(1)†	O(1)	Best for dense graphs + Dijkstra
Pairing Heap	O(1)	O(log n)†	O(log n)†	O(1)	Simpler than Fibonacci, good practice

Notes on the table:

*: Requires indexed heap for O(log n); otherwise O(n) to find element
†: Amortized time complexity

Fibonacci Heap:

The theoretically optimal choice for algorithms heavily using decrease-key (like Dijkstra's on dense graphs). Offers O(1) amortized insert and decrease-key, O(log n) amortized extract.

However:

Complex implementation
High constant factors
In practice, binary heaps often outperform for reasonable-sized inputs
Useful primarily for very large, dense graphs

Practical Recommendation:

Start with binary heaps. They're simple, fast, and sufficient for most applications. Only consider advanced heaps (Fibonacci, pairing) for specialized algorithms on very large datasets where decrease-key dominates the running time.

Theory vs Practice

Fibonacci heaps have better theoretical complexity but binary heaps often win in real benchmarks for moderate input sizes. The simpler structure of binary heaps leads to fewer cache misses and lower constant factors. Theory guides us toward optimal asymptotic behavior, but practice requires benchmarking for your specific use case.

Building Heaps Efficiently

An important question arises: If we have n elements to put in a priority queue, what's the fastest way to build the initial heap?

Naive Approach: n Insertions

Insert elements one by one: n × O(log n) = O(n log n)

This works, but can we do better?

Heapify: O(n) Heap Construction

Surprisingly, yes! We can build a heap from an unordered array in O(n) time. This is called "heapify" or "buildHeap."

The Insight:

Instead of bubbling up from the bottom, we bubble down from the middle. Leaves (half the nodes) are already valid heaps. We fix the heap property from the bottom up:

build-heap-concept
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Build a heap from an unordered array in O(n) time
 */
function buildHeap(arr: number[]): void {
    // Start from the last non-leaf node
    // (parent of the last element)
    const lastNonLeaf = Math.floor((arr.length - 2) / 2);
    
    // Bubble down each node, from bottom to top
    for (let i = lastNonLeaf; i >= 0; i--) {
        bubbleDown(arr, i);
    }
}
 
// Why O(n) and not O(n log n)?
//
// Consider the work done:
// - Nodes at height 0 (leaves): n/2 nodes, 0 work each
// - Nodes at height 1: n/4 nodes, 1 comparison/swap each
// - Nodes at height 2: n/8 nodes, 2 comparisons/swaps each
// - Nodes at height h: n/2^(h+1) nodes, h work each
//
// Total work = Σ (n/2^(h+1)) × h  for h = 0 to log(n)
//            = n × Σ h/2^(h+1)    for h = 0 to log(n)
//            = n × (constant < 2)
//            = O(n)
//
// The sum converges because higher nodes (more work) are exponentially fewer!
 
// Example:
const unsorted = [7, 3, 8, 1, 2, 9, 4, 5, 6];
buildHeap(unsorted);
// Result: [1, 2, 4, 3, 7, 9, 8, 5, 6] (a valid min-heap)

Counter-Intuitive Result

It seems like bubbling down from n/2 positions, each potentially log(n) work, should be O(n log n). The key insight is that most nodes are near the bottom (leaves), where bubble-down does little work. Only the few nodes near the top do O(log n) work. The math works out to O(n) total.

Practical Implications:

Initialization — If you have all elements upfront, use buildHeap (O(n)) rather than n insertions (O(n log n)).
Heapsort — The heapsort algorithm uses buildHeap + n extractMin operations: O(n) + O(n log n) = O(n log n) total, with O(1) extra space.
Batch Operations — Some systems batch insertions and periodically rebuild the heap, trading insert latency for overall throughput.

What's Coming in the Heaps Chapter

This preview has established conceptual understanding. The dedicated Heaps chapter will provide:

Full Implementation Details:

Complete, production-quality heap implementations in multiple languages
Edge case handling and error management
Generic implementations supporting any comparable type

Operation Deep Dives:

Step-by-step traces of bubbleUp and bubbleDown
Visualization of heap operations
Complexity analysis with formal proofs

Advanced Topics:

Indexed heaps for efficient decrease-key
D-ary heap variations
Heap memory layout and cache optimization
Concurrent/thread-safe priority queues

Topics Deferred to Heaps Chapter

•Heapsort Algorithm — Using a heap to sort an array in O(n log n) time with O(1) extra space.
•Heap in Graph Algorithms — Detailed implementation of Dijkstra's and Prim's using indexed heaps.
•K-way Merge — Using heaps to efficiently merge k sorted sequences.
•Top-K Problems — Finding the k largest/smallest elements using heaps.
•Median Maintenance — Using two heaps to track the running median of a stream.
•Heap Variants Implementation — Binomial heaps, Fibonacci heaps (conceptual), pairing heaps.

Curriculum Sequencing

We introduce priority queues conceptually before heaps because understanding the 'what' (interface) before the 'how' (implementation) leads to better comprehension. You can use priority queues effectively knowing only the interface. The heap chapter adds implementation mastery, enabling you to build and customize priority queues for specialized needs.

Summary: Heaps as Priority Queue Implementation

We've previewed the heap data structure—the elegant, efficient implementation behind priority queues. Let's consolidate the key concepts.

Key Takeaways

•Simpler structures fail — Sorted and unsorted arrays/lists can't achieve O(log n) for both insert and extract. We need something smarter.
•Heaps maintain partial ordering — Every parent is better than its children. This is enough to efficiently find the extreme element.
•Binary heaps use array representation — No pointers needed. Parent/child relationships are computed from indices. This gives excellent cache performance.
•Insert bubbles up — New element goes at the end and rises until the heap property is satisfied. O(log n) worst case.
•Extract bubbles down — Root is removed, last element takes its place and sinks. O(log n) worst case.
•Heap can be built in O(n) — Using bottom-up heapify, we can construct from an unordered array faster than n insertions.
•Advanced variants exist — Fibonacci heaps, binomial heaps, pairing heaps offer different trade-offs for specialized use cases.

Module Complete:

Congratulations! You've completed the Priority Queue conceptual introduction. You now understand:

What priority queues are and why they exist
The difference between priority-based and arrival-based ordering
The complete priority queue interface
How heaps make efficient implementation possible

You're fully prepared to use priority queues in your code and to dive into the Heaps chapter when we explore implementation in depth.

Module Complete

You have completed Module 7: Priority Queue — Conceptual Introduction. You've built a comprehensive mental model of priority queues as an abstract data type, understood their interface, and previewed how heaps make them efficient. This foundation prepares you for both practical usage and deep implementation study.