Heaps

Introduction

Heap is complete binary tree maintaining heap property: every parent satisfies ordering constraint relative to children. Min-heap: parent <= children. Max-heap: parent >= children. Enables O(log n) insertion/deletion while maintaining order, O(1) minimum/maximum access.

Contrast with binary search trees: BST enables O(log n) search for arbitrary values, but finding min/max requires traversal. Heaps sacrifice arbitrary search capability (no O(log n) search) for guarantee on extrema.

Cornerstone of priority queues: always access highest-priority (min/max) element. Applications: Dijkstra's algorithm (expand lowest-cost node), Huffman coding (combine lowest-frequency nodes), operating system scheduling (execute highest-priority task).

"Heaps elegantly solve the priority queue problem: maintain extrema while enabling efficient updates. Their array representation makes them both memory-efficient and cache-friendly." -- Data structure design

Heap Property and Completeness

Heap Property

Heap ordering property: parent-child relationship constraint. Min-heap: key(parent) <= key(child). Max-heap: key(parent) >= key(child).

Critical: only parent-child ordering guaranteed. Siblings unordered. Means: minimum at root (min-heap), maximum at root (max-heap).

Completeness

Complete binary tree: all levels filled except possibly last (filled left-to-right). Constraint on structure: enables array representation without gaps. Height = ceil(log n) for n elements.

Complete heap (5 elements):
 1
 / \
 2 3
 / \
 4 5

Not complete: 5 right child of 2? Would require 6 elements total.

Height

Height = O(log n). All operations exploit this: insertion/deletion bubble up/down at most height edges = O(log n).

Min-Heaps and Max-Heaps

Min-Heap

Minimum element at root. Used for: priority queue (lower priority value = higher priority), Dijkstra's algorithm (expand lowest-cost vertex).

Max-Heap

Maximum element at root. Used for: priority queue (higher priority value = higher priority), heap sort (extract elements descending).

Conversion

Min-heap to max-heap: negate all values, or use comparator (reverse comparison). Structurally identical, just different comparison direction.

Example Min-Heap

 1
 / \
 2 3
 / \ /
 4 5 6

Heap property: 1 <= 2, 1 <= 3, 2 <= 4, 2 <= 5, 3 <= 6 (satisfied)
Minimum: 1 (at root)

Array Representation of Heaps

Index Mapping

Store heap elements in array index 0 to n-1. Complete tree structure maps to array naturally:

Node at index i:
 Left child: 2*i + 1
 Right child: 2*i + 2
 Parent: (i - 1) / 2 (integer division)

Example (1-indexed for clarity):
Index: 1 2 3 4 5 6 7
Element: [1, 2, 3, 4, 5, 6, 7]
 1
 / \
 2 3
 / \ / \
 4 5 6 7

Advantages

• No explicit pointers (array compact)
• Cache-friendly (contiguous memory)
• Parent/child access O(1) (arithmetic)
• Space-efficient (no node objects)

Array Resizing

If array full, allocate larger array, copy elements. Amortized O(1) per operation with doubling.

Insert Operation and Bubble Up

Algorithm

def insert(heap, value):
 heap.append(value) # Add to end
 bubble_up(heap, len(heap) - 1)

def bubble_up(heap, index):
 while index > 0:
 parent_index = (index - 1) // 2
 if heap[index] < heap[parent_index]: # Min-heap comparison
 swap(heap, index, parent_index)
 index = parent_index
 else:
 break

Example

Insert 0 into min-heap [1, 2, 3, 4, 5]:
Initial: [1, 2, 3, 4, 5, 0]
 1
 / \
 2 3
 / \ /
 4 5 0 (0 at index 5)

Bubble up:
0 < parent 2, swap → [1, 0, 3, 4, 5, 2]
 1
 / \
 0 3
 / \ /
4 5 2

0 < parent 1, swap → [0, 1, 3, 4, 5, 2]
 0
 / \
 1 3
 / \ /
4 5 2

Done: 0 at root (min-heap property restored)

Time Complexity

Bubble up at most height steps = O(log n). Each step: comparison, swap. Total O(log n).

Delete Min/Max and Bubble Down

Delete Root

def delete_min(heap):
 if len(heap) == 0:
 raise IndexError("Heap empty")
 min_value = heap[0]
 heap[0] = heap[-1] # Move last to root
 heap.pop() # Remove last
 bubble_down(heap, 0)
 return min_value

def bubble_down(heap, index):
 while True:
 smallest = index
 left_child = 2 * index + 1
 right_child = 2 * index + 2

 if left_child < len(heap) and heap[left_child] < heap[smallest]:
 smallest = left_child
 if right_child < len(heap) and heap[right_child] < heap[smallest]:
 smallest = right_child

 if smallest != index:
 swap(heap, index, smallest)
 index = smallest
 else:
 break

Example

Delete min from [1, 2, 3, 4, 5, 6]:
Min: 1
Move last (6) to root: [6, 2, 3, 4, 5]
 6
 / \
 2 3
 / \
4 5

Bubble down 6:
Smaller child: 2 (left), swap → [2, 6, 3, 4, 5]
 2
 / \
 6 3
 / \
4 5

Smaller child: 4, swap → [2, 4, 3, 6, 5]
 2
 / \
 4 3
 / \
6 5

Done: 2 at root, heap property restored

Time Complexity

Bubble down at most height steps = O(log n).

Heapify: Building Heaps from Arrays

Naive Approach

Insert each element: n insertions * O(log n) per insert = O(n log n).

Efficient Heapify

def heapify(array):
 # Start from last non-leaf node, bubble down
 for i in range(len(array) // 2 - 1, -1, -1):
 bubble_down(array, i)

Time: O(n)

Intuition: bottom-up approach. Leaf nodes already satisfy heap property.
Bubble down non-leaves. Total work: O(n) not O(n log n).

Analysis

Why O(n)? Worst case: bubble down O(log n) at root. But most nodes near bottom (leaves), take ~0 bubble-down steps. Average work per node: O(1). Total: O(n).

Build Heap from Data

Heapify is critical: given unordered array, build heap in O(n) instead of O(n log n). Foundation for heap sort.

Heap Sort Algorithm

Algorithm

def heap_sort(array):
 # Build max-heap in-place
 for i in range(len(array) // 2 - 1, -1, -1):
 bubble_down_max(array, i)

 # Extract elements from heap
 for i in range(len(array) - 1, 0, -1):
 swap(array, 0, i) # Move root (max) to position i
 bubble_down_max(array, 0, i) # Heapify array[0:i]

Time: O(n log n), Space: O(1) in-place

Example

Sort [3, 1, 4, 1, 5]:
Build max-heap: [5, 3, 4, 1, 1]
 5
 / \
 3 4
 / \
1 1

Extract: swap 5 with last (index 4), heapify [4, 3, 1, 1] | 5
→ [4, 3, 1, 1, 5]
→ [4, 1, 1, 3] | 3, 5
→ [3, 1, 1, 4] | 4, 5
→ [1, 1, 3] | 3, 4, 5
→ [1, 1] | 1, 3, 4, 5
→ [1] | 1, 1, 3, 4, 5

Sorted: [1, 1, 3, 4, 5]

Comparison with QuickSort

Heap sort: guaranteed O(n log n), not adaptive (same performance sorted/unsorted). QuickSort: O(n log n) average, O(n^2) worst, faster in practice (cache-friendly, less data movement). Most systems prefer QuickSort unless worst-case guarantee needed.

Priority Queues Using Heaps

Implementation

class PriorityQueue:
 def __init__(self):
 self.heap = []

 def enqueue(self, value, priority):
 self.heap.append((priority, value))
 bubble_up(self.heap, len(self.heap) - 1)

 def dequeue(self):
 if not self.heap:
 raise IndexError("Queue empty")
 min_priority, value = self.heap[0]
 self.heap[0] = self.heap[-1]
 self.heap.pop()
 bubble_down(self.heap, 0)
 return value, min_priority

 def peek(self):
 if not self.heap:
 raise IndexError("Queue empty")
 return self.heap[0][1]

Operations

Enqueue: O(log n). Dequeue: O(log n). Peek: O(1). No ordering required during enqueue (unlike sorted array), yet dequeue returns minimum in O(log n).

Dijkstra's Algorithm with Priority Queue

Priority queue enables efficient Dijkstra: expand lowest-cost vertex. O((V + E) log V) vs. O(V^2) without priority queue.

Time and Space Complexity

Space

Heap elements stored in array (no additional structure). Auxiliary space O(1) for heap operations (recursion depth O(log n) but not counted as auxiliary in many analyses).

Heap Variants: Fibonacci, Binomial

Fibonacci Heaps

Advanced structure: decrease-key O(1) amortized (vs. O(log n) binary heap). More complex implementation. Used in Dijkstra for dense graphs (improves complexity to O(V log V + E)).

Binomial Heaps

Forest of binomial trees. Merge heaps efficiently O(log n). Decrease-key O(log n). Alternative to Fibonacci when merge or decrease-key frequent.

Ternary Heaps

Each node up to 3 children. Reduces tree height slightly (log_3 n vs. log_2 n), decreases bubble-down operations. Marginal improvement, rarely used.

Practical Choice

Binary heaps: simplest, cache-friendly, sufficient for most applications. Fibonacci/binomial: complex, only beneficial for specific algorithms with many decrease-key operations.

Applications

Dijkstra's Shortest Path

Priority queue: expand lowest-cost vertex. O((V + E) log V) with heap vs. O(V^2) without.

Prim's Minimum Spanning Tree

Greedy: add cheapest edge connecting tree to non-tree. Priority queue tracks candidate edges.

Huffman Coding

Repeatedly combine two lowest-frequency nodes. Min-heap enables O(n log n) algorithm.

Heap Sort

In-place sorting. O(n log n) guaranteed. Rarely used in practice (QuickSort faster average).

Load Balancing

Assign task to server with minimum load. Min-heap tracks server loads, update on task completion.

Event Simulation

Priority queue of events (ordered by time). Dequeue next event, process, enqueue resulting events.

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. "Introduction to Algorithms." MIT Press, 3rd edition, 2009.
• Knuth, D. E. "The Art of Computer Programming, Volume 1: Fundamental Algorithms." Addison-Wesley, 3rd edition, 1997.
• Sedgewick, R., and Wayne, K. "Algorithms, Part I." Addison-Wesley, 4th edition, 2011.
• Fibonacci, L. "The Art of Thinking Combinatorially." American Scientist, vol. 88, 2000.
• Fredman, M. L., and Tarjan, R. E. "Fibonacci Heaps and Their Uses." Journal of the ACM, vol. 34, 1987.