Min-Heap vs Max-Heap

A heap is a specialized tree-based data structure that keeps one element — either the smallest or the largest — instantly accessible at the root, while still supporting fast insertion and removal. A min-heap always surfaces the smallest item first; a max-heap always surfaces the largest. Heaps are the engine behind priority queues, and they show up constantly in scheduling systems, graph algorithms like Dijkstra’s, and interview questions about "the k largest/smallest elements" or "the next most urgent task." This lesson covers both flavors, how Python’s heapq module (which only gives you a min-heap) can be turned into a max-heap, and the mistakes people make along the way.

Overview: How Min-Heaps and Max-Heaps Work

A binary heap is a complete binary tree — every level is fully filled except possibly the last, which fills left to right — stored compactly in a plain array with no pointers at all. For any index i, its parent lives at (i - 1) // 2, and its children live at 2 * i + 1 and 2 * i + 2. Because the tree shape is always predictable (complete, never lopsided), these arithmetic formulas are enough to navigate the tree; you never need a `left`/`right`/`parent` pointer object like you would for a general binary tree.

A heap is not a fully sorted structure. It only guarantees the heap property: every parent is smaller than (or equal to) its children in a min-heap, or larger than (or equal to) its children in a max-heap. That’s a much weaker guarantee than a sorted array, and that weakness is exactly what makes heaps fast — you only pay to keep the root correct and to keep each parent/child pair correct, not to keep the whole array in order.

Picture a hospital emergency room where patients are logged with a severity number, and 1 means "most critical." You want to always treat the most critical patient next, but new patients keep arriving in random order. A min-heap is a perfect fit: insert each new patient in O(log n) time, and always peek/pop the most critical one in O(1)/O(log n) time, without ever needing to fully sort the waiting room. Now flip the scenario to a leaderboard where you want the highest score on top — that’s the same structure, just with the comparison reversed: a max-heap.

Python’s standard library, heapq, implements only a min-heap. There is no built-in max-heap. The standard trick is to negate every value before pushing it and negate again after popping — since flipping the sign of every number reverses their order, the "smallest negated value" is exactly the "largest original value." You’ll see this pattern throughout the examples below.

Time and Space Complexity

Every heap operation’s cost comes from the tree’s height. Because a binary heap is complete, a heap holding n elements has height O(log n) — each level roughly doubles the number of nodes, so the number of levels needed to hold n nodes is about log2(n). Any operation that walks from the root to a leaf (or vice versa) therefore costs O(log n).

Operation Min-Heap Max-Heap Why
Peek smallest/largest O(1) O(1) It’s always the root — index 0 of the underlying array, no traversal needed.
Insert (heappush) O(log n) O(log n) The new item is appended at the end, then "sifts up" by swapping with its parent at most once per level.
Remove root (heappop) O(log n) O(log n) The last element replaces the root, then "sifts down" toward a leaf, at most once per level.
Build from n items (heapify) O(n) O(n) Most nodes sit near the bottom of the tree and only sift a short distance. Summed across all levels, the total work converges to O(n), not O(n log n) — it’s cheaper to heapify a whole list at once than to heappush items one at a time.
Space O(n) O(n) One array slot per element; no extra pointer overhead.
Aspect Min-Heap Max-Heap
Root holds Smallest element Largest element
Heap property parent <= children parent >= children
Native Python support heapq directly Simulated by negating values pushed into heapq
Typical uses Dijkstra’s algorithm, k smallest elements, merging k sorted lists, "lower number = higher priority" schedulers Top-k leaderboards, k largest elements, "process the biggest job first" schedulers

Examples

Example 1: A min-heap with heapq

heapq.heappush maintains the min-heap property one element at a time, and repeatedly popping from a fully-loaded heap always yields elements in ascending order — that’s the basis of heap sort.

import heapq

def demo_min_heap(numbers: list[int]) -> list[int]:
    heap: list[int] = []
    for number in numbers:
        heapq.heappush(heap, number)

    print(f"Heap array after all pushes: {heap}")

    sorted_output: list[int] = []
    while heap:
        sorted_output.append(heapq.heappop(heap))
    return sorted_output


numbers = [7, 2, 9, 1, 5, 3]
result = demo_min_heap(numbers)
print(f"Popped in order: {result}")

Output:

Heap array after all pushes: [1, 2, 3, 7, 5, 9]
Popped in order: [1, 2, 3, 5, 7, 9]

Notice the internal array [1, 2, 3, 7, 5, 9] is not sorted — only the heap property holds (each parent <= its children). It’s the repeated popping that yields sorted output, one O(log n) step at a time.

Example 2: A max-heap via negation

heapq has no max-heap mode, so we negate every value on the way in and negate again on the way out. Negation reverses order, so the "minimum" of the negated values is exactly the maximum of the originals.

import heapq

def demo_max_heap(numbers: list[int]) -> list[int]:
    max_heap: list[int] = []
    for number in numbers:
        heapq.heappush(max_heap, -number)

    popped_in_order: list[int] = []
    while max_heap:
        popped_in_order.append(-heapq.heappop(max_heap))
    return popped_in_order


numbers = [7, 2, 9, 1, 5, 3]
result = demo_max_heap(numbers)
print(f"Popped in order (max first): {result}")

Output:

Popped in order (max first): [9, 7, 5, 3, 2, 1]

Same input list as Example 1, but because every value was negated before pushing, the heap now pops in descending order of the original numbers.

Example 3: A realistic priority queue with tie-breaking

Real task schedulers push (priority, task_name) pairs. But if two tasks share the same priority, Python falls back to comparing the second tuple element — and if that’s not orderable, you get a crash (see Common Mistakes). The fix is to add an always-increasing counter as a tie-breaker, which also guarantees stable, first-in-first-out ordering among equal priorities.

import heapq
import itertools

def run_task_scheduler(tasks: list[tuple[int, str]]) -> list[str]:
    heap: list[tuple[int, int, str]] = []
    counter = itertools.count()

    for priority, name in tasks:
        heapq.heappush(heap, (priority, next(counter), name))

    execution_order: list[str] = []
    while heap:
        priority, _, name = heapq.heappop(heap)
        execution_order.append(name)
    return execution_order


tasks = [(3, "send_email"), (1, "handle_outage"), (2, "deploy_fix"), (1, "restart_service")]
order = run_task_scheduler(tasks)
print(f"Execution order: {order}")

Output:

Execution order: ['handle_outage', 'restart_service', 'deploy_fix', 'send_email']

Priority 1 is treated as most urgent (lower number = more urgent, a common scheduler convention). Between the two priority-1 tasks, handle_outage was pushed first (counter value 1) so it comes out before restart_service (counter value 3), even though both share priority 1.

How a Heap Is Built, Step by Step

heapq.heapify() converts an existing list into a valid heap in place, in O(n) time, by processing internal (non-leaf) nodes from the bottom of the tree up to the root, "sifting down" each one until it’s smaller than both its children.

Trace it on [9, 4, 7, 1, 3, 2, 6] (7 elements, indices 0–6). The last parent node is at index n // 2 - 1 = 2, so we process indices 2, then 1, then 0:

  • index 2 (value 7): children are index 5 (value 2) and index 6 (value 6). The smaller child is 2. Since 7 > 2, swap them. Array becomes [9, 4, 2, 1, 3, 7, 6]. Index 5 has no children, so this subtree is done.
  • index 1 (value 4): children are index 3 (value 1) and index 4 (value 3). The smaller child is 1. Since 4 > 1, swap them. Array becomes [9, 1, 2, 4, 3, 7, 6]. Index 3 has no children in range, so this subtree is done.
  • index 0 (value 9): children are index 1 (value 1) and index 2 (value 2). The smaller child is 1. Since 9 > 1, swap them. Array becomes [1, 9, 2, 4, 3, 7, 6]. Now continue sifting the displaced 9 down: at index 1, its children are index 3 (value 4) and index 4 (value 3). The smaller child is 3. Since 9 > 3, swap them. Array becomes [1, 3, 2, 4, 9, 7, 6]. Index 4 has no children in range, so we’re done.

The final heapified array is [1, 3, 2, 4, 9, 7, 6]. Check the heap property: index 0 (1) <= index 1 (3) and index 2 (2); index 1 (3) <= index 3 (4) and index 4 (9); index 2 (2) <= index 5 (7) and index 6 (6). All good — it’s a valid min-heap, even though the array as a whole is clearly not sorted.

import heapq

def build_min_heap(values: list[int]) -> list[int]:
    heap = values.copy()
    heapq.heapify(heap)
    return heap


original = [9, 4, 7, 1, 3, 2, 6]
heap = build_min_heap(original)
print(f"Original array: {original}")
print(f"Heapified array: {heap}")

Output:

Original array: [9, 4, 7, 1, 3, 2, 6]
Heapified array: [1, 3, 2, 4, 9, 7, 6]

Common Mistakes

Mistake 1: Forgetting that heapq is always a min-heap

It’s easy to assume heapq.heappop() returns the largest value, especially if you’re thinking of it as a generic "priority queue" without checking which direction the priority runs.

import heapq

scores = [5, 1, 3, 9, 2]
heapq.heapify(scores)
top_score = heapq.heappop(scores)
print(f"Top score: {top_score}")

Output:

Top score: 1

The intent was clearly to get the highest score (9), but heapq always pops the smallest element, so this prints 1. The fix is the negation trick from Example 2:

import heapq

scores = [5, 1, 3, 9, 2]
max_heap = [-score for score in scores]
heapq.heapify(max_heap)
top_score = -heapq.heappop(max_heap)
print(f"Top score: {top_score}")

Output:

Top score: 9

Mistake 2: Tying priorities on non-orderable payloads

When two heap entries have equal priority, Python compares the next element of the tuple to break the tie. If that next element isn’t orderable (like a dict), you get a crash at runtime, not at compile time — so it’s easy to miss until two equal priorities actually collide in production.

import heapq

heap = []
heapq.heappush(heap, (2, {"task": "backup_database"}))
heapq.heappush(heap, (2, {"task": "rotate_logs"}))
print(heapq.heappop(heap))

Output:

TypeError: '<' not supported between instances of 'dict' and 'dict'

Both entries have priority 2, so Python tries to compare the dicts to break the tie — and dicts don’t support <. The fix is to insert an always-increasing counter between the priority and the payload, so ties break on the counter and the payload is never compared:

import heapq
import itertools

heap: list[tuple[int, int, dict]] = []
counter = itertools.count()

heapq.heappush(heap, (2, next(counter), {"task": "backup_database"}))
heapq.heappush(heap, (2, next(counter), {"task": "rotate_logs"}))

priority, _, payload = heapq.heappop(heap)
print(f"Next up: {payload['task']} (priority {priority})")

Output:

Next up: backup_database (priority 2)

Because backup_database was pushed with counter value 0 and rotate_logs with counter value 1, the tie is broken in favor of whichever was inserted first — matching FIFO behavior most people expect from a scheduler, and never touching the unorderable dicts.

Best Practices

  • Use heapq directly for a min-heap; negate the priority (not the whole object) to simulate a max-heap.
  • When payloads aren’t naturally orderable, push (priority, tie_breaker, payload) tuples with an itertools.count() tie-breaker — this avoids TypeError and gives predictable, stable ordering among equal priorities.
  • Prefer heapq.heapify(existing_list) for bulk construction (O(n)) over calling heappush in a loop (O(n log n)) when you already have all the data up front.
  • Use heapq.nlargest(k, iterable) / heapq.nsmallest(k, iterable) when you only need the top-k elements from a collection — it’s more efficient than sorting the whole thing when k is much smaller than n.
  • Use heapq.heapreplace(heap, item) (pop-then-push) or heapq.heappushpop(heap, item) (push-then-pop) when you need both operations back to back — each does the work in one O(log n) pass instead of two.
  • Reach for a heap when you need repeated access to "the current smallest/largest" while the collection keeps changing (priority queues, Dijkstra’s algorithm, k-way merges, running medians via two heaps). If you just need one min/max of a static collection, plain min()/max() is simpler and just as fast.
  • Remember a heap only guarantees the root is correct — don’t assume the rest of the internal array is sorted, and don’t iterate over it expecting sorted order.

Practice Exercises

  • Streaming k smallest: Given a list of stock prices arriving one at a time, maintain a max-heap of size k (negation trick) so it always holds the k smallest prices seen so far. Hint: if the heap grows past size k, pop the current largest of the kept values.
  • Top-3 leaderboard: Write a class backed by a max-heap that supports add_score(name, score) and top_three(), always returning the three highest scores seen. Expected behavior: after adding scores 10, 55, 30, 90, 20, top_three() should return the names attached to 90, 55, and 30, in that order.
  • Merge k sorted lists: Given k already-sorted lists of integers, merge them into one sorted list using a single min-heap. Hint: push (value, list_index, element_index) tuples so ties never need to compare list contents directly, and after popping an element, push the next element from that same list if one remains.

Summary

  • A heap is a complete binary tree stored as a flat array; a min-heap keeps the smallest value at the root, a max-heap keeps the largest.
  • heapq only implements a min-heap in Python — simulate a max-heap by negating values on push and pop.
  • heappush and heappop are O(log n) because they walk at most the height of the tree; peeking the root is O(1); bulk-building with heapify is O(n), not O(n log n).
  • Draining a heap by repeatedly popping yields fully sorted output — that’s heap sort in miniature — but the raw internal array is only partially ordered, never fully sorted.
  • When priorities can tie and payloads aren’t orderable, add an itertools.count() tie-breaker to the tuple to avoid TypeError and get stable ordering.
  • Use heapq.heapify, nlargest/nsmallest, and heapreplace/heappushpop instead of hand-rolling equivalents — they’re already optimized and well-tested.