What a Heap Is

Heaps & Top-K, lesson 1 of 3

What a Heap Is

A complete binary tree packed into a list that keeps the minimum on top.

11 min, 0 of 3 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

Many problems boil down to one question asked over and over: "what is the smallest (or largest) thing right now?", while new items keep arriving.

Your options with plain lists:

Structure insert get min remove min
unsorted list O(1) O(n) O(n)
sorted list (largest first) O(n) O(1) O(1) from the end
heap O(log n) O(1) O(log n)

A heap is the balanced middle ground: it never sorts everything, it only keeps enough order to find the minimum instantly.

The shape. A binary heap is a complete binary tree (every level full except the last, which fills left to right), so it fits in a plain list with no pointers: read the tree level by level, left to right.

Diagram

A min-heap and its list

137425103122734455

Index 1 holds 3. Its children sit at 2*1 + 1 = 3 and 2*1 + 2 = 4 (7 and 4), its parent at (1 - 1) // 2 = 0 (1).

node i = 1
its children
its parent

For the node at index i:

  • children: 2*i + 1 and 2*i + 2
  • parent: (i - 1) // 2

The rule (min-heap): every parent is <= its children. That's all. Siblings can be in any order, so the list is not sorted, but the root h[0] is always the minimum.

Example

Walking the tree through list indexes

Every value is >= its parent. Change h to [1, 3, 2, 0, 4, 5] and spot which parent/child pair breaks the rule.

Push = append + sift up. Put the new value at the end (keeps the shape complete), then swap it with its parent while it is smaller than the parent.

Pop = move last to root + sift down. Remember the root (the answer), move the last element to index 0, then swap it with its smaller child while it is bigger than that child.

A complete tree with n nodes has height about log₂ n, and each sift walks one root-to-leaf path, so both are O(log n).

Walkthrough

push(0): append, then sift up

137425103122734455
Step 1 of 4

A valid min-heap: every parent is <= its children. Now push(0).

moving value
parent it's compared with
broken parent/child pair
valid heap
Walkthrough

pop(): move the last value up, then sift down

037415200311273445526
Step 1 of 4

pop(): the root 0 is the answer. To keep the tree complete, the last value (2, index 6) takes its place.

moving value
value it swaps with
child that's bigger
broken parent/child pair
popped value / valid heap
Example

A tiny min-heap, with traces

Pops come out in sorted order (1, 3, 4, 5, 8) even though the list is never fully sorted. Popping everything is exactly heapsort: O(n log n).

Quiz

What does this print?

Quiz

In a min-heap stored as a Python list h, which is always true?

Exercise

Is it a min-heap?

Write is_min_heap(h) that returns True when the list satisfies the min-heap rule (every parent <= each of its children) and False otherwise. An empty list is a valid heap.

Tip: check each index against its parent, or each parent against its children at 2*i + 1 and 2*i + 2.