Pointer Walk

Heaps

The smallest item always floats to the top. Insert swaps its way up, and removing the top lets the last item sink.

Data StructuresBeginner9 min read

Always knowing the smallest

A hospital waiting room does not call patients in the order they arrived. It calls the most urgent. New patients keep arriving, and each time the question is the same: who is most urgent right now?

Keeping everyone fully sorted would answer it, but sorting is more work than needed. You never ask who is 7th. You only ever ask for the top one.

A heap is built for exactly that. It supports two operations, both fast:

  • insert a new item, and
  • remove the smallest item.

This page uses a min-heap, where the smallest is on top. A max-heap is the same idea turned upside down.

The one rule

A heap is a tree where every parent is smaller than its children. That is the only rule. Brothers and sisters can be in any order.

Follow the rule up the tree and one thing is guaranteed: the smallest value of all sits at the top.

The tree is also kept complete: every level is full except possibly the last, which fills from the left. That shape matters for the next two operations.

A min-heap: insert, then remove the smallestInteractive
259738

The same heap as it is really stored: one array

02
15
23
39
47
58

Start. A min-heap. The rule: every parent is smaller than its children. So the smallest value is always at the top.

Insert: add at the bottom, swap upwards

  1. Put the new value in the first free spot

    The bottom of the tree, as far left as possible. The shape stays complete.

  2. Compare it with its parent

    If it is smaller, the rule is broken. Swap them.

  3. Repeat from its new position

    Stop when the parent is smaller, or when it reaches the top.

Remove the smallest: move the last to the top, swap downwards

  1. Take the top value. That is the answer

    It leaves a hole at the root.

  2. Move the last value into the hole

    The shape is complete again, but the rule is probably broken at the top.

  3. Compare it with its children and swap with the smaller one

    The smaller child must go up, or it would end up above its own brother.

  4. Repeat until it is smaller than its children

    Or until it has no children.

Both operations follow one path between the top and the bottom. A complete tree with a million items is only 20 levels deep, so each takes at most about 20 swaps.

It is secretly an array

A complete tree has no gaps, so it can be stored level by level in a plain array with no pointers at all. For the item at position i:

RelationPosition
Its left child2 * i + 1
Its right child2 * i + 2
Its parent(i - 1) // 2
python
import heapq

waiting = []
heapq.heappush(waiting, (2, "sprained ankle"))    # (priority, patient)
heapq.heappush(waiting, (1, "chest pain"))
heapq.heappush(waiting, (3, "paperwork"))

heapq.heappop(waiting)                            # (1, "chest pain")

Good at

  • Insert and remove-smallest both take a number of steps that grows very slowly with size
  • Looking at the smallest (without removing it) is instant
  • One compact array, no pointers

Where it bites

  • Finding any other item means searching the whole thing
  • It is not sorted: only the top is in a known place

Where you will meet it

  • Priority queues: task schedulers, and timers that must fire in order.
  • Shortest routes: Dijkstra's algorithm keeps the places still to visit in a heap, nearest first.
  • Top 10 of a million: keep a heap of the 10 best seen so far and compare each new item only with the worst of those.
  • Heapsort: put everything in a heap, then remove the smallest again and again.

Key takeaways

  • A heap keeps the smallest item at the top without keeping everything sorted.
  • The rule: every parent is smaller than its children.
  • Insert adds at the bottom and swaps upwards. Remove takes the top, moves the last item there, and swaps downwards.
  • Both follow one path through the tree, so they stay fast as the heap grows.
  • The tree is stored as a flat array, with children at 2i + 1 and 2i + 2.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    7 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress