Paul's Python CoursePPC

Heaps

Not met yet

A heap is a list kept in an order that's only just good enough: no item is smaller than its parent, so the smallest is always at position 0. The children of position i are at 2 * i + 1 and 2 * i + 2, and its parent is at (i - 1) // 2. Adding an item puts it at the end and lets it climb past bigger parents; taking the smallest moves the last item to the top and lets it sink past smaller children. Both are O(log n). Python's heapq does all this to an ordinary list.

Try it

main.py

Output

Press Run and what your program prints shows up here.

Easy to get wrong

  • Thinks a heap kept in a list is in sorted order, rather than only having the smallest item at the front.
  • Thinks heappush adds the item to the end like append, so the list stays in the order things arrived.
  • Thinks heappop takes the last item in the list, like list.pop(), rather than the smallest.
  • Thinks the children of position i in a heap list are at 2i and 2i + 1, forgetting that the list counts from 0.
  • Thinks adding an item to a heap means looking at every item already in it, so it takes O(n) steps.
  • Thinks a sinking item can swap with either child, rather than the smaller one, so the smaller child can end up below a bigger one.

Where it comes up