Select the smallest records with an explicit stable heap tie key

By Batu · English technical notes

To select the smallest records with an explicit stable heap tie key, enumerate the input and pass (score, original_index) as the heapq.nsmallest() key. For A(2), B(1), C(1), and D(3), selecting two records returns B then C. The original positions make the equal-score ordering part of the code’s contract rather than an unstated consequence of a score-only recipe.

The fixture keeps the records intact and creates (index, record) pairs through enumerate(). Its composite key first ranks lower scores, then ranks earlier source positions when scores match. The assertion checks the selected pair and their retained positions. Printing the composite keys makes the decision visible: B has (1, 1) and C has (1, 2).

Use this pattern when you want a bounded selection and need a defined source-order rule for ties. It does not claim that nsmallest() is always faster than sorting; the best choice depends on the data, selection size, and surrounding work. It also does not replace a domain-specific secondary ranking—use one if, for example, a timestamp should decide ties instead of input order.

heapq.nsmallest(n, iterable, key=None) is the standard-library function used here. This code needs Python 3; it uses no newer API.

AI assistance disclosure: this article was prepared with AI assistance and checked against the shown synthetic fixture.

Source: Python heapq.nsmallest.

from heapq import nsmallest

records = [
    {"name": "A", "score": 2},
    {"name": "B", "score": 1},
    {"name": "C", "score": 1},
    {"name": "D", "score": 3},
]

enumerated = list(enumerate(records))
chosen = nsmallest(
    2,
    enumerated,
    key=lambda pair: (pair[1]["score"], pair[0]),
)

assert records == [
    {"name": "A", "score": 2},
    {"name": "B", "score": 1},
    {"name": "C", "score": 1},
    {"name": "D", "score": 3},
]
assert [(index, record["name"]) for index, record in chosen] == [(1, "B"), (2, "C")]

print("input:", records)
print("chosen:", [
    (record["name"], (record["score"], index))
    for index, record in chosen
])

input: [{'name': 'A', 'score': 2}, {'name': 'B', 'score': 1}, {'name': 'C', 'score': 1}, {'name': 'D', 'score': 3}]
chosen: [('B', (1, 1)), ('C', (1, 2))]