What Is a Heap?

A heap is a complete binary tree stored as an ARRAY (remember Chapter 08’s array representation?) where every parent is ≤ its children (min-heap) or ≥ its children (max-heap).

The Array Representation IS the Heap

Min-heap tree view:        Array layout:
        1                  [1, 3, 5, 7, 4, 8]
       / \                  0  1  2  3  4  5
      3   5
     / \  /               Parent of i:     (i - 1) // 2
    7  4  8               Left child of i:  2*i + 1
                          Right child of i: 2*i + 2

There is no separate "heap object" with pointers — the array IS the data structure. The tree shape is implicit from index math.

Python’s heapq Module

Python provides MIN-heaps only. For max-heaps, negate the values.

import heapq

# heapq operates on regular Python LISTS — no special class needed.
heap = []                        # Start with empty list
heapq.heappush(heap, 5)          # O(log n) — push and maintain heap property
heapq.heappush(heap, 1)          # O(log n)
heapq.heappush(heap, 3)          # O(log n)

smallest = heapq.heappop(heap)   # O(log n) — removes and returns the SMALLEST
# smallest = 1, heap is now [3, 5]

# Peek at smallest without removing: heap[0] — O(1)

# Convert a list into a heap IN-PLACE: O(n) — NOT O(n log n)!
# This is faster than pushing n elements individually.
data = [5, 3, 8, 1, 2]
heapq.heapify(data)  # data is now a valid min-heap: [1, 2, 8, 5, 3]

Max-heap trick: Python only has min-heaps. For a max-heap, negate values:

heapq.heappush(heap, -value)     # Store negative
largest = -heapq.heappop(heap)   # Negate back when retrieving

C# equivalent: PriorityQueue<TElement, TPriority> (min-heap by default, .NET 6+)

TS equivalent: No built-in — you’d implement one or use a library

Complexity

Operation Complexity Why

heappush

O(log n)

Bubble up through tree of height log n

heappop

O(log n)

Swap root with last, bubble down

heap[0] (peek)

O(1)

Root is always at index 0

heapify

O(n)

⭐ NOT O(n log n) — uses sift-down from leaves

Build by n pushes

O(n log n)

Each push is O(log n)

When to Use a Heap

  1. "Top K" or "Kth largest/smallest" — maintain a heap of size k

  2. Merge K sorted lists — heap stores one element from each list

  3. Continuous median — two heaps (max-heap for lower half, min-heap for upper)

  4. Event-driven simulation / scheduling — process events by priority

  5. Dijkstra’s algorithm — extract minimum-distance node

Exercises