Lessons · Python · heaps (the smallest first)

Always hand me the smallest

A heap keeps only enough order to know its minimum. heapq.heappush and heapq.heappop each cost about log n, and the smallest is always at index 0.

Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.

What it is for

When you need the best few out of an enormous number of things, sorting everything is wasted work. A heap of size k gives you the top k for n log k, and it never has to hold the whole stream in memory.

How to think about it

Say 'smallest so far' or 'best k' and reach for heapq. For the k LARGEST, keep a heap of size k and pop the smallest whenever it grows past k: the root is the weakest survivor.

Worked example

import heapq

The heap lives in the standard library; there is no class.

h = []

A plain list, kept in heap order by the functions.

for v in [5, 1, 9, 3]:

    heapq.heappush(h, v)

Each push settles the value into place.

print(h[0])

print(heapq.heappop(h), heapq.heappop(h))

1 3

stream, k, best = [7, 2, 9, 4, 11, 1], 3, []

Keep the three largest of a stream.

for v in stream:

    heapq.heappush(best, v)

In it goes.

    if len(best) > k: heapq.heappop(best)

Out goes the smallest: it can never be in the top three.

print(sorted(best))

[7, 9, 11]

Your turn

Drop the weakest survivor so only k remain.

heapq.heappush(best, value)
if len(best) > k:
    heapq.(best)

The trap

h[0] is the smallest, but the rest of the list is NOT sorted. Printing a heap shows a jumble, and that is correct: partial order is what makes it cheap.

Practise heaps (the smallest first) on HoneA question on it now, a coding challenge where there is one, and it is remembered for review. Free, no email needed.