Introduction to Heaps

You're building a task scheduler. Tasks have priorities. High priority tasks should execute first, regardless of when they were added.

A queue won't work—FIFO means first task added runs first. You need priority-based ordering.

Enter heaps. Always gives you the highest (or lowest) priority element in O(1). Insert in O(log n). Perfect for priority queues.

What's a Heap?

A binary tree with two properties:

1. Complete binary tree: All levels full except possibly last, which fills left to right.

2. Heap property:

• Max heap: Every parent ≥ its children
• Min heap: Every parent ≤ its children

Max heap example:

       10
     /    \
    8      9
   / \    /
  5   7  6

10 ≥ 8 and 10 ≥ 9. 8 ≥ 5 and 8 ≥ 7. 9 ≥ 6. All parents ≥ children. Max heap.

Root is always the maximum.

Min heap: Same structure, but every parent ≤ children. Root is always minimum.

Array Representation

Heaps are stored in arrays. No pointers needed.

Heap:
       10
     /    \
    8      9
   / \    /
  5   7  6

Array: [10, 8, 9, 5, 7, 6]

For node at index i:

• Parent at (i - 1) // 2
• Left child at 2i + 1
• Right child at 2i + 2

Example: Node 8 is at index 1. Parent: (1-1)//2 = 0 (which is 10). Left child: 2(1)+1 = 3 (which is 5). Right child: 2(1)+2 = 4 (which is 7).

Complete binary tree property means no gaps in array. Efficient.

Why Heaps?

Priority queues: Get highest/lowest priority in O(1). Insert in O(log n).

Heap sort: O(n log n) sorting. Build heap, repeatedly extract max/min.

Top K elements: Find K largest/smallest in O(n log k). Better than sorting (O(n log n)).

Median maintenance: Track running median with two heaps. O(log n) per element.

Max Heap vs Min Heap

Max heap: Parent ≥ children. Root is maximum.

Use when you need maximum element quickly (largest task priority, highest value).

Min heap: Parent ≤ children. Root is minimum.

Use when you need minimum element quickly (shortest path, earliest deadline).

Python's heapq

Python has built-in heap (min heap).

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)

print(heap)  # [1, 3, 7, 5] (min heap, root is 1)

min_val = heapq.heappop(heap)
print(min_val)  # 1
print(heap)  # [3, 5, 7]

Min heap by default. For max heap, negate values.

# Max heap trick
heapq.heappush(heap, -5)  # Insert 5 as -5
heapq.heappush(heap, -3)  # Insert 3 as -3
max_val = -heapq.heappop(heap)  # Pop and negate

Building a Heap

Naive: Insert elements one by one. O(n log n).

Heapify: Build heap in O(n). Bottom-up approach.

def heapify(arr):
    n = len(arr)
    # Start from last non-leaf node
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, n, i)

def sift_down(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        sift_down(arr, n, largest)

arr = [3, 9, 2, 1, 4, 5]
heapify(arr)
print(arr)  # Max heap: [9, 4, 5, 1, 3, 2]

Heapify is O(n). Better than repeated insertions.

Heap vs BST

Heaps are specialized. Great for priority queues, not for general searching.

Complete Binary Tree Property

Why complete? Allows array representation without gaps.

Incomplete tree:

    10
   /
  8
   \
    7

Array: [10, 8, ?, 7] — gap at index 2. Wasteful.

Complete tree:

    10
   /  \
  8    9
 /
7

Array: [10, 8, 9, 7] — no gaps. Efficient.

Example: Find Kth Largest

Using min heap of size k.

import heapq

def find_kth_largest(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)  # Min heap of k elements
    
    for num in nums[k:]:
        if num > heap[0]:  # Larger than smallest in heap
            heapq.heapreplace(heap, num)
    
    return heap[0]

print(find_kth_largest([3, 2, 1, 5, 6, 4], 2))  # 5

Keep k largest in heap. Root is kth largest. O(n log k).

The Foundation

Heaps are simple but powerful:

• Complete binary tree + heap property
• Array representation with index formulas
• O(1) access to max/min, O(log n) insert/delete

Understanding heaps means understanding:

• When you need priority-based access
• How complete binary trees enable array storage
• The trade-off: fast priority access vs general searching

Master heaps, and you'll solve priority queue problems efficiently.