Ordering by something you compute

The heap orders by whatever you put first in the tuple, which is usually not the data itself.

Key idea

The key is a decision

The items you are choosing among are rarely the numbers you want to order by. Points have distances, tasks have deadlines, words have frequencies. The heap needs the ordering quantity first and the item after it.

Computing that quantity is usually one line, and choosing it correctly is the actual problem.

1import heapq2 3people = [("ana", 31), ("bo", 27), ("cy", 45)]4 5heap = [(age, name) for name, age in people]6heapq.heapify(heap)7print([name for _, name in [heapq.heappop(heap) for _ in range(2)]])

Why it works

Do not compute more than you need

When ordering by a distance, the square root is unnecessary. Squared distance orders identically to real distance because squaring is increasing over non-negative numbers, so comparing squares gives the same order.

That is worth doing: it avoids floating point entirely and keeps the arithmetic exact. The general principle is that any strictly increasing transformation of a key produces the same ordering, so use whichever form is cheapest and most exact.

1import heapq2 3points = [(3, 4), (1, 1), (0, 5)]4heap = [(x * x + y * y, x, y) for x, y in points]     # no square root5heapq.heapify(heap)6 7for _ in range(2):8    squared, x, y = heapq.heappop(heap)9    print((x, y), squared)

Both (3, 4) and (0, 5) are at squared distance 25; the tie fell through to the next tuple element, which is the subject of the next section

Gotcha

Ties fall through to the next tuple element

Two items with equal keys compare their second element. If that is a dict or a custom object without ordering, Python raises TypeError at an unpredictable moment, because it only happens when a tie actually occurs.

Insert a unique increasing counter between the key and the payload. It breaks every tie deterministically and never compares the payload at all. Bugs of this kind are especially unpleasant because small test inputs often have no ties.

1import heapq2 3heap = []4for counter, task in enumerate([{"id": "a"}, {"id": "b"}]):5    heapq.heappush(heap, (1, counter, task))     # same priority, no crash6 7print(heapq.heappop(heap)[2]["id"])

Predict the output· 5 min

Predict the output: ordering by a value you compute

A heap orders whatever you push. Here the pushed value is a pair whose first element is a computed distance rather than anything present in the input. Type the two lines it prints.

Python

1import heapq2 3points = [(3, 3), (5, -1), (-2, 4)]4 5heap = []6for x, y in points:7    heapq.heappush(heap, (x * x + y * y, (x, y)))   # computed key first8 9print([entry[0] for entry in sorted(heap)])10print(heapq.heappop(heap)[1])

Printed output

Problem· 20 min

K Closest Points To Origin

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 22 min

Kth Largest Element In An Array

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1import heapq2 3points = [(3, 4), (1, 1), (0, 5)]4heap = [(x * x + y * y, x, y) for x, y in points] # no square root5heapq.heapify(heap)6 7for _ in range(2):8 squared, x, y = heapq.heappop(heap)9 print((x, y), squared)

1import heapq2 3points = [(3, 3), (5, -1), (-2, 4)]4 5heap = []6for x, y in points:7 heapq.heappush(heap, (x * x + y * y, (x, y))) # computed key first8 9print([entry[0] for entry in sorted(heap)])10print(heapq.heappop(heap)[1])