Heaps (Min/Max) — Complete Tutorial

The Story That Explains Heaps

A heap is a complete binary tree stored as an array, satisfying one invariant: every parent is either ≥ (max-heap) or ≤ (min-heap) than both its children. That single rule is what makes the top always the extreme — and the whole structure self-maintaining with a handful of swap operations.

Heap Structure & Array Representation

A heap lives in a plain Python list. The array indices encode the tree shape — no pointers needed. For a node at index i:

Min-Heap — Live Animation

Watch how the heap array changes as you push and pop elements. The highlighted row shows which line of code is executing and what swap is occurring.

Python heapq — Min-Heap in Practice

Python's standard library implements a min-heap only. All operations work on a plain list — the heap is the list, no wrapper object needed.

import heapq

# ── Build a heap ───────────────────────────────────────────
data = [15, 3, 10, 8, 12, 5, 7]
heapq.heapify(data)          # O(n) — transforms list in-place
print("Heap array :", data)
print("Root (min) :", data[0])  # always index 0

# ── Push a new element ─────────────────────────────────────
heapq.heappush(data, 1)       # O(log n) — sift up
print("After push 1 :", data)

# ── Pop the minimum ────────────────────────────────────────
minimum = heapq.heappop(data)  # O(log n) — sift down
print("Popped min :", minimum)
print("Heap after pop:", data)

# ── Peek without removing ──────────────────────────────────
print("Current min :", data[0])  # O(1) — just read index 0

# ── Push + Pop atomically (more efficient) ─────────────────
result = heapq.heappushpop(data, 2)
print("heappushpop(2):", result)  # returns min of (pushed, current top)

Max-Heap in Python — The Negation Trick

Python's heapq is min-only. To simulate a max-heap, negate all values on insert and negate again on pop.

import heapq

# ── Max-heap via negation ──────────────────────────────────
max_heap = []

def max_push(h, val):
    heapq.heappush(h, -val)       # store negative

def max_pop(h):
    return -heapq.heappop(h)        # negate on way out

def max_peek(h):
    return -h[0]                    # O(1) peek

# Push cinema seat comfort scores
for score in [42, 91, 17, 68, 55]:
    max_push(max_heap, score)

print("Best seat (max):", max_peek(max_heap))

# Hand out best seats one by one
while max_heap:
    print("Seat assigned:", max_pop(max_heap))

Building a Heap From Scratch — Animated Step-by-Step

This section shows exactly which comparisons and swaps happen, line-by-line, when you implement sift-up and sift-down manually.

def sift_up(heap, i):
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] < heap[parent]:
            heap[i], heap[parent] = heap[parent], heap[i]
            i = parent
        else:
            break

Full Min-Heap Implementation

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

    def push(self, val):         # O(log n)
        self.heap.append(val)
        self._sift_up(len(self.heap) - 1)

    def pop(self):                 # O(log n)
        if not self.heap: raise IndexError("pop from empty heap")
        self._swap(0, len(self.heap) - 1)
        val = self.heap.pop()
        self._sift_down(0)
        return val

    def peek(self):                # O(1)
        return self.heap[0] if self.heap else None

    def _sift_up(self, i):
        while i > 0:
            p = (i - 1) // 2
            if self.heap[i] < self.heap[p]:
                self._swap(i, p); i = p
            else: break

    def _sift_down(self, i):
        n = len(self.heap)
        while True:
            smallest = i
            l, r = 2*i+1, 2*i+2
            if l < n and self.heap[l] < self.heap[smallest]: smallest = l
            if r < n and self.heap[r] < self.heap[smallest]: smallest = r
            if smallest != i:
                self._swap(i, smallest); i = smallest
            else: break

    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

# ── Demo ───────────────────────────────────────────────────
mh = MinHeap()
for v in [15, 3, 10, 8, 12, 5]:
    mh.push(v)

print("Peek:", mh.peek())
print("Pop sequence:", [mh.pop() for _ in range(6)])

Classic Patterns — K Largest & K Smallest Elements

import heapq

def k_largest(nums, k):
    # Min-heap of size k — root is k-th largest
    min_h = []
    for n in nums:
        heapq.heappush(min_h, n)
        if len(min_h) > k:
            heapq.heappop(min_h)   # evict the smallest so far
    return sorted(min_h, reverse=True)   # heap doesn't guarantee order

def k_smallest(nums, k):
    # heapq.nsmallest is optimised — uses heapify + nlargest internally
    return heapq.nsmallest(k, nums)

data = [7, 3, 19, 1, 15, 8, 4, 11]

print("3 largest :", k_largest(data, 3))
print("3 smallest:", k_smallest(data, 3))

# LeetCode 215: Kth Largest Element in an Array
def kth_largest(nums, k):
    return heapq.nlargest(k, nums)[-1]

print("2nd largest:", kth_largest(data, 2))

Advanced Pattern — Median of a Data Stream

One of the most elegant heap applications: maintain the running median of a stream using two heaps — a max-heap for the lower half and a min-heap for the upper half.

import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []   # max-heap (negated) — lower half
        self.hi = []   # min-heap — upper half

    def addNum(self, num):            # O(log n)
        heapq.heappush(self.lo, -num)
        # ensure max(lo) <= min(hi)
        if self.hi and -self.lo[0] > self.hi[0]:
            heapq.heappush(self.hi, -heapq.heappop(self.lo))
        # balance sizes: |lo| == |hi| or |lo| == |hi|+1
        if len(self.lo) > len(self.hi) + 1:
            heapq.heappush(self.hi, -heapq.heappop(self.lo))
        elif len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self):             # O(1)
        if len(self.lo) == len(self.hi):
            return (-self.lo[0] + self.hi[0]) / 2
        return -self.lo[0]

mf = MedianFinder()
for n in [5, 15, 1, 3]:
    mf.addNum(n)
    print(f"Added {n:2d}  →  median = {mf.findMedian()}")

Time & Space Complexity Reference

Real-World Use Cases

Before / After — Replacing a Sorted List

Golden Rules