📚 Heaps & Priority Queues

A Comprehensive Study Guide for CS210

📑 Table of Contents

1. Introduction to Collections

Fred Brooks: "Show me your code and conceal your data structures, and I shall continue to be mystified. Show me your data structures, and I won't usually need your code; it'll be obvious."

A collection is a data type that stores groups of items. Different collections have different key operations and are implemented with different data structures.

Common Collections

Data Type Key Operations Data Structure
Stack PUSH, POP Linked list, resizing array
Queue ENQUEUE, DEQUEUE Linked list, resizing array
Priority Queue INSERT, DELETE-MAX Binary heap
Symbol Table PUT, GET, DELETE BST, hash table
Set ADD, CONTAINS, DELETE BST, hash table

2. Priority Queue ADT

Definition

A Priority Queue is a collection where you insert and delete items, but unlike a regular queue, you remove the largest (or smallest) item, not the item that was added first or last.

Key Differences from Other Collections

  • Stack: Remove the item most recently added (LIFO)
  • Queue: Remove the item least recently added (FIFO)
  • Randomized Queue: Remove a random item
  • Priority Queue: Remove the largest (or smallest) item

Priority Queue API (Java)

public class MaxPQ<Key extends Comparable<Key>> { // Create an empty priority queue MaxPQ() // Create a priority queue with given keys MaxPQ(Key[] a) // Insert a key into the priority queue void insert(Key v) // Return and remove the largest key Key delMax() // Is the priority queue empty? boolean isEmpty() // Return the largest key (without removing) Key max() // Number of entries in the priority queue int size() }
⚠️ Important: The generic type Key must implement Comparable<Key> so that items can be ordered.

Example Operations

Example: Priority Queue Operations

Operation Argument Return Value Contents (unordered)
insert P - P
insert Q - P Q
insert E - P Q E
removeMax - Q P E
insert X - P E X
insert A - P E X A
insert M - P E X A M
removeMax - X P E M A

3. Priority Queue Applications

Priority queues generalize stacks, queues, and randomized queues, and have numerous real-world applications:

🌟 Real-World Applications

  • Event-driven simulation: Customers in a line, colliding particles
  • Numerical computation: Reducing roundoff error
  • Data compression: Huffman codes
  • Graph searching: Dijkstra's algorithm, Prim's algorithm
  • Number theory: Sum of powers
  • Artificial intelligence: A* search
  • Statistics: Online median in data stream
  • Operating systems: Load balancing, interrupt handling
  • Computer networks: Web cache
  • Discrete optimization: Bin packing, scheduling
  • Spam filtering: Bayesian spam filter

4. Complete Binary Trees

Binary Tree

A binary tree is either empty or a node with links to left and right binary trees (each node has at most 2 children).

Complete Binary Tree

A complete tree is perfectly balanced, except possibly for the bottom level. All levels are completely filled except possibly the last level, which is filled from left to right.

Complete Binary Tree Example (N = 16, height = 4)

                    ○
                   / \
                  ○   ○
                 / \ / \
                ○ ○ ○ ○
               /\\/\\/\\/\
              ○○○○○○○○○

📐 Important Property

Height of a complete tree with N nodes is ⌊lg N⌋

The height increases only when N is a power of 2.

This logarithmic height is what makes heaps efficient!

Why Complete Binary Trees?

✅ Advantages

  • Guaranteed logarithmic height
  • Can be stored efficiently in an array
  • No explicit links needed
  • Easy to navigate using array indices

⚠️ Constraints

  • Must maintain completeness property
  • Insertions must go at the end
  • Deletions require restructuring

5. Heap Definition & Properties

Binary Heap

A binary heap is an array representation of a heap-ordered complete binary tree.

Two Key Properties

1. Heap-Order Property

For every internal node v other than the root:

key(v) ≥ key(parent(v))

This means: Parent's key is no smaller than children's keys

Or equivalently: Each node's key must be less than or equal to its parent's key.

2. Complete Binary Tree Property

The tree must be a complete binary tree (as defined above).

Types of Heaps

Heap Type Property Root Contains
Max Heap Parent ≥ Children Maximum element
Min Heap Parent ≤ Children Minimum element
📝 Note: By default, when we say "heap" we typically mean a max heap. This study guide focuses on max heaps, but the concepts apply equally to min heaps with reversed comparisons.

Array Representation

Array Indices for Navigation

In a heap stored in array a[] starting at index 1:

  • Root: a[1]
  • Parent of node at k: a[k/2]
  • Left child of node at k: a[2k]
  • Right child of node at k: a[2k+1]

Heap Visualization (Max Heap)

Tree representation:

           T (1)
          / \
        S(2) R(3)
       / \   / \
     P(4)N(5)O(6)A(7)
     /\  /\
   E I  H G
   8 9 10 11

Array representation:

0
-
1
T
2
S
3
R
4
P
5
N
6
O
7
A
8
E
9
I
10
H
11
G

Note: Index 0 is not used (we start at index 1)

🎯 Key Properties

  • The largest key is always at a[1] (the root)
  • We can navigate the tree using simple arithmetic on array indices
  • No explicit links (pointers) are needed!
  • Space efficient: only need array of size N+1

6. Heap Operations

6.1 Insert Operation (Swim Up)

Insert Algorithm

  1. Add the new key at the end of the array (position N+1)
  2. The new node becomes the new "last node" of the complete tree
  3. Swim up: Compare with parent and swap if necessary
  4. Repeat until heap order is restored

Swim Helper Method

private void swim(int k) { // While not at root AND child > parent while (k > 1 && less(k/2, k)) { exch(k, k/2); // Swap with parent k = k/2; // Move up to parent } }

Insert Method

public void insert(Key x) { pq[++N] = x; // Add at end and increment size swim(N); // Restore heap order }

Example: Insert 'S' into heap

Before:              After adding:         After swim:
     T                    T                    S
    / \                  / \                  / \
   P   R                P   R                T   R
  / \                  / \ /                / \ /
 N   H                N  H S              N  H P
    
Heap: T P R N H    → T P R N H S  →  S T R N H P
                     (violates)       (restored)

⏱️ Time Complexity of Insert

At most 1 + lg N compares

Why? In the worst case, we swim from the bottom to the top of the tree, and the height is ⌊lg N⌋.

6.2 Delete Maximum Operation (Sink Down)

Delete Max Algorithm

  1. Save the root value (maximum) to return later
  2. Exchange root with the last node (at position N)
  3. Decrement N (remove last position)
  4. Sink down: Compare with children and swap with larger child if necessary
  5. Repeat until heap order is restored
  6. Return the saved maximum value

Sink Helper Method

private void sink(int k) { while (2*k <= N) { // While has at least one child int j = 2*k; // Left child // Choose larger child if (j < N && less(j, j+1)) j++; // If parent >= larger child, done if (!less(k, j)) break; exch(k, j); // Swap with larger child k = j; // Move down } }

Delete Max Method

public Key delMax() { Key max = pq[1]; // Get root (maximum) exch(1, N--); // Exchange with last, decrement N sink(1); // Restore heap order pq[N+1] = null; // Prevent loitering return max; }

Example: Delete maximum from heap

Before:              After exchange:      After sink:
     T                    H                    S
    / \                  / \                  / \
   S   R                S   R                P   R
  / \ / \              / \ /                / \ /
 P  N O  A            P  N O  A            N  H O  A

Remove T  →  Exchange with H  →  Sink H down
(return T)   (violates order)    (restored)

❓ Why swap with the larger child?

If we swapped with the smaller child, we might end up with a parent smaller than its other child, violating heap order. By swapping with the larger child, we ensure both children will be smaller than the promoted parent.

⏱️ Time Complexity of Delete Max

At most 2 lg N compares

Why 2? At each level, we compare the two children (1 compare) and then compare with parent (1 more compare). Height is ⌊lg N⌋.

💡 "Peter Principle": In swim, a node is promoted to its level of incompetence (can't go higher). In sink, there's a "power struggle" where the better subordinate gets promoted!

7. Complete Java Implementation

public class MaxPQ<Key extends Comparable<Key>> { private Key[] pq; // Array to store heap private int N; // Number of elements // Constructor public MaxPQ(int capacity) { pq = (Key[]) new Comparable[capacity + 1]; } // Is the priority queue empty? public boolean isEmpty() { return N == 0; } // Number of elements public int size() { return N; } // Insert a key public void insert(Key key) { pq[++N] = key; swim(N); } // Delete and return maximum public Key delMax() { Key max = pq[1]; exch(1, N--); sink(1); pq[N+1] = null; // Prevent loitering return max; } /******************************************* * Helper functions for heap operations *******************************************/ private void swim(int k) { while (k > 1 && less(k/2, k)) { exch(k, k/2); k = k/2; } } private void sink(int k) { while (2*k <= N) { int j = 2*k; if (j < N && less(j, j+1)) j++; if (!less(k, j)) break; exch(k, j); k = j; } } /******************************************* * Helper functions for comparisons and swaps *******************************************/ private boolean less(int i, int j) { return pq[i].compareTo(pq[j]) < 0; } private void exch(int i, int j) { Key t = pq[i]; pq[i] = pq[j]; pq[j] = t; } }
📝 Implementation Notes:
  • Array indices start at 1 (index 0 is not used)
  • For simplicity, this uses fixed capacity (could be made resizing)
  • Generic type Key must implement Comparable
  • Setting pq[N+1] = null prevents loitering (allows garbage collection)

8. Time Complexity Analysis

Elementary Implementations vs Binary Heap

Implementation Insert Delete Max Get Max
Unordered Array 1 N N
Ordered Array N 1 1
Binary Heap log N log N 1

🎯 Why Binary Heap is Optimal

  • Logarithmic operations: Both insert and delete max are O(log N)
  • Constant time max: Getting the maximum is O(1)
  • Space efficient: Only O(N) space needed
  • Simple implementation: Just an array with two helper functions

Detailed Analysis

Insert Operation

  • Best case: O(1) - element already in correct position
  • Worst case: O(log N) - swim from bottom to top
  • Average case: O(log N)

Delete Max Operation

  • Best case: O(log N) - still need to check children
  • Worst case: O(log N) - sink from top to bottom
  • Average case: O(log N)
💡 Why log N? Because the height of a complete binary tree with N nodes is ⌊log₂ N⌋, and in the worst case, we traverse from one end to the other.

9. Heap Sort

Heapsort Algorithm

Heapsort is a comparison-based sorting algorithm that uses a binary heap to sort an array in O(N log N) time using O(1) extra space.

Algorithm Overview

  1. Build heap: Rearrange array into a heap
  2. Sortdown: Repeatedly remove the maximum (root) and place at end

Using Priority Queue for Sorting

// Simple approach using priority queue public static void sort(Comparable[] a) { int N = a.length; MaxPQ pq = new MaxPQ(N); // Phase 1: Insert all elements for (int i = 0; i < N; i++) pq.insert(a[i]); // Phase 2: Remove in sorted order for (int i = N-1; i >= 0; i--) a[i] = pq.delMax(); }

Time Complexity

⏱️ Runtime Analysis

  • Building heap: O(N log N) with repeated inserts
  • Removing all elements: O(N log N)
  • Total: O(N log N)
  • Space: O(N) for the heap

Comparison with Other Sorts

Algorithm Time Complexity Space Stable?
Insertion Sort O(N²) O(1) ✅ Yes
Selection Sort O(N²) O(1) ❌ No
Merge Sort O(N log N) O(N) ✅ Yes
Heap Sort O(N log N) O(N) ❌ No
Quick Sort O(N log N)* O(log N) ❌ No

* Average case; worst case is O(N²)

✅ Advantages of Heapsort

  • Guaranteed O(N log N) performance
  • In-place sorting (no extra array needed)
  • No worst-case quadratic behavior
  • Simple implementation

⚠️ Disadvantages

  • Not stable
  • Poor cache performance
  • Slower than quicksort in practice
  • Not adaptive (doesn't benefit from partial order)

10. Practice Problems & Key Concepts

Practice Problem 1: Build a Max Heap

Problem

Insert the following elements into an empty max heap in order: 2, 5, 16, 4, 10, 23, 39, 18, 26, 15

Solution Steps

The solution requires building up the heap one element at a time, swimming up after each insertion. The final heap should be:

           39
          /  \
        26    23
       / \   / \
     18  15 16  5
     / \ /
    2  4 10

Array: [-, 39, 26, 23, 18, 15, 16, 5, 2, 4, 10]

Practice Problem 2: Delete Operations

Problem

From the heap above, perform three deleteMax() operations. Show the heap after each deletion.

Hint

Remember: Exchange root with last element, remove last, then sink down.

Practice Problem 3: Is this a Heap?

Problem

Determine if the following binary tree is a valid max heap:

        8
       / \
      30  12
     / \  / \
    60 40 50 60

Answer

NO - The smallest element in a heap should always be found in the root node. Here, 8 is the root but it's smaller than its children (30 and 12), violating the heap-order property.

🎯 Key Concepts to Remember

  • Complete Binary Tree: All levels filled except possibly last, which fills left-to-right
  • Heap-Order Property: Parent ≥ Children (max heap) or Parent ≤ Children (min heap)
  • Array Representation: Parent at k/2, children at 2k and 2k+1
  • Root is at index 1: Makes math simpler (parent = k/2)
  • Maximum always at root: O(1) access to max element
  • Height is ⌊log N⌋: Guarantees logarithmic operations
  • Swim up: Used after insert, compares with parent
  • Sink down: Used after delete max, compares with larger child
  • Both operations: O(log N) time complexity
  • No explicit links needed: Array arithmetic handles navigation

📚 Study Tips

  • Draw it out: Visualize heap operations by drawing trees
  • Trace the code: Follow swim and sink operations step-by-step
  • Understand the why: Know why we swap with larger child in sink
  • Practice array indexing: Get comfortable with k/2, 2k, 2k+1
  • Memorize complexities: Insert O(log N), Delete Max O(log N), Get Max O(1)
  • Compare implementations: Understand trade-offs vs other data structures

Common Mistakes to Avoid

  • ❌ Starting array at index 0 (makes parent/child math harder)
  • ❌ Forgetting to set deleted elements to null (memory leak)
  • ❌ Swapping with smaller child in sink (violates heap order)
  • ❌ Not checking array bounds in sink
  • ❌ Confusing max heap with min heap properties
  • ❌ Thinking heap is sorted (it's only partially ordered)