Data Structures & AlgorithmsPriority Queues Revisited

Priority Queues Revisited — Now with Implementation

LevelIntermediate

Duration60 mins

TopicPriority Queues Revisited

4 / 4

The Heap as an Efficient Implementation

The Elegant Solution

We've established the problem: priority queues require O(log n) for both insert and extract, and naive linear structures can't deliver. We've hinted at the solution: a tree structure with partial ordering.

Now we meet the binary heap—one of computer science's most elegant data structures.

The heap is simultaneously:

Simple to understand: just two properties define it
Efficient to implement: stored as an array, no pointers needed
Optimal in performance: O(log n) insert and extract, O(1) peek
Cache-friendly: sequential array access patterns
Foundation-laying: basis for heapsort, graph algorithms, and countless applications

By the end of this page, you'll understand the heap so deeply that you could implement one from scratch without reference material—and more importantly, you'll understand why it works, not just how.

Learning Objectives

By the end of this page, you will understand the two defining properties of a binary heap (structure and ordering), why these properties together enable efficient priority queue operations, how a heap visually looks as a tree, and the intuition for why operations achieve O(log n) complexity.

The Binary Heap Definition

A binary heap is a binary tree with exactly two properties:

Property 1: Shape Property (Complete Binary Tree)

The tree is a complete binary tree: all levels are fully filled except possibly the last, which is filled left-to-right.

Property 2: Heap Property (Ordering)

For a min-heap: Every parent is ≤ its children. For a max-heap: Every parent is ≥ its children.

That's it. These two properties—one about shape, one about ordering—completely define a binary heap.

heap_properties.md
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
# Binary Heap Properties
 
## Property 1: Complete Binary Tree Structure
┌─────────────────────────────────────────────────────┐
│                                                     │
│  Valid Complete Binary Tree:                        │
│                                                     │
│            1         Level 0: 1 node (full)         │
│          /   \                                     │
│         2     3      Level 1: 2 nodes (full)        │
│        / \   /                                      │
│       4   5 6        Level 2: filled left-to-right  │
│                                                     │
│  Invalid (not complete):                            │
│                                                     │
│            1                                        │
│          /   \                                     │
│         2     3      ✗ Level 2 has gaps            │
│          \   /                                     │
│           5 6                                       │
│                                                     │
└─────────────────────────────────────────────────────┘
 
## Property 2: Heap Ordering (Min-Heap Example)
┌─────────────────────────────────────────────────────┐
│                                                     │
│  Valid Min-Heap:     Every parent ≤ children        │
│                                                     │
│            1         1 ≤ 2, 1 ≤ 3 ✓                 │
│          /   \                                     │
│         2     3      2 ≤ 4, 2 ≤ 5, 3 ≤ 6 ✓         │
│        / \   /                                      │
│       4   5 6                                       │
│                                                     │
│  Invalid Min-Heap:                                  │
│                                                     │
│            1                                        │
│          /   \                                     │
│         5     3      5 > 2 ✗ (child smaller)       │
│        / \   /                                      │
│       2   7 6                                       │
│                                                     │
└─────────────────────────────────────────────────────┘

Two Properties, One Power

The beauty of the heap is that these two simple properties are sufficient. Shape ensures O(log n) height. Ordering ensures the extremum is at the root. Together, they enable everything we need.

Understanding the Complete Binary Tree

Why Completeness Matters:

A complete binary tree is filled level-by-level, left-to-right, with no gaps. This specific shape provides two crucial benefits:

Benefit 1: Guaranteed Height Bound

A complete binary tree with n nodes has height exactly ⌊log₂(n)⌋.

Proof intuition:

Level 0 has 1 node
Level 1 has up to 2 nodes
Level 2 has up to 4 nodes
Level k has up to 2^k nodes
Total nodes through level k: 1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1

For n nodes, we need at least ⌊log₂(n)⌋ levels. Completeness ensures we don't need more.

Benefit 2: Array Representation

Because there are no gaps, we can store the tree in an array without wasted space. Element at index i has:

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

This eliminates pointer overhead entirely.

Height vs Capacity for Complete Binary Trees
Height	Max Nodes	Min Nodes	Height in O-notation
0	1	1	O(1) for n=1
1	3	2	O(1) for n=2-3
2	7	4	O(1) for n=4-7
3	15	8	O(1) for n=8-15
10	2,047	1,024	O(10) for n~1000-2000
20	2,097,151	1,048,576	O(20) for n~1 million
30	~1 billion	~500 million	O(30) for n~1 billion

Contrast with Unbalanced Trees:

Without the completeness constraint, a binary tree with n nodes could have height n-1 (a linked list in disguise). If heap operations took O(height) time, an unbalanced heap would have O(n) operations—no better than our naive approaches!

Unbalanced BST (worst case)     vs     Complete Binary Tree

    1                                        1
     \                                     /   
      2                                   2     3
       \                                /   \  /  
        3              vs              4   5  6   7
         
          4
           
            5

Height: n-1 = 4                        Height: log₂(7) ≈ 2.8

Completeness guarantees logarithmic height, which guarantees logarithmic operation time.

Completeness ≠ Balanced

A complete binary tree is a specific type of balanced tree. All complete trees are balanced (height = O(log n)), but not all balanced trees are complete. AVL and Red-Black trees are balanced but allow gaps. Heaps specifically require completeness for the array representation.

Understanding the Heap Property

The Heap Property Formally:

For a min-heap, for every node N (except the root):

N.value ≥ N.parent.value

Equivalently, for every parent P:

P.value ≤ P.leftChild.value  (if left child exists)
P.value ≤ P.rightChild.value (if right child exists)

For a max-heap, reverse the inequalities.

What the Heap Property Guarantees:

Heap Property Implications

•Root is the minimum (min-heap): By transitivity, root ≤ children ≤ grandchildren ≤ ... ≤ all nodes. The root is the global minimum.
•Peek is O(1): The minimum is always at index 0 of the array. No searching required.
•Path ordering: Every path from root to leaf is sorted (ascending for min-heap).
•Subtrees are heaps: Any subtree rooted at a heap node is itself a valid heap.

What the Heap Property Does NOT Guarantee:

What Heaps Don't Provide

•Sibling ordering: Left child vs right child have no ordering relationship. Either can be smaller.
•Level ordering: Elements at the same level have no ordering relationship.
•General sorted access: You can only efficiently access the min. Finding the 5th smallest requires 5 extractions.
•Efficient search: Finding if a value exists requires O(n) traversal in the worst case.

heap_property_examples.md
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
# Heap Property Examples (Min-Heap)
 
## Example 1: Valid Min-Heap
           1
         /   \
        3     2
       / \   / \
      7   6 4   5
 
Parent-child relationships all satisfy parent ≤ children:
- 1 ≤ 3 ✓, 1 ≤ 2 ✓
- 3 ≤ 7 ✓, 3 ≤ 6 ✓
- 2 ≤ 4 ✓, 2 ≤ 5 ✓
 
Note: 3 > 2 (siblings unordered) — this is FINE!
Note: 7 > 4 (cousins unordered) — this is FINE!
 
## Example 2: Invalid Min-Heap
           1
         /   \
        4     2
       / \       
      3   6      
 
Violation: 4 > 3 (parent > child) ✗
The value 3 should "bubble up" past 4.
 
## Example 3: Deceptive Valid Heap
           1
         /   \
        8     2
       / \   / \
      9  10 3   4
 
This IS valid! Despite 8 appearing "too big":
- 1 ≤ 8 ✓, 1 ≤ 2 ✓
- 8 ≤ 9 ✓, 8 ≤ 10 ✓
- 2 ≤ 3 ✓, 2 ≤ 4 ✓
 
The heap property is LOCAL (parent vs direct children).
8 being much larger than its sibling 2 is irrelevant.

Don't Expect Full Sorting

A common misconception: heaps are 'almost sorted.' They're not! A heap only guarantees parent ≤ children—this is a very weak ordering. Two adjacent elements in the array may be in any order relative to each other. The heap property is just enough to efficiently find the minimum, nothing more.

How the Heap Achieves O(log n)

Now for the key insight: how do the two heap properties combine to achieve O(log n) for insert and extract?

The Fundamental Operations:

Both insert and extract temporarily violate the heap property, then restore it:

Insert: Add element at the end (maintains completeness), then "bubble up" (restore heap property)
Extract: Remove root, move last element to root (maintains completeness), then "bubble down" (restore heap property)

Why O(log n)?

Bubbling up: Element moves from bottom toward root, at most log n levels. Bubbling down: Element moves from root toward bottom, at most log n levels.

Each level requires O(1) comparisons and swaps. The height is O(log n). Therefore, both operations are O(log n).

operation_overview.md
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
# Insert Operation Overview
 
Initial Heap:            Insert 0:          After Bubble Up:
                         Add at end         0 bubbles to root
 
      1                       1                    0
    /   \                   /   \                /   \
   3     2                 3     2               1     2
  / \   /                 / \   / \             / \   /
 7   6 4                  7   6 4   0          7   6 4   3
                                ↑                      ↑
                          New position          Bubble up
 
Bubbling: Compare 0 with parent 2. 0 < 2, swap.
          Compare 0 with parent 1. 0 < 1, swap.
          0 is now root. Done.
 
Path length: 2 swaps = O(log n)
 
 
# Extract Operation Overview
 
Initial Heap:            Remove root,       After Bubble Down:
                         Replace with last
 
      1                       4                    2
    /   \                   /   \                /   \
   3     2                 3     2               3     4
  / \   /                 / \                   / \
 7   6 4                  7   6                 7   6
                               ↑                     ↑
                          Last to root        Bubble down
 
Bubbling down: Compare 4 with children 3, 2. Swap with smaller (2).
               Compare 4 with children (none on left, none on right).
               4 is a leaf. Done.
 
Path length: 1 swap = O(log n)

The Critical Invariant:

At every step of bubbling, we restore the heap property for an ever-larger subtree:

After bubbling one level, the heap property holds for the moved element and its immediate neighbors
After bubbling to completion, the heap property holds for the entire tree

This local repair propagating upward/downward is what makes heaps efficient. We never examine more than O(log n) nodes.

Heap Operation Complexity Summary
Operation	Complexity	Mechanism	Why It Works
insert	O(log n)	Add at end, bubble up	At most log n levels to traverse
extractMin	O(log n)	Move last to root, bubble down	At most log n levels to traverse
peekMin	O(1)	Return root	Heap property guarantees root is min
build heap	O(n)	Bottom-up heapify	Most nodes near bottom, short bubble distance
isEmpty	O(1)	Check array length	Trivial
size	O(1)	Return array length	Trivial

Completeness Enables Speed

The completeness property is crucial. It guarantees the tree has minimum height for n nodes. Without completeness (e.g., an arbitrary binary tree with heap ordering), the tree could be tall and skinny, and bubbling could take O(n) time.

The Array Representation

The Brilliant Trick:

A complete binary tree can be stored in an array without wasting space and without needing pointers. This is called the implicit tree representation.

The Mapping:

For a 0-indexed array:

Root is at index 0
For node at index i:
- Parent is at index: ⌊(i-1)/2⌋
- Left child is at index: 2i + 1
- Right child is at index: 2i + 2

array_representation.ts
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
/**
 * Tree:                 Array:
 * 
 *        10             index: 0  1  2  3  4  5  6
 *      /    \           value: 10 20 15 30 25 40 35
 *    20      15         
 *   /  \    /  \
 *  30  25  40  35
 * 
 * Relationships (0-indexed):
 * - Node 10 at index 0: children at 1, 2
 * - Node 20 at index 1: parent at 0, children at 3, 4
 * - Node 15 at index 2: parent at 0, children at 5, 6
 * - Node 30 at index 3: parent at 1, no children (3*2+1=7 > array.length)
 */
 
class BinaryHeap<T> {
    private data: T[] = [];
    private compare: (a: T, b: T) => number;
    
    constructor(compare: (a: T, b: T) => number) {
        this.compare = compare;
    }
    
    // Index calculations — the heart of array-based heaps
    private parent(i: number): number {
        return Math.floor((i - 1) / 2);
    }
    
    private leftChild(i: number): number {
        return 2 * i + 1;
    }
    
    private rightChild(i: number): number {
        return 2 * i + 2;
    }
    
    private hasLeftChild(i: number): boolean {
        return this.leftChild(i) < this.data.length;
    }
    
    private hasRightChild(i: number): boolean {
        return this.rightChild(i) < this.data.length;
    }
    
    private hasParent(i: number): boolean {
        return i > 0;
    }
    
    // Swapping elements — O(1)
    private swap(i: number, j: number): void {
        [this.data[i], this.data[j]] = [this.data[j], this.data[i]];
    }
}

Why Arrays Work Here:

Normally, trees use explicit pointers (left, right, parent). Why can heaps use arrays?

Completeness: No gaps in the tree = no gaps in the array. Each index corresponds to exactly one node.
Predictable structure: The tree shape is completely determined by the number of elements. We don't need to store the structure—it's implicit in the indices.
Efficient navigation: Parent and child lookups are simple arithmetic—no pointer chasing, excellent cache performance.

Array Representation Benefits

•No pointer overhead (saves memory)
•Cache-friendly (contiguous memory)
•Simple index arithmetic
•Easy to serialize/deserialize
•Dynamic array handles growth

Pointer-Based Downsides

•Memory overhead per node
•Poor cache locality
•More complex traversal code
•Harder to serialize
•Memory fragmentation over time

1-Indexed vs 0-Indexed

Some textbooks use 1-indexed arrays (root at index 1) for prettier formulas: parent(i) = i/2, left(i) = 2i, right(i) = 2i+1. Both work; 0-indexed is more natural in most programming languages. Just be consistent.

Visualizing the Heap — Tree and Array Together

Let's build a mental model that connects the tree visualization with the array storage. When you work with heaps, you'll think in both representations simultaneously.

Example: Building a Min-Heap

Starting with elements: [4, 10, 3, 5, 1]

Insert order and heap evolution:

heap_visualization.md
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
# Building a Min-Heap: Insert [4, 10, 3, 5, 1]
 
## Insert 4
Tree:   4          Array: [4]
        
No bubbling needed (single element).
 
## Insert 10
              4                    Array: [4, 10]
             /
           10
 
10 ≥ 4 → heap property holds.
 
## Insert 3
              4                    
             / \                  Array: [4, 10, 3]
           10   3
 
3 < 4 → violation! Bubble up:
 
              3                    
             / \                  Array: [3, 10, 4]
           10   4
 
3 is now root.
 
## Insert 5
              3                    
             / \                  Array: [3, 10, 4, 5]
           10   4
           /
          5
 
5 < 10 → violation! Bubble up:
 
              3                    
             / \                  Array: [3, 5, 4, 10]
            5   4
           /
         10
 
## Insert 1
              3                    
             / \                  Array: [3, 5, 4, 10, 1]
            5   4
           / \
         10   1
 
1 < 5 → violation! Swap:
 
              3                    
             / \                  Array: [3, 1, 4, 10, 5]
            1   4
           / \
         10   5
 
1 < 3 → still violation! Swap:
 
              1                    
             / \                  Array: [1, 3, 4, 10, 5]
            3   4
           / \
         10   5
 
Final heap established!

Reading the Array as a Tree:

The array [1, 3, 4, 10, 5] represents:

        1          (index 0)
       / 
      3   4        (indices 1, 2)
     / 
   10   5          (indices 3, 4)

Verify the heap property:

Index 0 (value 1): children at 1,2 (values 3, 4). 1 ≤ 3 ✓, 1 ≤ 4 ✓
Index 1 (value 3): children at 3,4 (values 10, 5). 3 ≤ 10 ✓, 3 ≤ 5 ✓
Index 2 (value 4): no children (2*2+1 = 5, out of bounds)

All checks pass—it's a valid min-heap.

Practice Both Views

When debugging heaps, draw both the tree and array. Check the heap property in the tree view (visually inspect parent-child pairs). Verify index calculations in the array view. The two representations reinforce understanding.

Why Not Use a Binary Search Tree?

A natural question arises: Binary Search Trees (BSTs) also provide O(log n) operations. Why use a heap instead of a BST for priority queues?

The Key Differences:

Heap vs BST for Priority Queue
Aspect	Binary Heap	Balanced BST
Structure	Complete binary tree	Balanced but can have gaps
Ordering	Parent ≤ children (partial)	Left < root < right (total)
Find min	O(1) — always at root	O(log n) — traverse to leftmost
Extract min	O(log n)	O(log n)
Insert	O(log n)	O(log n)
Find arbitrary	O(n) — must search entire heap	O(log n) — binary search
Storage	Array (cache-friendly)	Nodes with pointers
Memory overhead	Low (just the array)	Higher (pointers per node)
Implementation	Simple (~50 lines)	Complex (~200+ lines)

When to Choose Each:

Use a Heap When:

You only need min/max extraction
Simplicity and cache performance matter
You're implementing a priority queue strictly
Memory is constrained

Use a BST When:

You need to find/delete arbitrary elements
You need range queries (all elements between x and y)
You need in-order traversal (sorted iteration)
You're building something more general than a priority queue

The Priority Queue Sweet Spot:

For priority queues specifically, heaps win on almost every metric:

Simpler to implement
Better constant factors
O(1) peek vs O(log n)
Better cache behavior

BSTs only win when you need operations heaps don't support (like searching for arbitrary elements). For pure priority queue use, BSTs are overkill.

The Right Tool for the Job

This is a classic DSA pattern: stronger invariants enable more operations but cost more to maintain. Heaps maintain a weaker invariant (parent ≤ children) than BSTs (left < root < right), so heaps are cheaper to maintain but support fewer operations. Choose based on your requirements.

Real-World Heap Implementations

Standard libraries across languages provide heap implementations. Understanding their APIs helps you use them effectively.

Python: heapq Module

python_heapq.py
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
import heapq
 
# heapq operates on regular lists, transforming them in-place
heap = []
 
# Insert: heappush
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)
 
print(heap)  # [1, 3, 7, 5] — valid min-heap (not sorted!)
 
# Peek: just access index 0
print(heap[0])  # 1
 
# Extract: heappop
print(heapq.heappop(heap))  # 1
print(heapq.heappop(heap))  # 3
 
# Build heap from list: heapify
data = [9, 5, 6, 2, 3]
heapq.heapify(data)  # O(n) in-place heapification
print(data)  # [2, 3, 6, 5, 9]
 
# For max-heap: negate values
max_heap = []
heapq.heappush(max_heap, -5)  # Insert "5" as -5
heapq.heappush(max_heap, -10)
print(-heapq.heappop(max_heap))  # Extract, negate: 10

Java: PriorityQueue

JavaPriorityQueue.java
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
import java.util.PriorityQueue;
import java.util.Comparator;
 
public class HeapExample {
    public static void main(String[] args) {
        // Min-heap by default (natural ordering)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        minHeap.offer(5);  // insert
        minHeap.offer(3);
        minHeap.offer(7);
        
        System.out.println(minHeap.peek());  // 3 (minimum)
        System.out.println(minHeap.poll());  // 3 (extract)
        
        // Max-heap: provide reverse comparator
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
            Comparator.reverseOrder()
        );
        
        maxHeap.offer(5);
        maxHeap.offer(10);
        maxHeap.offer(3);
        
        System.out.println(maxHeap.poll());  // 10 (maximum)
        
        // Custom objects: use Comparator
        PriorityQueue<Task> taskQueue = new PriorityQueue<>(
            Comparator.comparingInt(task -> task.priority)
        );
    }
}

JavaScript/TypeScript: No Built-in (Roll Your Own or Use Library)

typescript_heap.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// JavaScript/TypeScript has no built-in heap!
// Common approaches:
 
// 1. Use a library like 'heap-js' or 'ts-priority-queue'
import { MinHeap } from 'heap-js';
 
const heap = new MinHeap<number>();
heap.push(5);
heap.push(3);
console.log(heap.pop());  // 3
 
// 2. Implement your own (coming in later modules!)
class SimpleMinHeap {
    private data: number[] = [];
    
    push(val: number): void { /* implementation */ }
    pop(): number { /* implementation */ }
    peek(): number { return this.data[0]; }
}

Library Differences Matter

Notice that Python's heapq is min-heap (and requires negation trick for max), while C++'s priority_queue is max-heap by default (and requires greater<T> for min). Always check the documentation for your language's default behavior.

Summary — The Priority Queue Problem Solved

Key Takeaways

•Binary heap = complete binary tree + heap property — Two simple rules define the entire structure.
•Complete tree guarantees O(log n) height — Fundamental for logarithmic operation times.
•Heap property guarantees root is extreme — Enables O(1) peek.
•Array representation eliminates pointers — Simple index formulas navigate the tree.
•Insert bubbles up, extract bubbles down — Both touch at most O(log n) nodes.
•Heaps maintain partial order — Weaker than BST, but sufficient for priority queues.
•Standard libraries provide heap implementations — Python heapq, Java PriorityQueue, C++ priority_queue.

Module Complete:

We've completed the journey from priority queue concept to heap solution:

Page 1: Recalled what priority queues are and why they matter
Page 2: Defined the precise interface (insert, extract, peek)
Page 3: Proved why naive implementations fail
Page 4: Introduced the heap as the elegant solution

What's Next:

The following modules in this chapter will dive into the implementation details:

Module 2: What exactly is a heap? Structure and properties in depth
Module 3: Complete binary tree representation
Module 4: Array-based heap implementation
Module 5: Heap operations — the bubbling algorithms
And more: heapify, complexity analysis, patterns...

Module 1 Complete

You now understand the priority queue ADT, why naive implementations fail, and why heaps succeed. You can explain the two defining properties of a heap and why they enable O(log n) operations. This foundational understanding prepares you for the detailed implementation content ahead.

4 / 4

Loading learning content...

Data Structures & AlgorithmsPriority Queues Revisited

Priority Queues Revisited — Now with Implementation

LevelIntermediate

Duration60 mins

TopicPriority Queues Revisited

4 / 4

The Heap as an Efficient Implementation

The Elegant Solution

Now we meet the binary heap—one of computer science's most elegant data structures.

The heap is simultaneously:

Simple to understand: just two properties define it
Efficient to implement: stored as an array, no pointers needed
Optimal in performance: O(log n) insert and extract, O(1) peek
Cache-friendly: sequential array access patterns
Foundation-laying: basis for heapsort, graph algorithms, and countless applications

Learning Objectives

The Binary Heap Definition

A binary heap is a binary tree with exactly two properties:

Property 1: Shape Property (Complete Binary Tree)

The tree is a complete binary tree: all levels are fully filled except possibly the last, which is filled left-to-right.

Property 2: Heap Property (Ordering)

For a min-heap: Every parent is ≤ its children. For a max-heap: Every parent is ≥ its children.

That's it. These two properties—one about shape, one about ordering—completely define a binary heap.

heap_properties.md
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
# Binary Heap Properties
 
## Property 1: Complete Binary Tree Structure
┌─────────────────────────────────────────────────────┐
│                                                     │
│  Valid Complete Binary Tree:                        │
│                                                     │
│            1         Level 0: 1 node (full)         │
│          /   \                                     │
│         2     3      Level 1: 2 nodes (full)        │
│        / \   /                                      │
│       4   5 6        Level 2: filled left-to-right  │
│                                                     │
│  Invalid (not complete):                            │
│                                                     │
│            1                                        │
│          /   \                                     │
│         2     3      ✗ Level 2 has gaps            │
│          \   /                                     │
│           5 6                                       │
│                                                     │
└─────────────────────────────────────────────────────┘
 
## Property 2: Heap Ordering (Min-Heap Example)
┌─────────────────────────────────────────────────────┐
│                                                     │
│  Valid Min-Heap:     Every parent ≤ children        │
│                                                     │
│            1         1 ≤ 2, 1 ≤ 3 ✓                 │
│          /   \                                     │
│         2     3      2 ≤ 4, 2 ≤ 5, 3 ≤ 6 ✓         │
│        / \   /                                      │
│       4   5 6                                       │
│                                                     │
│  Invalid Min-Heap:                                  │
│                                                     │
│            1                                        │
│          /   \                                     │
│         5     3      5 > 2 ✗ (child smaller)       │
│        / \   /                                      │
│       2   7 6                                       │
│                                                     │
└─────────────────────────────────────────────────────┘

Two Properties, One Power

The beauty of the heap is that these two simple properties are sufficient. Shape ensures O(log n) height. Ordering ensures the extremum is at the root. Together, they enable everything we need.

Understanding the Complete Binary Tree

Why Completeness Matters:

A complete binary tree is filled level-by-level, left-to-right, with no gaps. This specific shape provides two crucial benefits:

Benefit 1: Guaranteed Height Bound

A complete binary tree with n nodes has height exactly ⌊log₂(n)⌋.

Proof intuition:

Level 0 has 1 node
Level 1 has up to 2 nodes
Level 2 has up to 4 nodes
Level k has up to 2^k nodes
Total nodes through level k: 1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1

For n nodes, we need at least ⌊log₂(n)⌋ levels. Completeness ensures we don't need more.

Benefit 2: Array Representation

Because there are no gaps, we can store the tree in an array without wasted space. Element at index i has:

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

This eliminates pointer overhead entirely.

Height vs Capacity for Complete Binary Trees
Height	Max Nodes	Min Nodes	Height in O-notation
0	1	1	O(1) for n=1
1	3	2	O(1) for n=2-3
2	7	4	O(1) for n=4-7
3	15	8	O(1) for n=8-15
10	2,047	1,024	O(10) for n~1000-2000
20	2,097,151	1,048,576	O(20) for n~1 million
30	~1 billion	~500 million	O(30) for n~1 billion

Contrast with Unbalanced Trees:

Unbalanced BST (worst case)     vs     Complete Binary Tree

    1                                        1
     \                                     /   
      2                                   2     3
       \                                /   \  /  
        3              vs              4   5  6   7
         
          4
           
            5

Height: n-1 = 4                        Height: log₂(7) ≈ 2.8

Completeness guarantees logarithmic height, which guarantees logarithmic operation time.

Completeness ≠ Balanced

Understanding the Heap Property

The Heap Property Formally:

For a min-heap, for every node N (except the root):

N.value ≥ N.parent.value

Equivalently, for every parent P:

P.value ≤ P.leftChild.value  (if left child exists)
P.value ≤ P.rightChild.value (if right child exists)

For a max-heap, reverse the inequalities.

What the Heap Property Guarantees:

Heap Property Implications

•Root is the minimum (min-heap): By transitivity, root ≤ children ≤ grandchildren ≤ ... ≤ all nodes. The root is the global minimum.
•Peek is O(1): The minimum is always at index 0 of the array. No searching required.
•Path ordering: Every path from root to leaf is sorted (ascending for min-heap).
•Subtrees are heaps: Any subtree rooted at a heap node is itself a valid heap.

What the Heap Property Does NOT Guarantee:

What Heaps Don't Provide

•Sibling ordering: Left child vs right child have no ordering relationship. Either can be smaller.
•Level ordering: Elements at the same level have no ordering relationship.
•General sorted access: You can only efficiently access the min. Finding the 5th smallest requires 5 extractions.
•Efficient search: Finding if a value exists requires O(n) traversal in the worst case.

heap_property_examples.md
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
# Heap Property Examples (Min-Heap)
 
## Example 1: Valid Min-Heap
           1
         /   \
        3     2
       / \   / \
      7   6 4   5
 
Parent-child relationships all satisfy parent ≤ children:
- 1 ≤ 3 ✓, 1 ≤ 2 ✓
- 3 ≤ 7 ✓, 3 ≤ 6 ✓
- 2 ≤ 4 ✓, 2 ≤ 5 ✓
 
Note: 3 > 2 (siblings unordered) — this is FINE!
Note: 7 > 4 (cousins unordered) — this is FINE!
 
## Example 2: Invalid Min-Heap
           1
         /   \
        4     2
       / \       
      3   6      
 
Violation: 4 > 3 (parent > child) ✗
The value 3 should "bubble up" past 4.
 
## Example 3: Deceptive Valid Heap
           1
         /   \
        8     2
       / \   / \
      9  10 3   4
 
This IS valid! Despite 8 appearing "too big":
- 1 ≤ 8 ✓, 1 ≤ 2 ✓
- 8 ≤ 9 ✓, 8 ≤ 10 ✓
- 2 ≤ 3 ✓, 2 ≤ 4 ✓
 
The heap property is LOCAL (parent vs direct children).
8 being much larger than its sibling 2 is irrelevant.

Don't Expect Full Sorting

How the Heap Achieves O(log n)

Now for the key insight: how do the two heap properties combine to achieve O(log n) for insert and extract?

The Fundamental Operations:

Both insert and extract temporarily violate the heap property, then restore it:

Insert: Add element at the end (maintains completeness), then "bubble up" (restore heap property)
Extract: Remove root, move last element to root (maintains completeness), then "bubble down" (restore heap property)

Why O(log n)?

Bubbling up: Element moves from bottom toward root, at most log n levels. Bubbling down: Element moves from root toward bottom, at most log n levels.

Each level requires O(1) comparisons and swaps. The height is O(log n). Therefore, both operations are O(log n).

operation_overview.md
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
# Insert Operation Overview
 
Initial Heap:            Insert 0:          After Bubble Up:
                         Add at end         0 bubbles to root
 
      1                       1                    0
    /   \                   /   \                /   \
   3     2                 3     2               1     2
  / \   /                 / \   / \             / \   /
 7   6 4                  7   6 4   0          7   6 4   3
                                ↑                      ↑
                          New position          Bubble up
 
Bubbling: Compare 0 with parent 2. 0 < 2, swap.
          Compare 0 with parent 1. 0 < 1, swap.
          0 is now root. Done.
 
Path length: 2 swaps = O(log n)
 
 
# Extract Operation Overview
 
Initial Heap:            Remove root,       After Bubble Down:
                         Replace with last
 
      1                       4                    2
    /   \                   /   \                /   \
   3     2                 3     2               3     4
  / \   /                 / \                   / \
 7   6 4                  7   6                 7   6
                               ↑                     ↑
                          Last to root        Bubble down
 
Bubbling down: Compare 4 with children 3, 2. Swap with smaller (2).
               Compare 4 with children (none on left, none on right).
               4 is a leaf. Done.
 
Path length: 1 swap = O(log n)

The Critical Invariant:

At every step of bubbling, we restore the heap property for an ever-larger subtree:

After bubbling one level, the heap property holds for the moved element and its immediate neighbors
After bubbling to completion, the heap property holds for the entire tree

This local repair propagating upward/downward is what makes heaps efficient. We never examine more than O(log n) nodes.

Heap Operation Complexity Summary
Operation	Complexity	Mechanism	Why It Works
insert	O(log n)	Add at end, bubble up	At most log n levels to traverse
extractMin	O(log n)	Move last to root, bubble down	At most log n levels to traverse
peekMin	O(1)	Return root	Heap property guarantees root is min
build heap	O(n)	Bottom-up heapify	Most nodes near bottom, short bubble distance
isEmpty	O(1)	Check array length	Trivial
size	O(1)	Return array length	Trivial

Completeness Enables Speed

The Array Representation

The Brilliant Trick:

A complete binary tree can be stored in an array without wasting space and without needing pointers. This is called the implicit tree representation.

The Mapping:

For a 0-indexed array:

Root is at index 0
For node at index i:
- Parent is at index: ⌊(i-1)/2⌋
- Left child is at index: 2i + 1
- Right child is at index: 2i + 2

array_representation.ts
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
/**
 * Tree:                 Array:
 * 
 *        10             index: 0  1  2  3  4  5  6
 *      /    \           value: 10 20 15 30 25 40 35
 *    20      15         
 *   /  \    /  \
 *  30  25  40  35
 * 
 * Relationships (0-indexed):
 * - Node 10 at index 0: children at 1, 2
 * - Node 20 at index 1: parent at 0, children at 3, 4
 * - Node 15 at index 2: parent at 0, children at 5, 6
 * - Node 30 at index 3: parent at 1, no children (3*2+1=7 > array.length)
 */
 
class BinaryHeap<T> {
    private data: T[] = [];
    private compare: (a: T, b: T) => number;
    
    constructor(compare: (a: T, b: T) => number) {
        this.compare = compare;
    }
    
    // Index calculations — the heart of array-based heaps
    private parent(i: number): number {
        return Math.floor((i - 1) / 2);
    }
    
    private leftChild(i: number): number {
        return 2 * i + 1;
    }
    
    private rightChild(i: number): number {
        return 2 * i + 2;
    }
    
    private hasLeftChild(i: number): boolean {
        return this.leftChild(i) < this.data.length;
    }
    
    private hasRightChild(i: number): boolean {
        return this.rightChild(i) < this.data.length;
    }
    
    private hasParent(i: number): boolean {
        return i > 0;
    }
    
    // Swapping elements — O(1)
    private swap(i: number, j: number): void {
        [this.data[i], this.data[j]] = [this.data[j], this.data[i]];
    }
}

Why Arrays Work Here:

Normally, trees use explicit pointers (left, right, parent). Why can heaps use arrays?

Completeness: No gaps in the tree = no gaps in the array. Each index corresponds to exactly one node.
Predictable structure: The tree shape is completely determined by the number of elements. We don't need to store the structure—it's implicit in the indices.
Efficient navigation: Parent and child lookups are simple arithmetic—no pointer chasing, excellent cache performance.

Array Representation Benefits

•No pointer overhead (saves memory)
•Cache-friendly (contiguous memory)
•Simple index arithmetic
•Easy to serialize/deserialize
•Dynamic array handles growth

Pointer-Based Downsides

•Memory overhead per node
•Poor cache locality
•More complex traversal code
•Harder to serialize
•Memory fragmentation over time

1-Indexed vs 0-Indexed

Visualizing the Heap — Tree and Array Together

Let's build a mental model that connects the tree visualization with the array storage. When you work with heaps, you'll think in both representations simultaneously.

Example: Building a Min-Heap

Starting with elements: [4, 10, 3, 5, 1]

Insert order and heap evolution:

heap_visualization.md
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
# Building a Min-Heap: Insert [4, 10, 3, 5, 1]
 
## Insert 4
Tree:   4          Array: [4]
        
No bubbling needed (single element).
 
## Insert 10
              4                    Array: [4, 10]
             /
           10
 
10 ≥ 4 → heap property holds.
 
## Insert 3
              4                    
             / \                  Array: [4, 10, 3]
           10   3
 
3 < 4 → violation! Bubble up:
 
              3                    
             / \                  Array: [3, 10, 4]
           10   4
 
3 is now root.
 
## Insert 5
              3                    
             / \                  Array: [3, 10, 4, 5]
           10   4
           /
          5
 
5 < 10 → violation! Bubble up:
 
              3                    
             / \                  Array: [3, 5, 4, 10]
            5   4
           /
         10
 
## Insert 1
              3                    
             / \                  Array: [3, 5, 4, 10, 1]
            5   4
           / \
         10   1
 
1 < 5 → violation! Swap:
 
              3                    
             / \                  Array: [3, 1, 4, 10, 5]
            1   4
           / \
         10   5
 
1 < 3 → still violation! Swap:
 
              1                    
             / \                  Array: [1, 3, 4, 10, 5]
            3   4
           / \
         10   5
 
Final heap established!

Reading the Array as a Tree:

The array [1, 3, 4, 10, 5] represents:

        1          (index 0)
       / 
      3   4        (indices 1, 2)
     / 
   10   5          (indices 3, 4)

Verify the heap property:

Index 0 (value 1): children at 1,2 (values 3, 4). 1 ≤ 3 ✓, 1 ≤ 4 ✓
Index 1 (value 3): children at 3,4 (values 10, 5). 3 ≤ 10 ✓, 3 ≤ 5 ✓
Index 2 (value 4): no children (2*2+1 = 5, out of bounds)

All checks pass—it's a valid min-heap.

Practice Both Views

Why Not Use a Binary Search Tree?

A natural question arises: Binary Search Trees (BSTs) also provide O(log n) operations. Why use a heap instead of a BST for priority queues?

The Key Differences:

Heap vs BST for Priority Queue
Aspect	Binary Heap	Balanced BST
Structure	Complete binary tree	Balanced but can have gaps
Ordering	Parent ≤ children (partial)	Left < root < right (total)
Find min	O(1) — always at root	O(log n) — traverse to leftmost
Extract min	O(log n)	O(log n)
Insert	O(log n)	O(log n)
Find arbitrary	O(n) — must search entire heap	O(log n) — binary search
Storage	Array (cache-friendly)	Nodes with pointers
Memory overhead	Low (just the array)	Higher (pointers per node)
Implementation	Simple (~50 lines)	Complex (~200+ lines)

When to Choose Each:

Use a Heap When:

You only need min/max extraction
Simplicity and cache performance matter
You're implementing a priority queue strictly
Memory is constrained

Use a BST When:

You need to find/delete arbitrary elements
You need range queries (all elements between x and y)
You need in-order traversal (sorted iteration)
You're building something more general than a priority queue

The Priority Queue Sweet Spot:

For priority queues specifically, heaps win on almost every metric:

Simpler to implement
Better constant factors
O(1) peek vs O(log n)
Better cache behavior

BSTs only win when you need operations heaps don't support (like searching for arbitrary elements). For pure priority queue use, BSTs are overkill.

The Right Tool for the Job

Real-World Heap Implementations

Standard libraries across languages provide heap implementations. Understanding their APIs helps you use them effectively.

Python: heapq Module

python_heapq.py
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
import heapq
 
# heapq operates on regular lists, transforming them in-place
heap = []
 
# Insert: heappush
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)
 
print(heap)  # [1, 3, 7, 5] — valid min-heap (not sorted!)
 
# Peek: just access index 0
print(heap[0])  # 1
 
# Extract: heappop
print(heapq.heappop(heap))  # 1
print(heapq.heappop(heap))  # 3
 
# Build heap from list: heapify
data = [9, 5, 6, 2, 3]
heapq.heapify(data)  # O(n) in-place heapification
print(data)  # [2, 3, 6, 5, 9]
 
# For max-heap: negate values
max_heap = []
heapq.heappush(max_heap, -5)  # Insert "5" as -5
heapq.heappush(max_heap, -10)
print(-heapq.heappop(max_heap))  # Extract, negate: 10

Java: PriorityQueue

JavaPriorityQueue.java
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
import java.util.PriorityQueue;
import java.util.Comparator;
 
public class HeapExample {
    public static void main(String[] args) {
        // Min-heap by default (natural ordering)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        minHeap.offer(5);  // insert
        minHeap.offer(3);
        minHeap.offer(7);
        
        System.out.println(minHeap.peek());  // 3 (minimum)
        System.out.println(minHeap.poll());  // 3 (extract)
        
        // Max-heap: provide reverse comparator
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
            Comparator.reverseOrder()
        );
        
        maxHeap.offer(5);
        maxHeap.offer(10);
        maxHeap.offer(3);
        
        System.out.println(maxHeap.poll());  // 10 (maximum)
        
        // Custom objects: use Comparator
        PriorityQueue<Task> taskQueue = new PriorityQueue<>(
            Comparator.comparingInt(task -> task.priority)
        );
    }
}

JavaScript/TypeScript: No Built-in (Roll Your Own or Use Library)

typescript_heap.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// JavaScript/TypeScript has no built-in heap!
// Common approaches:
 
// 1. Use a library like 'heap-js' or 'ts-priority-queue'
import { MinHeap } from 'heap-js';
 
const heap = new MinHeap<number>();
heap.push(5);
heap.push(3);
console.log(heap.pop());  // 3
 
// 2. Implement your own (coming in later modules!)
class SimpleMinHeap {
    private data: number[] = [];
    
    push(val: number): void { /* implementation */ }
    pop(): number { /* implementation */ }
    peek(): number { return this.data[0]; }
}

Library Differences Matter

Summary — The Priority Queue Problem Solved

Key Takeaways

•Binary heap = complete binary tree + heap property — Two simple rules define the entire structure.
•Complete tree guarantees O(log n) height — Fundamental for logarithmic operation times.
•Heap property guarantees root is extreme — Enables O(1) peek.
•Array representation eliminates pointers — Simple index formulas navigate the tree.
•Insert bubbles up, extract bubbles down — Both touch at most O(log n) nodes.
•Heaps maintain partial order — Weaker than BST, but sufficient for priority queues.
•Standard libraries provide heap implementations — Python heapq, Java PriorityQueue, C++ priority_queue.

Module Complete:

We've completed the journey from priority queue concept to heap solution:

Page 1: Recalled what priority queues are and why they matter
Page 2: Defined the precise interface (insert, extract, peek)
Page 3: Proved why naive implementations fail
Page 4: Introduced the heap as the elegant solution

What's Next:

The following modules in this chapter will dive into the implementation details:

Module 2: What exactly is a heap? Structure and properties in depth
Module 3: Complete binary tree representation
Module 4: Array-based heap implementation
Module 5: Heap operations — the bubbling algorithms
And more: heapify, complexity analysis, patterns...

Module 1 Complete

4 / 4