Data structures in Python

Heap Lab

A heap is a tree that lives in a plain Python list. Step through insert, delete and heapify and watch the same values move in the tree and in the list at the same time.

The heap property

# min heap: every parent <= its children
min_heap = [1, 3, 2, 7, 5, 4]

# max heap: every parent >= its children
max_heap = [10, 7, 9, 3, 5, 4]

So the root, arr[0], is always the smallest (min heap) or largest (max heap) value. That is the only promise: siblings are in no order, and the list is not sorted.

A complete binary tree, stored in a list

parent = (i - 1) // 2
left   = 2 * i + 1
right  = 2 * i + 2
# indices n // 2 .. n - 1 are leaves

Levels fill left to right with no gaps, so a node's position alone tells you where its parent and children are. No node objects, no pointers. A heap of n values is only about log₂ n levels tall.

Min vs max: one operator

# min heap: the smaller value moves up
if arr[i] < arr[parent]: ...

# max heap: the larger value moves up
if arr[i] > arr[parent]: ...

Every function in this lab is identical for both kinds except that one comparison. smallest and largest are just variable names. Flip the toggle below and only those lines change.

Two repair moves

sift_up(arr, i)    # value too good for its spot
sift_down(arr, i)  # value too poor for its spot

Insert adds at the end and sifts up. Delete moves the last value to the root and sifts down. Heapify sifts down every parent. You will also see sift_down written as shift_down; same function.

being comparedthe value being siftedsettled: already in heap ordernot checked yetindex variable (i, parent, left…)

Tip: the ← and → keys step too. The min heap examples are the max heap ones mirrored, so both take the same steps.

Common mistakes

Sift-up with no way out

# loops forever once the value is in place
while i > 0:
    parent = (i - 1) // 2
    if arr[i] < arr[parent]:
        arr[i], arr[parent] = arr[parent], arr[i]
        i = parent

    else:
        break   # parent is fine: stop

When the parent is already in order nothing changes, so i stays the same and the loop spins forever. The else: break is not optional.

Delete that crashes or forgets the root

def delete_min(arr):
    arr[0] = arr.pop()  # IndexError if len is 1
    sift_down(arr, 0)   # old root is lost

def delete_min(arr):
    root = arr[0]
    last = arr.pop()
    if arr:
        arr[0] = last
        sift_down(arr, 0)
    return root

On a one-value heap, pop() empties the list first, so arr[0] = … has nowhere to write. Save the root before you overwrite it, and return it.

Heapify in the wrong direction

# top-down: walks from the root towards the leaves
for i in range(len(arr) // 2):
    sift_down(arr, i)
# [1, 2, 3, 4, 5, 6, 7] -> [3, 5, 7, 4, 2, 6, 1]
# as a max heap the root should be 7, not 3

sift_down(arr, i) only works when both subtrees below i are already heaps. Going bottom-up, from len(arr) // 2 - 1 down to 0, makes that true every time. Top-down, a big value deep in the tree climbs at most one level and never reaches the root.

Why heapify is O(n), not O(n log n)

Heapify calls sift_down about n/2 times, and one sift_down can cost O(log n). Multiplying gives O(n log n), but that bound is loose. A node can only sink as far as its height, the number of levels below it, and most nodes have almost nothing below them.

A full heap of n = 15 values (4 levels)
Level	Nodes	Heapify: max swaps each (height)	Heapify: max total	Insert one at a time: max swaps each (depth)	Insert: max total
0 (root)	1	3	3	0	0
1	2	2	4	1	2
2	4	1	4	2	8
3 (leaves)	8	0	0	3	24
Total	15		11		34

Work per level, n = 15

Read the table bottom-up. About n/2 nodes are leaves and cost nothing. About n/4 sit one level up and can sink at most 1 level, n/8 can sink 2, and so on. The total is

n/4 · 1 + n/8 · 2 + n/16 · 3 + … = n · (1/4 + 2/8 + 3/16 + …) < n

The series in brackets adds up to 1, so heapify does fewer than n swaps (and at most two comparisons per swap level), which is O(n). The expensive nodes, the ones that can sink far, are the rare ones near the root.

Inserting one at a time flips this around. Each new value lands at the bottom and may climb its full depth, and the bottom is where most nodes are: the 8 leaves alone can cost 3 swaps each. That is about n · log₂ n in total, so building by inserting is O(n log n).

Counts measured by the lab (max heap inputs shown; the mirrored min heap inputs give the same counts)
Input	Heapify	Build by inserting
The 11-value example `[3, 17, 10, 1, 2, 8, 9, 4, 5, 7, 6]`	14 comparisons, 5 swaps	17 comparisons, 8 swaps
Worst case, 15 values ascending (max heap) / descending (min heap)	22 comparisons, 11 swaps	34 comparisons, 34 swaps

The worst-case run hits both bounds from the table exactly: 11 swaps for heapify, 34 for inserting. Try it: pick Heapify or Build by inserting above and enter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 with Max heap selected.

Cost of each operation

Operation	Time	How	Python `heapq`
Peek at the root	O(1)	read `arr[0]`	h[0]
Insert	O(log n)	append, then sift up at most one level per swap	heappush(h, x)
Delete the root	O(log n)	last value to the root, then sift down	heappop(h)
Heapify (build from a list)	O(n)	sift down every parent, bottom-up	heapify(h)
Build by inserting n values	O(n log n)	n separate inserts	n × heappush
Search for any value	O(n)	heap order says nothing about left vs right, so check everything	x in h
Heap sort	O(n log n)	heapify, then delete the root n times; in place with O(1) extra space	[heappop(h) for _ in range(len(h))]

Python's heapq works on a plain list and is always a min heap. For a max heap, the usual trick is to push negated values and negate again on the way out:

import heapq

h = []
for x in [10, 7, 9]:
    heapq.heappush(h, -x)   # store -x
biggest = -heapq.heappop(h) # 10