How a binary heap works

Heaps and priority queues Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
import heapq
xs = [9, 4, 7, 1, 8, 2]
heapq.heapify(xs)
print(xs[0], xs[1] < xs[3] or xs[1] < xs[4], sorted(xs) == xs)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 1 True False

Right: the minimum is on top, parents are no larger than children, but the list is not sorted.

Heap order is weaker than sorted order, which is exactly why building it costs only O(n).

Why not the others?
  • B 1 True True. heapify does not sort the list.
  • C 9 False False. heapify moves the smallest value to index 0.

30-second answer

A binary heap is a complete binary tree where every parent is no larger than its children (for a min-heap). It is stored in a plain list: children of i at 2i + 1 and 2i + 2. Peek is O(1), push and pop are O(log n), and building from a list with heapify is O(n). Searching for an arbitrary value is O(n).

Practise saying it · 45 s. No recording, just a timer

Explain a binary heap.

Say your answer out loud, then check which of these points you covered:

  • Complete tree in a list
  • Parent no larger than children
  • O(log n) push and pop

Deep dive

Complete means every level is full except the last, filled from the left, so the list has no gaps.

A heap is not sorted; only the path from any node to the root is ordered.

Changing a priority needs the item's position; libraries often push a new entry and skip stale ones on pop.

Common mistakes

  • Expecting heap[1] to be the second smallest.
  • Searching a heap for a value as if it were a search tree.

Senior take & follow-ups

Draw the array and the tree together; it makes the index rule obvious.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you update a priority in heapq?

    Show hint

    Push a new (priority, item) entry and mark the old one stale; skip stale entries on pop.

  2. Why is the tree height log n?

    Show hint

    Each full level doubles the node count.

What each operation costs: Min Heap · Max Heap · Heap Operations · Priority Queue

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.