Heaps Explained

A heap is a specialized tree-based data structure that always keeps its smallest (or largest) element instantly accessible at the root. It’s the standard way to implement a priority queue — a queue where items come out in order of importance rather than in the order they were added. Heaps power algorithms like Dijkstra’s shortest path, task schedulers, and “find the k largest/smallest” problems, all because they offer a rare combination: fast insertion, fast removal of the extreme value, and low memory overhead.

Overview: What a Heap Is and How It Works

Imagine you’re running a hospital triage desk. Patients arrive in random order, but you always need to treat the most urgent case next. A sorted list would let you always grab the most urgent patient, but keeping it sorted as new patients arrive is expensive. A heap solves this: it doesn’t keep everything sorted, it only guarantees that the most urgent item is always at the top, and it can restore that guarantee after an insertion or removal very cheaply.

Formally, a binary heap is a complete binary tree (every level is fully filled except possibly the last, which fills left to right with no gaps) that satisfies the heap property:

• Min-heap: every parent node is less than or equal to its children, so the smallest element is always at the root.
• Max-heap: every parent node is greater than or equal to its children, so the largest element is always at the root.

Note that a heap is not a fully sorted structure — it only enforces the parent/child ordering, not any ordering between siblings or across subtrees. That partial ordering is exactly what makes heaps cheap to maintain.

Why Heaps Are Stored as Arrays

Because a binary heap is always a complete tree, it can be stored in a plain array with no pointers at all. For a node at index i (0-indexed):

• Parent index: (i - 1) // 2
• Left child index: 2 * i + 1
• Right child index: 2 * i + 2

This array representation is why heaps are memory-efficient compared to a general tree with explicit left/right/parent pointers — there’s no pointer overhead, and everything lives contiguously in one list.

Sift-Up and Sift-Down

Two operations keep the heap property intact:

• Sift-up (bubble up): used after inserting a new element at the end of the array. The new element is repeatedly swapped with its parent while it’s smaller (min-heap) than that parent, until the heap property holds.
• Sift-down (bubble down): used after removing the root. The last element is moved to the root position, then repeatedly swapped with its smaller child until the heap property holds.

Both operations only ever travel along a single path from a node toward the root or a leaf — and since the tree is complete, that path has length O(log n), which is the source of a heap’s efficiency.

Python’s heapq Module

Python’s standard library provides heapq, which turns an ordinary list into a min-heap in place. There is no built-in max-heap: the standard trick is to negate numbers before pushing them and negate again when popping. heapq is not a heap class; it’s a set of functions (heappush, heappop, heapify, heapreplace, nlargest, nsmallest) that operate on a plain Python list, which is why the underlying data structure is always “just a list” with the heap property enforced by convention.

Time and Space Complexity

A heap’s power comes from every core operation being bounded by the height of a complete binary tree, which is O(log n) for n elements — except peeking at the top and building a heap from scratch, which have their own special-case complexities.

Operation	Time Complexity	Why
Peek min/max (heap[0])	O(1)	The extreme value is always stored at index 0 — no search needed.
heappush (insert)	O(log n)	Append to the end, then sift-up at most the height of the tree, log n levels.
heappop (remove root)	O(log n)	Move the last element to the root, then sift-down at most log n levels.
heapify (build from n items)	O(n)	Counter-intuitively linear, not O(n log n) — most nodes are near the bottom of the tree and need almost no sifting; the math works out to a linear sum.
n individual pushes	O(n log n)	Each of the n pushes costs up to O(log n), so building a heap by pushing one item at a time is slower than heapify.
nlargest(k, iterable)	O(n log k)	Maintains a heap of size k while scanning all n items once.

Space complexity is O(n) to store n elements, since a heap is just an array with no extra pointer overhead; push and pop are done in place and use only O(1) auxiliary space beyond the array itself. There’s no meaningful best/average/worst-case split for push and pop the way there is for, say, a binary search tree — because a heap’s shape is always a complete tree, its height is always log n regardless of insertion order, so there’s no “unlucky” degenerate shape.

Examples

Example 1: A Min-Heap With heapq

The simplest use of heapq is pushing values in and popping them back out one at a time — since heappop always removes the current smallest element, popping repeatedly naturally produces a sorted sequence.

import heapq


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

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


result = demo_min_heap([5, 1, 8, 3, 9, 2])
print(result)

Output:

[1, 2, 3, 5, 8, 9]

Each heappush call inserts a value and lets it bubble up to restore the heap property. Because heappop always removes whatever is currently smallest, draining the heap one pop at a time yields the numbers in ascending order — this pattern (“push everything, then pop everything”) is essentially heap sort.

Example 2: Simulating a Max-Heap to Find the k Largest Values

Since heapq only gives you a min-heap, the standard workaround for max-heap behavior is to negate every value on the way in and negate again on the way out.

import heapq


def k_largest(nums: list[int], k: int) -> list[int]:
    heap = [-num for num in nums]
    heapq.heapify(heap)

    largest: list[int] = []
    for _ in range(k):
        largest.append(-heapq.heappop(heap))
    return largest


numbers = [7, 2, 9, 4, 1, 8, 3]
print(k_largest(numbers, 3))

Output:

[9, 8, 7]

Negating turns “find the largest” into “find the smallest of the negated values,” which heapq handles natively. heapify rearranges the whole list into valid min-heap order in O(n) time, and each of the three pops costs O(log n), giving O(n + k log n) overall — much better than sorting the entire list when k is small.

Example 3: A Priority Queue for Task Scheduling

A real task queue needs a tiebreaker: if two tasks share the same priority, comparing task names (or objects) directly can be undesirable or even error-prone. The standard fix is to push a tuple of (priority, insertion_order, item) so ties are broken by insertion order, and the heap never needs to compare the items themselves.

import heapq


def process_tasks(tasks: list[tuple[int, str]]) -> list[str]:
    heap: list[tuple[int, int, str]] = []
    for index, (priority, name) in enumerate(tasks):
        heapq.heappush(heap, (priority, index, name))

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


tasks = [(3, "cleanup"), (1, "send_email"), (2, "generate_report"), (1, "backup_db")]
print(process_tasks(tasks))

Output:

['send_email', 'backup_db', 'generate_report', 'cleanup']

Lower numbers mean higher priority here. Both send_email and backup_db have priority 1, so the heap compares their second tuple element (insertion order) to break the tie, and send_email (inserted first) comes out first. Without that tiebreaker field, Python would fall back to comparing the task name strings, or raise a TypeError if the third element weren’t comparable at all (for example, if it were an arbitrary object).

How Heap Operations Work Step by Step

Let’s trace heappush building a min-heap one value at a time from the same input as Example 1: [5, 1, 8, 3, 9, 2]. Each push appends to the end of the array, then sifts the new value up while it’s smaller than its parent.

Push	Array After Append	Sift-Up Action	Array After Sift-Up
5	[5]	No parent, nothing to do	[5]
1	[5, 1]	1 < parent 5 → swap	[1, 5]
8	[1, 5, 8]	8 ≥ parent 1 → no swap	[1, 5, 8]
3	[1, 5, 8, 3]	3 < parent 5 → swap; then 3 ≥ parent 1 → stop	[1, 3, 8, 5]
9	[1, 3, 8, 5, 9]	9 ≥ parent 3 → no swap	[1, 3, 8, 5, 9]
2	[1, 3, 8, 5, 9, 2]	2 < parent 8 → swap; then 2 ≥ parent 1 → stop	[1, 3, 2, 5, 9, 8]

The final array [1, 3, 2, 5, 9, 8] is a valid min-heap: index 0 (value 1) is the parent of indices 1 and 2 (values 3 and 2, both ≥ 1); index 1 (value 3) is the parent of indices 3 and 4 (values 5 and 9, both ≥ 3); index 2 (value 2) is the parent of index 5 (value 8, ≥ 2). Notice the array is not sorted — 3 sits before 2 — because the heap property only constrains parent/child pairs, not siblings. That’s exactly why draining the heap with repeated heappop calls (Example 1) is required to get a fully sorted sequence, rather than just reading the array in order.

Common Mistakes

Mistake 1: Assuming heapq Gives You the Largest Element

Because “heap” sounds generic, it’s easy to forget that heapq is always a min-heap. Calling heappop expecting the maximum value silently returns the minimum instead — no error, just a wrong answer.

import heapq


def get_largest(numbers: list[int]) -> int:
    heap = numbers.copy()
    heapq.heapify(heap)
    return heapq.heappop(heap)


numbers = [5, 1, 8, 3, 9, 2]
print(get_largest(numbers))

Output:

1

That prints 1, the smallest value, even though the function is named get_largest. The fix is the negation trick from Example 2:

import heapq


def get_largest(numbers: list[int]) -> int:
    heap = [-number for number in numbers]
    heapq.heapify(heap)
    return -heapq.heappop(heap)


numbers = [5, 1, 8, 3, 9, 2]
print(get_largest(numbers))

Output:

9

Mistake 2: Assuming the Heap’s Internal List Is Sorted

A heap only guarantees the root is the minimum — it does not guarantee the rest of the list is in any particular sorted order. Printing the raw list after heapify and expecting ascending order is a common source of confusion.

import heapq

numbers = [5, 1, 8, 3, 9, 2]
heapq.heapify(numbers)
print(numbers)

Output:

[1, 3, 2, 5, 9, 8]

That is a valid heap (index 0 is the minimum), but it is clearly not the sorted list [1, 2, 3, 5, 8, 9]. To actually get a sorted result, you must pop every element out one at a time, letting each pop re-establish the heap property via sift-down:

import heapq

numbers = [5, 1, 8, 3, 9, 2]
heapq.heapify(numbers)
sorted_numbers = [heapq.heappop(numbers) for _ in range(len(numbers))]
print(sorted_numbers)

Output:

[1, 2, 3, 5, 8, 9]

Best Practices

• Use heapq.heapify to build a heap from an existing list in O(n) time rather than pushing items one at a time in a loop, which costs O(n log n).
• For a max-heap, negate values on push and pop rather than writing a custom comparator — it’s the idiomatic Python approach and keeps the code short.
• When priorities can tie, push tuples like (priority, insertion_order, item) so ties break deterministically and Python never has to compare the underlying items directly.
• Reach for a heap when you repeatedly need the current min/max as data streams in or changes, but don’t need the full data sorted at every step — that’s exactly the priority-queue use case (task schedulers, Dijkstra’s algorithm, merging k sorted lists, running medians with two heaps).
• If you only need the top k elements once from a static collection, prefer heapq.nlargest/heapq.nsmallest over sorting the whole collection — they run in O(n log k) instead of O(n log n).
• Don’t reach for a heap if you need to search for an arbitrary element or need the data fully sorted at all times — a heap only optimizes access to the extreme value, not general lookup.

Practice Exercises

1. Write a function kth_smallest(nums: list[int], k: int) -> int that returns the k-th smallest value using a heap, without sorting the entire list. Hint: a max-heap of size k lets you discard anything larger than the current k-th smallest as you scan.
2. Given a list of (arrival_time, patient_name, severity) tuples, build a priority queue that always serves the most severe patient next, breaking ties by earliest arrival time. Expected behavior: two patients with the same severity should come out in arrival order, not alphabetical order.
3. Implement merge_sorted_lists(lists: list[list[int]]) -> list[int] that merges several already-sorted lists into one sorted list using a heap that always holds one “current smallest candidate” per input list. Hint: push tuples of (value, list_index, element_index) so you can find which list to pull the next value from.

Summary

• A heap is a complete binary tree stored as an array, satisfying either the min-heap property (parent ≤ children) or max-heap property (parent ≥ children).
• Array indices replace pointers: parent is (i - 1) // 2, children are 2i + 1 and 2i + 2.
• Peek is O(1); push and pop are O(log n) via sift-up/sift-down; building a heap from n items with heapify is O(n), not O(n log n). Space is O(n).
• Python’s heapq is always a min-heap; simulate a max-heap by negating values on push and pop.
• A heap is not fully sorted — only the root is guaranteed to be the extreme value. Get a sorted list by popping every element, one at a time.
• Use tuples like (priority, insertion_order, item) to break ties deterministically in a priority queue and avoid comparing incomparable items.