Heap operations

A heap is a complete binary tree stored in an array where every parent is smaller (or larger) than its children. The smallest element is always at the top, and push and pop keep that in O(log n).

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

Explain the heap property and how the array stores the tree
Trace a push and a pop with sift-up and sift-down
Spot the assumption that the array beyond the root is sorted

In practice

A few lines that show Heap operations doing its job.

Python

import heapq

tasks = []
heapq.heappush(tasks, (2, "write tests"))
heapq.heappush(tasks, (1, "fix build"))
heapq.heappush(tasks, (3, "refactor"))

while tasks:
    priority, name = heapq.heappop(tasks)
    print(priority, name)           # 1 fix build, 2 write tests, 3 refactor

# max-heap: push negated keys

The common mistake

Watch for

Reading tasks[1] and tasks[2] expecting the second and third smallest. Only the root is ordered; the rest of the array is not sorted, and popping is the only way to get items in order.

What to know first

Your roadmap puts these before Heap operations, unless you already know them.

Tree traversals

How it stays learned

Once a session shows you understand Heap operations, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

Day 3First recall, while it is fresh
Day 7Second, a week on
Day 18Last, when it has settled

Where it leads

Topics that build on Heap operations.

Next in the moduleBuilding a heap →