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 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:

        1
      /   \
     3     2
    / \   /
   7   4 5

list:  [1, 3, 2, 7, 4, 5]
index:  0  1  2  3  4  5

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).

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.