Heaps and Priority Queues
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.
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.
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.
Tip
Two ways to take the k best
Heapify everything and pop k times: O(n + k log n). Or keep a bounded heap of size k while scanning: O(n log k).
Which is better depends on how k compares with n. For k much smaller than n they are close, and for k close to n the heapify version wins. Either is a fine answer if you can say what it costs, and saying that is what the question is really about.
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.
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.
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.