Skip to content
Tutorials Center
My learning

Topics

Lesson 106 of 225 ยท Heaps

Binary Heaps

Learn binary heaps in Python: the complete tree stored in a list, index formulas, min and max heaps, sift up and down, and why build-heap runs in O(n).

A priority queue promises to hand you the best item next. With an unsorted list, finding the best item costs O(n). With a sorted list, inserting costs O(n). A binary heap gets both operations down to O(log n), and it does so with one of the most elegant tricks in computer science: a tree that is stored in a plain list, with no node objects and no pointers.

Heaps power heap sort, Dijkstra's shortest paths, event simulations, "top k" queries and the schedulers in many operating systems. In this lesson you will build a min-heap from scratch, trace it step by step, and prove why building a heap from a whole list takes only O(n) time. The next lesson shows the ready-made heapq module.

What a heap is

A binary heap is a binary tree with two properties:

  1. Shape property: the tree is complete. Every level is full except possibly the last, and the last level is filled from left to right with no gaps.
  2. Heap property: every node is ordered against its children. In a min-heap, a parent is less than or equal to both children, so the smallest element is at the root. In a max-heap, a parent is greater than or equal to its children, so the largest is at the root.
TEXT
min-heap:
              2
           /     \
         5         3
        / \       / \
       9   6     8   7
      /
     10

Every parent <= its children.
Nothing is said about siblings: 5 and 3 are in no particular order.

Notice what the heap property does not say. It does not sort the tree. Left and right subtrees are unrelated, and a node may be larger than a cousin on the level above. A heap is only "partly sorted", exactly enough to find the minimum instantly. That looseness is why updates are cheap.

The tree lives in a list

Because the tree is complete, you can number its nodes level by level from left to right, and store them in a list in that order. No pointers are needed, because the position tells you the relatives. For the element at index i (starting at 0):

  • left child: 2*i + 1
  • right child: 2*i + 2
  • parent: (i - 1) // 2
TEXT
tree above, written level by level:

index:   0  1  2  3  4  5  6  7
value:  [2, 5, 3, 9, 6, 8, 7, 10]

node 3 (value 9): parent = (3-1)//2 = 1 (value 5), left child = 7 (value 10), right child = 8 (does not exist)
Python Index formulas and the heap property

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Since a complete tree with n nodes has floor(log2 n) + 1 levels, the height is O(log n). Every heap operation walks along a single root-to-leaf path, which is why it costs O(log n).

Insert: sift up

To add a value:

  1. Append it at the end of the list. That is the next free spot in the last level, so the shape stays complete.
  2. The new value may now be smaller than its parent, which breaks the heap property. Sift up (also called bubble up or percolate up): while the value is smaller than its parent, swap them.

Only the path from the new leaf to the root can be affected, and it has O(log n) nodes. Inserting 1 into the heap above:

TEXT
[2, 5, 3, 9, 6, 8, 7, 10, 1]       append 1 at index 8; parent is index 3 (9)
[2, 5, 3, 1, 6, 8, 7, 10, 9]       1 < 9: swap; now at index 3, parent index 1 (5)
[2, 1, 3, 5, 6, 8, 7, 10, 9]       1 < 5: swap; now at index 1, parent index 0 (2)
[1, 2, 3, 5, 6, 8, 7, 10, 9]       1 < 2: swap; now the root. Done.

Remove the minimum: sift down

The minimum is at index 0, but removing it leaves a hole at the top. Shifting everything left would cost O(n). Instead:

  1. Move the last element to the root, and shrink the list by one. The shape is still complete.
  2. The root is probably too large now. Sift down: compare it with both children, and if either is smaller, swap it with the smaller child. Repeat from that child's position until the value is no larger than its children, or it becomes a leaf.

Why the smaller child? After the swap, that child becomes the parent of its sibling, so it must be the smaller of the two for the heap property to hold.

Python A min-heap from scratch with a trace

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Popping everything yields the values in sorted order. That is the idea behind heap sort: n pushes and n pops cost O(n log n) in total.

Max-heaps

A max-heap flips every comparison: swap while a child is greater than its parent. In Python you rarely need a second class. The common trick is to store negated numbers in a min-heap (see heapq). A more general approach is a heap that takes a comparison key:

Python One heap class, min or max

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Building a heap from a list: O(n), not O(n log n)

Given n values, you could push them one by one: n pushes at O(log n) each give O(n log n). There is a faster way called heapify (Floyd's algorithm):

  1. Treat the list as a complete tree, in whatever order it came.
  2. Go through the nodes from the last parent down to the root (indices n//2 - 1 down to 0) and sift each one down.

Leaves are already valid one-node heaps, so you skip them. By the time you sift down node i, both of its subtrees are valid heaps, so one sift-down fixes the whole subtree.

Why is that O(n)?

Sift-down cost depends on a node's height (distance to the deepest leaf below it), not its depth. Most nodes are near the bottom:

  • about n/2 nodes are leaves (height 0, cost 0),
  • about n/4 nodes have height 1 (cost at most 1),
  • about n/8 nodes have height 2 (cost at most 2), and so on.

The total work is at most n/4 * 1 + n/8 * 2 + n/16 * 3 + .... That sum equals n/2 * (1/2 + 2/4 + 3/8 + ...), and the series in parentheses converges to 2, so the total is at most about n. Linear time. Pushing one by one is slower because the many nodes at the bottom each travel up the tall distance, whereas heapify moves the few nodes at the top down the tall distance.

Python Counting swaps: heapify versus repeated push

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Compare the columns: heapify's swap count stays below n, while pushing grows like n log n.

Complexity

Operation Time Notes
peek (min or max) O(1) the root
push O(log n) worst, O(1) average for random input sift up
pop O(log n) sift down
build from a list O(n) Floyd's heapify
search for an arbitrary value O(n) the heap is not sorted
delete an arbitrary value O(n) to find, O(log n) to repair needs a position index to be faster
space O(n) one list, no pointers

The O(1) average push for random data holds because a random new value usually stays near the bottom, where most nodes live.

Heaps are not good at "find this value" or "list all values in order". If you need those, use a balanced tree (AVL or red-black) or a sorted list. A heap is the right tool exactly when you only ever ask for the extreme.

Common mistakes

  • Off-by-one in the index formulas. The formulas 2*i + 1 and 2*i + 2 are for 0-based lists. For 1-based arrays they are 2*i and 2*i + 1.
  • Swapping with the wrong child. In a min-heap, sift down with the smaller child. Using the larger one can break the heap property for the sibling.
  • Forgetting the bounds check. A node may have 0, 1 or 2 children. Always check child < n.
  • Heapifying in the wrong direction. You must go from the last parent to the root. Going from the root down does not guarantee that the subtrees below are already heaps.
  • Assuming the list is sorted. The heap list [1, 2, 3, 5, 6, 8, 7, 10, 9] is not in sorted order. Only the root has a guarantee.
  • Popping from an empty heap. Check len(heap) first.

When to use heaps

Use a heap when you repeatedly need the smallest or largest of a changing collection: scheduling, "k best" problems (top-k), a running median (two heaps), merging sorted streams (merge k lists) and graph algorithms such as Dijkstra. Avoid them when you need sorted traversal, fast arbitrary search or deletion by value.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In a 0-based heap array, where is the parent of the node at index 9?

    The parent is (9 - 1) // 2 = 4. Index 4 has children 9 and 10.
  2. 2. Which statement about a min-heap is always true?

    The heap property only orders each parent against its children. Siblings and cousins can be in any order, so the list is not sorted, and the smallest value is at the root.
  3. 3. During sift down in a min-heap, which child do you swap the parent with?

    The smaller child will become the parent of its sibling, so it must be the smaller of the two for the heap property to hold. If neither child is smaller than the parent, the sift stops.
  4. 4. Why does building a heap with Floyd's heapify take O(n) while n pushes take O(n log n)?

    About half the nodes are leaves that never move, a quarter can move at most one level, and so on. The sum of these small costs converges to about n.
  5. 5. What is the time to remove the minimum from a binary heap with n items?

    Reading the minimum is O(1), but removing it moves the last leaf to the root and sifts it down one root-to-leaf path of length O(log n).

Summary

  • A binary heap is a complete binary tree with the heap property (min-heap: parent <= children). Only the root is guaranteed to be the extreme value.
  • It is stored in a list: children of i are 2i + 1 and 2i + 2, the parent is (i - 1) // 2.
  • push appends and sifts up, pop moves the last element to the root and sifts down, both in O(log n). peek is O(1).
  • Heapify builds a heap from a list in O(n) by sifting down every non-leaf from the last parent to the root.
  • A max-heap flips the comparisons. Heaps cannot search or iterate in sorted order efficiently.

Next: Heaps in Python: heapq