The Project | About Us | Contribute | Donations | License

HOME

Time to settle the course's oldest debt. In module 4, TaskFlow's UrgentInbox always dispatched the highest-priority task using heapq as a black box: we put in (priority, counter, task) tuples and they came out in order, "by magic and in O(log n)", with the promise of opening the box in this module. You now have all the pieces: you know what a complete binary tree is (06-02), you know the array representation with 2i+1/2i+2 indices (06-02), and you understand why O(height) operations are fast when the height is logarithmic. The heap combines the three ideas with a brilliant relaxation: it doesn't maintain the BST's total order — it only guarantees that every parent is less than or equal to its children — and with that minimal contract it manages to insert and extract the minimum in O(log n) on a plain array, with no nodes or references. In this lesson you'll implement the complete heap, rebuild the UrgentInbox on top of it, and close out the priority queue comparison table.

The heap property: partial order, not total
The shape: complete tree = array with no gaps
Inserting: sift-up
Extracting the minimum: sift-down
The complete Heap class
UrgentInbox 2.0: the black box, opened
Bonus: heapify in O(n), heapsort, and the max-heap

The heap property: partial order, not total

A min-heap is a binary tree satisfying two conditions:

Shape property: it's a complete binary tree (all levels full except the last, filled left to right — 06-02).
Heap property: every parent is less than or equal to each of its children.

And nothing else. Compare it with the BST, because the contrast is the key to the lesson:

graph TD
    subgraph "Valid min-heap"
        A((1)) --> B((3))
        A --> C((2))
        B --> D((7))
        B --> E((4))
        C --> F((5))
        C --> G((9))
    end

	BST (06-04)	Min-heap
Rule	left < node < right	parent ≤ children (no side distinction)
Kind of order	total: inorder lists everything sorted	partial: only the root-leaf path is guaranteed
Where is the minimum?	leftmost leaf (O(height))	the root, always (O(1))
Finding an arbitrary value?	O(height)	O(n) — no clues about where it is
Ranges, successor, sorted listing?	yes	no
Shape	whatever comes out (hence the AVL)	complete by definition: height ⌊log₂ n⌋ for free

Look at the diagram: 3 is to the left of 2 and nobody cares — there's no order at all among siblings. A heap is a BST that has given up almost everything: it can't list in order, or answer ranges, or find an element. In exchange for that surrender, it gains two things the BST doesn't have: the minimum at the root always, and perfect balance by definition (the complete shape is non-negotiable, so there's no possible degeneration and no need for an AVL to watch over it). It's the perfect specialization for a single question: "which one is most urgent?" — exactly a priority queue's question. Mental rule for choosing: do you need all the elements in order at any moment? BST/AVL. Just the next smallest, over and over? Heap.

The shape: complete tree = array with no gaps

Here the seed planted in 06-02 sprouts: since the heap is always a complete tree, it lives perfectly in an array without wasting a slot — no BinaryNode, no references, no extra memory. The diagram above is, in memory, this:

heap = [1, 3, 2, 7, 4, 5, 9]
# indices:  0  1  2  3  4  5  6

With 06-02's arithmetic as the only navigation: children of i at 2i+1 and 2i+2, parent at (i-1)//2. Verify the property on the array: heap[1] = 3 ≥ heap[0] = 1 (parent at (1-1)//2 = 0), heap[5] = 5 ≥ heap[2] = 2... The heap property, translated to arrays: arr[i] >= arr[(i-1)//2] for all i > 0.

When in module 4 we wrote heapq.heappush(inbox, ...) on a Python list and asked for your faith: this is what was there. heapq is not a structure: it's a set of functions that maintain this property on an ordinary list. Print a heapq heap and you'll see the array above — unordered to the naked eye, ordered per the heap's contract.

Inserting: sift-up

To insert, both properties must be preserved. The strategy: guarantee the shape first and repair the order afterward.

Place the new element in the only position that keeps the tree complete: the end of the array (the first gap of the last level).
It may now be smaller than its parent, violating the property. Fix it by sifting up: while it's smaller than its parent, swap them and move up.

Let's insert 0 into the example heap, with a full trace:

[1, 3, 2, 7, 4, 5, 9, 0]      0 enters at i=7; its parent: (7-1)//2 = 3, holds 7
        0 < 7: swap  →  [1, 3, 2, 0, 4, 5, 9, 7]   now i=3, parent i=1 (holds 3)
        0 < 3: swap  →  [1, 0, 2, 3, 4, 5, 9, 7]   now i=1, parent i=0 (holds 1)
        0 < 1: swap  →  [0, 1, 2, 3, 4, 5, 9, 7]   i=0: it's the root, done

graph TD
    subgraph "1. 0 enters at the end"
        A((1)) --> B((3))
        A --> C((2))
        B --> D((7))
        B --> E((4))
        C --> F((5))
        C --> G((9))
        D --> H((0))
    end
    subgraph "2. After sifting up to the root"
        A2((0)) --> B2((1))
        A2 --> C2((2))
        B2 --> D2((3))
        B2 --> E2((4))
        C2 --> F2((5))
        C2 --> G2((9))
        D2 --> H2((7))
    end

Notice what the 0 did not touch: 2's subtree never even noticed. Sifting up only walks the new node's path toward the root — at most the tree's height, which in a complete tree is exactly ⌊log₂ n⌋. Insertion: O(log n), guaranteed without rotations or watchdogs.

Extracting the minimum: sift-down

The minimum is the root (arr[0]), but ripping it out would leave a hole at the top — and arrays hate holes at index 0 (remember the O(n) dequeue of the list-based queue, in module 4?). The mirror trick of the previous one — shape first, order after:

Save the root (it's the result). Move the last element of the array to the root — the shape is correct again, shrunk in the right place.
That element is probably too big for the top: sift it down — while it's greater than either of its children, swap it with the smaller of the two and descend.

Let's extract from the resulting heap [0, 1, 2, 3, 4, 5, 9, 7]:

0 leaves; the last one (7) rises to the root  →  [7, 1, 2, 3, 4, 5, 9]
   children of 7 (i=0): 1 (i=1) and 2 (i=2); the smaller is 1
   7 > 1: swap                                →  [1, 7, 2, 3, 4, 5, 9]
   children of 7 (i=1): 3 (i=3) and 4 (i=4); the smaller is 3
   7 > 3: swap                                →  [1, 3, 2, 7, 4, 5, 9]
   children of 7 (i=3): none (2·3+1 = 7 ≥ len): it's a leaf, done

Why with the smaller of the two children? Because the chosen one will become the other's parent: if we raised the larger one, we'd violate the property on the spot. It's the classic implementation mistake — with two children 3 and 4, raising the 4 leaves 4 > 3 as 3's parent.

Cost: again at most the path from the root to a leaf — O(log n). And the sequence of successive extractions returns the elements in ascending order: 0, 1, 2, 3... each extraction reorganizes just enough for the new minimum to surface at the top.

The complete `Heap` class

All together, in a class with a priority queue's interface:

class Heap:
    """Min-heap on a Python list. Elements must be comparable."""

    def __init__(self):
        self._data = []

    def __len__(self):
        return len(self._data)

    def peek_min(self):
        """The minimum without extracting it. O(1): it's the root."""
        return self._data[0] if self._data else None

    def insert(self, element):
        """Append at the end and sift up. O(log n)."""
        self._data.append(element)
        self._sift_up(len(self._data) - 1)

    def extract_min(self):
        """Take the root, move the last one up, and sift it down. O(log n)."""
        if not self._data:
            return None
        minimum = self._data[0]
        last = self._data.pop()            # O(1): removing from the end
        if self._data:                     # if anyone remains, they take the top and sink
            self._data[0] = last
            self._sift_down(0)
        return minimum

    def _sift_up(self, i):
        while i > 0:
            parent = (i - 1) // 2
            if self._data[i] < self._data[parent]:
                self._data[i], self._data[parent] = self._data[parent], self._data[i]
                i = parent                 # keep rising from the new position
            else:
                break                      # the parent is already smaller or equal: in place

    def _sift_down(self, i):
        n = len(self._data)
        while True:
            left, right = 2 * i + 1, 2 * i + 2
            smallest = i
            if left < n and self._data[left] < self._data[smallest]:
                smallest = left
            if right < n and self._data[right] < self._data[smallest]:
                smallest = right           # the smallest of the three: parent, left, right
            if smallest == i:
                break                      # already smaller than both children: in place
            self._data[i], self._data[smallest] = self._data[smallest], self._data[i]
            i = smallest                   # keep descending from the new position

Details that deserve a second read:

_sift_down computes smallest among three candidates (the node itself and its existing children): that way the swap is always with the smaller child, and the left < n checks cover nodes with one child or none.
In extract_min, the "only one element remained" case comes free: pop() removes it, self._data is left empty, and nothing sinks.
Let's prove module 4's magic is no longer magic:

h = Heap()
for x in [5, 3, 8, 1, 9, 2]:
    h.insert(x)
print(h._data)          # [1, 3, 2, 5, 9, 8] — the array-heap, in plain sight
while len(h):
    print(h.extract_min(), end=" ")   # 1 2 3 5 8 9 — ascending

This is, behavior line by line, what heapq.heappush and heapq.heappop were doing in module 4 (with the list exposed instead of encapsulated — Python's design decision, ADT vs implementation from module 1). Black box: opened.

`UrgentInbox` 2.0: the black box, opened

Let's rebuild module 4's UrgentInbox on top of our heap, with the same interface and the same (priority, counter, task) tuple trick — which you now fully understand: tuples compare element by element, so the heap orders by priority; the counter from itertools.count breaks ties FIFO among equals and prevents the comparison from ever reaching the dict (dictionaries don't compare with <; without the counter, two tasks of equal priority would blow up with TypeError).

from itertools import count

class UrgentInbox:
    """TaskFlow's priority queue. Priority 1 = highest.
    Same interface as in module 4; engine of our own."""

    def __init__(self):
        self._heap = Heap()
        self._counter = count()            # FIFO tiebreak and anti-TypeError shield

    def arrive(self, task):
        self._heap.insert((task["priority"], next(self._counter), task))

    def next_task(self):
        """The most urgent task (oldest among equals), or None."""
        entry = self._heap.extract_min()
        return entry[2] if entry else None

    def peek_urgent(self):
        entry = self._heap.peek_min()
        return entry[2] if entry else None

inbox = UrgentInbox()
inbox.arrive({"id": "T-11", "title": "Weekly report", "priority": 3, "status": "pending"})
inbox.arrive({"id": "T-12", "title": "Server down", "priority": 1, "status": "pending"})
inbox.arrive({"id": "T-13", "title": "Review PR", "priority": 2, "status": "pending"})
inbox.arrive({"id": "T-14", "title": "Slow database", "priority": 1, "status": "pending"})

print(inbox.next_task()["id"])   # T-12  (priority 1, arrived before T-14)
print(inbox.next_task()["id"])   # T-14  (priority 1)
print(inbox.next_task()["id"])   # T-13  (priority 2)

And the table module 4 left half-finished, now complete — the three priority queue implementations, face to face:

Implementation (module)	`arrive` (insert)	`next_task` (extract min)	`peek_urgent`
`UnorderedPriorityQueue` (4)	O(1)	O(n) — search for the minimum	O(n)
`OrderedPriorityQueue` (4)	O(n) — `insert_sorted`	O(1)	O(1)
Heap (6)	O(log n)	O(log n)	O(1)

The first two paid O(n) on one of the two operations — they maintained too little order (none) or too much (total). The heap is the exact balance: just enough order to answer "what's next?" fast, not a drop more. With 10,000 tasks and constant traffic of arrivals and dispatches, it's the difference between thousands of operations per event and ~13. This idea — paying only for the order you actually consume — is one of the most profitable things you'll take from the course.

Bonus: heapify in O(n), heapsort, and the max-heap

Heapify. Turning a list of n elements into a heap? Inserting them one by one costs O(n log n). But there's a better way, and in 06-02 (exercise 2) you saw the key piece: in an array-heap, every index from n//2 to the end is a leaf — and a leaf is already a valid mini-heap. So it's enough to walk the internal nodes back to front (n//2 - 1 → 0), sifting each one down: when a node's turn comes, its two subtrees are already heaps, and sifting it down fuses the three into one. The arithmetic surprises: half the nodes (leaves) do 0 work, a quarter sink 1 level, an eighth 2... the sum converges to O(n), not O(n log n) — almost all nodes are near the bottom and have little sinking to do. This is what heapq.heapify does, and it's why it's the right way to bootstrap a heap from existing data.

Heapsort. Heapify O(n) + extract the minimum n times O(log n) = a sorted list in guaranteed O(n log n) with no extra memory (the in-place version uses a max-heap and keeps depositing each maximum at the end of the array itself). We'll leave it at the mention: sorting algorithms deserve their own course, but you now know that one of the big three (alongside mergesort and quicksort) is this tree disguised as an array.

Max-heap. What if you wanted the maximum first (tasks by estimated hours, scores)? Purist option: invert Heap's comparisons (parent ≥ children). Pragmatic option — and the standard idiom with heapq, which only ships a min-heap: negate the key on insert (insert(-value)) and negate on extract. The minimum of the negated values is the maximum of the originals. This trick will reappear in the next lesson's top-k exercise.

Common Mistakes and Tips

Sifting down by swapping with the wrong child. Always with the smaller of the two children; with the other, the property breaks in the very swap. It's the number-one bug in homemade heaps.
Forgetting that the heap isn't sorted. h._data is not a sorted list, and walking it doesn't yield ascending order (look at [1, 3, 2, 5, 9, 8]). Order only emerges by extracting. If you need to list everything in order repeatedly without draining anything, your structure is the AVL, not the heap.
Searching for or deleting an arbitrary element in O(log n). The heap doesn't index by value: locating "task T-13" is O(n). Variants with an auxiliary map (each element's position) exist — that's how real schedulers do decrease-key — but they aren't free and don't come with heapq.
Feeding it raw dicts (or anything non-comparable). insert(task) with two tasks of equal priority ends up comparing dictionaries: TypeError. The (priority, counter, task) tuple is the regulation outfit; the counter, its zipper.
Tip: in production use heapq — it's compiled C, well tested, and you now know exactly what it does inside (and why it operates on an ordinary list in plain view). Your own Heap is for learning and for interviews, where "implement a heap" remains a classic.

Exercises

Exercise 1: the trace without a computer

Without running any code: start from the heap [2, 5, 3, 9, 6, 8] and apply (a) insert(1) and then (b) extract_min(). Write the array after each swap. Then check with the Heap class.

Exercise 2: is it a valid heap?

Write is_min_heap(lst) that verifies in O(n) whether a list satisfies the min-heap property, and use it as an auditor: generate 100 random lists, turn them into heaps by inserting element by element into a Heap, and check that all 100 pass the audit (and that the original list almost never does).

Exercise 3: merging inboxes

Two TaskFlow teams merge their urgency inboxes (two Heaps with m and n elements). Write merge(h1, h2) that returns a new Heap with everything. Compare the cost of (a) extracting everything from both and inserting it into the new one, versus (b) concatenating the internal arrays and "heapifying" by sifting the internal nodes down back to front. Implement (b).

Solutions

Solution 1

(a) insert(1): 1 enters at i=6 → [2, 5, 3, 9, 6, 8, 1]. Its parent is i=2 (holds 3): 1 < 3 → [2, 5, 1, 9, 6, 8, 3]. New parent i=0 (holds 2): 1 < 2 → [1, 5, 2, 9, 6, 8, 3]. Done: two swaps, 1 at the top.

(b) extract_min(): 1 leaves; the last one (3) rises → [3, 5, 2, 9, 6, 8]. Children of 3: 5 and 2, smaller is 2: 3 > 2 → [2, 5, 3, 9, 6, 8]. Children of 3 (i=2): only 8 (i=5): 3 < 8, done. Comment: we've returned exactly to the starting heap — inserting and then extracting the freshly inserted minimum leaves the rest as it was, a sign that both operations touch only the essential path.

Solution 2

import random

def is_min_heap(lst):
    for i in range(1, len(lst)):
        if lst[i] < lst[(i - 1) // 2]:     # smaller than its parent? violation
            return False
    return True

failures = 0
for _ in range(100):
    original = [random.randint(0, 999) for _ in range(50)]
    h = Heap()
    for x in original:
        h.insert(x)
    assert is_min_heap(h._data)            # all 100 pass
    failures += not is_min_heap(original)
print(f"originals that weren't heaps: {failures}/100")   # ~100

Comment: the auditor walks each node checking it against its parent — and that's enough, because the heap property is local (direct parent-child). Contrast with the BST, where checking only against the parent was the classic mistake: there the property speaks about entire subtrees. Same gesture, opposite validity — understanding why is understanding the difference between partial and total order. (A 50-value random list being a heap "at birth" is extremely rare: hence the ~100.)

Solution 3

def merge(h1, h2):
    result = Heap()
    result._data = h1._data + h2._data             # concatenate: the shape is already valid
    for i in range(len(result._data) // 2 - 1, -1, -1):
        result._sift_down(i)                       # heapify: internal nodes back to front
    return result

a, b = Heap(), Heap()
for x in [4, 9, 6]: a.insert(x)
for x in [1, 7, 3]: b.insert(x)
c = merge(a, b)
print([c.extract_min() for _ in range(len(c))])   # [1, 3, 4, 6, 7, 9]

Comment: option (a) — extracting and inserting everything — costs O((m+n)·log(m+n)); option (b) concatenates in O(m+n) and heapifies in O(m+n): linear total, thanks to the bonus section's argument (the leaves, more than half, do no work). The loop starts at the last internal node (n//2 - 1, the parent of the last element) and moves back to the root: when _sift_down(i) runs, i's subtrees are already valid heaps — the same "children to parents" reasoning as postorder. It's literally heapq.heapify written by hand.

Conclusion

Promise kept: module 4's black box is open, and inside was a complete binary tree living in an array — 06-02's seed made structure. You now know its contract (parent ≤ children: partial order, just enough to keep the minimum at the root, versus the BST's total order), its two gestures (sift up on insert, sift down on extract, both O(log n) along a root-leaf path of guaranteed height), its cold start (heapify O(n)), its relatives (heapsort, max-heap by negation), and its place in TaskFlow: the definitive UrgentInbox, which closes the priority queue table by winning at the operation the other two paid at O(n). With this, the module's arsenal is complete: generic tree for hierarchies, traversals to exploit them, BST/AVL for order and ranges, B-tree for disk, and heap for urgencies. The next lesson adds no theory: it's the gym — six progressive exercises where all these pieces work together on TaskFlow, including the interview classics (validating a BST, rebuilding a tree, top-k with a heap). Time to train.

Heaps

Contents

The heap property: partial order, not total

The shape: complete tree = array with no gaps

Inserting: sift-up

Extracting the minimum: sift-down

The complete `Heap` class

`UrgentInbox` 2.0: the black box, opened

Bonus: heapify in O(n), heapsort, and the max-heap

Common Mistakes and Tips

Exercises

Exercise 1: the trace without a computer

Exercise 2: is it a valid heap?

Exercise 3: merging inboxes

Solutions

Solution 1

Solution 2

Solution 3

Conclusion

Data Structures Course

Module 1: Introduction to Data Structures

Module 2: Lists

Module 3: Stacks

Module 4: Queues

Module 5: Hash Tables and Dictionaries

Module 6: Trees

Module 7: Graphs

Module 8: Conclusions and Further Resources

Heaps

Contents

The heap property: partial order, not total

The shape: complete tree = array with no gaps

Inserting: sift-up

Extracting the minimum: sift-down

The complete Heap class

UrgentInbox 2.0: the black box, opened

Bonus: heapify in O(n), heapsort, and the max-heap

Common Mistakes and Tips

Exercises

Exercise 1: the trace without a computer

Exercise 2: is it a valid heap?

Exercise 3: merging inboxes

Solutions

Solution 1

Solution 2

Solution 3

Conclusion

Data Structures Course

Module 1: Introduction to Data Structures

Module 2: Lists

Module 3: Stacks

Module 4: Queues

Module 5: Hash Tables and Dictionaries

Module 6: Trees

Module 7: Graphs

Module 8: Conclusions and Further Resources

The complete `Heap` class

`UrgentInbox` 2.0: the black box, opened