Heaps & Priority Queues — Data Structures Course

What you'll learn

A heap is a tree that keeps the largest (or smallest) value instantly reachable at the root. It's the structure behind the priority queue — and it lives entirely inside a plain array.

By the end you'll be able to:

State the heap property and map a heap onto an array
Insert with sift-up and extract with sift-down
Use a priority queue and know its O(log n) costs

The heap property

A max-heap is a complete binary tree (filled left to right, every level full except maybe the last) where every parent is ≥ its children. So the maximum is always the root — readable in O(1). (A min-heap is the mirror: every parent ≤ its children.)

A tree in an array

Because a heap is complete, it needs no pointers — store it level by level in an array, and arithmetic gives you the parent and children of any index:

The array is the tree

parent(i) = (i − 1) / 2left(i) = 2i + 1right(i) = 2i + 2

No node objects, no pointers — just an array and index math.

Insert (sift up)

Add the new value at the next open leaf, then sift it up: while it's bigger than its parent, swap. At most one swap per level — O(log n):

Insert 45 and sift it up

Heap insert (sift up)

1/5A max-heap: every parent is ≥ its children, so the maximum (50) sits at the root.

Yellow = comparing a child with its parent · purple = the value moving up.

Extract-max (sift down)

The max is the root. To remove it, move the last leaf to the root and sift it down: repeatedly swap with the larger child until the heap property is restored — again O(log n):

Extract the max and sift down

Heap extract-max (sift down)

1/5extract-max returns the root, 50 — always the maximum, in O(1) to read.

Swap with the larger child each step until the value settles.

Key idea

Building a heap from n items by inserting one at a time is O(n log n), but a clever bottom-up heapify does it in O(n) — that's the trick behind heap sort (Module 13).

In code

Language

heap.py

import heapq
# Python's heapq is a MIN-heap
h = []
heapq.heappush(h, 30)
heapq.heappush(h, 50)
heapq.heappush(h, 40)
print(heapq.heappop(h))     # 30 (the smallest)

# manual max-heap sift-up on an array
def sift_up(h, i):
    while i > 0 and h[(i - 1) // 2] < h[i]:
        p = (i - 1) // 2
        h[i], h[p] = h[p], h[i]
        i = p

Recap & quick check

Key takeaways

A max-heap is a complete binary tree where every parent ≥ its children; the max is the root.
It's stored in an array: parent = (i−1)/2, children = 2i+1 and 2i+2.
Insert adds at the end and sifts up; extract-max moves the last leaf to the root and sifts down.
peek is O(1); insert and extract are O(log n).
A heap implements a priority queue and powers heap sort.

Quick check

1. In a max-heap, where is the largest element?

2. For a 0-based array heap, the children of index i are at:

3. After removing the root, how is the heap repaired?

4. Insert and extract on a heap are:

Heaps rank by priority. Next, a tree that indexes strings by their characters for instant prefix search. Next up: Module 21 — Tries.