Custom comparators and tie-breaking in heapq

Why this matters

A heap always gives back the smallest item first. "Smallest" is not a fact about the items. It is a rule that you give the heap. For a list of jobs, the smallest might mean the most urgent job, or the job that arrived first, or the job with the shortest run time. The rule that answers "which of these two comes first?" is the ordering of the items. In Python, the heapq functions decide order with one question only: "is item a less than item b?" They ask that question with the < operator.

Most real heap problems need a rule with more than one part. A hospital queue sees the most serious patient first. If two patients are equally serious, the one who arrived earlier goes first. A task runner might sort by due date, then by name. If you write the rule wrongly, the program usually does not crash. It hands back items in a slightly wrong order, and the bug shows up later in some other part of the program. That is why this lesson shows wrong versions next to right ones.

The heap's shape and its basic operations are covered in the earlier lessons of this module. This lesson is only about the rule the heap uses to decide order.

By the end of this lesson you will be able to write an order with two keys, add a counter so that equal items come out in the order they went in, reverse part of an order safely, and recognise the comparisons that quietly break a heap.

A comparison answers one question

In Python, a comparator is a function that takes two items and returns a negative number, zero, or a positive number. This is the convention that Python's functools.cmp_to_key expects:

• a negative number means the first item comes first,
• zero means the two items are equal for ordering purposes,
• a positive number means the second item comes first.

Most code does not need a comparator function. A class can tell Python how to compare its objects by defining a method named __lt__, which means "less than". The heapq functions call <, and < calls __lt__. A dataclass is a class that Python builds from a list of fields, so you do not write __init__ by hand. Adding order=True also writes the comparison methods, and it compares the fields in the order they are listed. The @ line above a class is a decorator. It passes the class to a function, here dataclass, that adds methods to it.

Here is the simplest heap. The items are plain numbers, and Python already knows how to compare them.

Output:

10
30
40

With numbers and strings, the default order is the smaller item first. A comparison rule is needed when the items are your own objects, or when you want a different order.

Example 1: one key, and the problem with equal keys

Now use something closer to a real job. Each job has a name, a priority number where 1 is the most urgent, and an arrival number that says when the job came in.

Start by ordering only on priority. The field(compare=False) call tells the dataclass to leave a field out of the comparison. The name and arrival are kept on the object, but they do not affect the order.

Output from one run on Python 3.14:

B priority=1 arrival=2
C priority=2 arrival=3
E priority=2 arrival=5
A priority=2 arrival=1
D priority=2 arrival=4

Job B comes first because its priority number is the smallest. That part is right. The four jobs with priority 2 come out as C, E, A, D. They were added as A, C, D, E, so the order is not the order they arrived, and nothing in the rule says what it should be. The rule says all four are equal, so the heap is free to return them in any order. The heapq documentation does not promise an order for items that compare as equal. This run gave one particular order. Another sequence of additions could give a different order, and nothing in the code tells you which one you will get.

Equal keys are common. Many jobs share a priority, many people share a score, and many tasks share a due date. If the order among them matters, you need a second key.

Example 2: two keys, and the order of the fields

With a dataclass, the fields are compared in the order they are written. The first field is the main key. The second field is the tie-break, which is used only when the first fields are equal. So putting arrival second gives a two-key order.

Output:

Job(priority=1, arrival=2, name='B')
Job(priority=2, arrival=1, name='A')
Job(priority=2, arrival=3, name='C')
Job(priority=2, arrival=4, name='D')
Job(priority=2, arrival=5, name='E')
True True

Now the four jobs with priority 2 come out in arrival order. The rule is written in the class, so it does not depend on how the heap happens to arrange its list.

The last line shows a side effect of compare=False. The two jobs Job(2, 1, "A") and Job(2, 1, "Z") are equal with ==, because the name is not part of the comparison. Keep that in mind when you use a dataclass as a key.

Why the arrival number works as a tie-break

A tie-break is the second rule that decides the order when the first rule gives a tie. Arrival is a good tie-break here because every job has a different arrival number. Two jobs can never be fully equal, so the heap always has one clear answer.

A tie-break is only as good as the key you pick. If two jobs had the same priority and the same arrival number, the heap would be back to an arbitrary order. In that case you need a third key, or a counter that you create yourself, as the next example shows.

The same rule as a comparison function

Sometimes a rule is easier to write as a function. functools.cmp_to_key turns a comparison function into a key that heapq can use. Each item is wrapped before it goes into the heap, and the original item is kept in the wrapper's obj attribute.

Output:

Job(priority=1, arrival=2, name='B')
Job(priority=2, arrival=1, name='A')
Job(priority=2, arrival=3, name='C')

The function returns a negative number, zero or a positive number, as described at the start of this lesson. The class version in the previous example is shorter, so use a comparison function only when the rule is hard to express with fields.

Example 3: an index as the last tie-break

Sometimes the items do not carry a natural second key. Think of a help desk that receives tickets with only a priority number. You still want tickets with the same priority to be served in the order they came in. The fix is to give every ticket a sequence number at the moment it is added. The first ticket gets 0, the next gets 1, and so on. This number is often called an index or a sequence number. It never repeats, so no two tickets are ever fully equal.

The itertools.count() function gives these numbers. Each call to next on it returns the next number, starting from 0.

Output:

(1, 1, 'urgent')
(2, 0, 'first')
(2, 2, 'second')
(2, 3, 'third')
(2, 4, 'fourth')

The urgent ticket goes first because its priority is 1. The four priority-2 tickets come out as first, second, third, fourth, which is the order they were added. The counter is the reason.

A tuple is compared one element at a time, from left to right. The second element is used only when the first elements are equal, so the sequence number acts as the tie-break. Because the numbers are unique, Python never reaches the name. A tuple can hold an object that has no order of its own, as long as the earlier elements settle every comparison. The section "A class without an order" shows the case where they do not.

The counter should be kept in one place, so that only one piece of code creates new numbers. If other code could make its own numbers, two tickets could end up with the same number, and the tie-break would stop working.

The index as a tie-break in a standard problem

In many problems the index is a position in a list. You may have a list of values and you need to know which value came from which spot. In that case, store the index next to the value in a tuple, (value, index). The comparison uses the value first and the index second. This keeps the answer the same every time the program runs, and it makes the result easy to check by hand.

Example 4: reversing an order safely

Often you want the largest item first. A heap is a min-heap, so the usual trick is to negate a number: the largest number becomes the smallest negated number. With two keys, the position of the minus sign matters. Consider players sorted by score from high to low, and then by name from A to Z. The right tuple negates only the score:

Output:

right: Ali Bo Zara Mia
sorted with reverse=True: ['Zara', 'Bo', 'Ali', 'Mia']

In the heap, the score comes from high to low (90, 90, 90, 75), and the names among the 90s go from A to Z (Ali, Bo, Zara). That is what the rule asks for.

The sorted line shows the same trap in another form. Its reverse=True flag reverses the whole key, so the names among the 90s also go from Z to A. To keep one key in its normal direction, you must negate the other key, and that works only for numbers. Trying to negate a string gives an error:

Output:

TypeError: bad operand type for unary -: 'str'

For a string key that must go in reverse, use a class with its own __lt__ method, or cmp_to_key with a comparison function. When you read a sort or heap rule, ask after each reversal: which key does this apply to?

Comparisons that break heap order

A heap depends on the comparison giving a consistent answer. If the comparison gives an answer that does not follow the rules of ordering, the heap can return items in the wrong order. The comparison must follow three rules:

• Antisymmetry: if a is less than b, then b is not less than a.
• Transitivity: if a comes before b, and b comes before c, then a comes before c.
• Fixed answers: the comparison between two items does not change while they sit in the heap.

Each of the following is a comparison that breaks one of these rules, or that looks correct and is not.

Subtraction is safe for ints

In languages with fixed-size integers, the subtraction a - b can wrap around to a wrong sign for very large values. Python int values have no fixed size, so the subtraction gives the right sign every time:

Output:

2**31 - 1 - (-1) = 2147483648
[-1, 5, 2147483647]

The value 2147483648 is correct, and the sort puts the values in the right order. The subtraction trick is safe here for ints. It is not a good habit with floats, because inf - inf gives nan (not a number), and a nan is neither less than nor greater than anything. A comparison with < and > avoids that question.

A comparison that returns a boolean

A new Python programmer may write a comparison that returns True or False, for example lambda a, b: a < b. Python does not reject this. cmp_to_key checks whether the result is less than zero. True and False are numbers too (1 and 0), so the check never succeeds, and the heap is never reordered:

Output:

[40, 30, 10, 20]

The output is not in order, and Python gives no error. This is the most dangerous mistake in this lesson, because the program runs and prints wrong results. The fix is to return a number: a negative number for "less", a positive number for "more", and zero for "equal". Subtraction for ints does that, and so does the next version.

A comparison that says both items are less

The comparison must never say that a is less than b and also that b is less than a. Here is a function that breaks that rule when the priorities are equal:

Output:

x < y: True  y < x: True

Both items claim to come first. The heap has no consistent answer for them, so the order it produces can depend on which pair it compares first. The fix is to return zero when the keys are equal:

Output:

x < y: False  y < x: False

A class without an order

If you push an object into a heap and the object has no __lt__ method, Python does not know how to compare it. A plain class does not have that method, so the comparison fails on the second item. A single item in an empty heap is never compared with anything, so the first push works.

Output:

first push ok
TypeError: '<' not supported between instances of 'NoOrder' and 'NoOrder'

The fix is to add an order to the class, usually with @dataclass(order=True) as in the examples above, or to write a __lt__ method yourself. For a class that is used in one place only, a tuple or a cmp_to_key wrapper is simpler.

None items

A heap does not accept None as a value that can be compared with numbers. Pushing None into an empty heap works, because nothing is compared. The code below pushes 5 first, so the push of None is compared and fails:

Output:

TypeError: '<' not supported between instances of 'NoneType' and 'int'

If a value can be missing, decide what it means before pushing it. Usually the right choice is to skip it, and to write that check in the code that calls heappush.

Keys that change after insertion

The last problem is the most common one in real code. If the field that the order reads changes while the item is inside the heap, the heap's order is wrong, and the heap may return an item that is no longer the smallest. This is a bug that shows up as a wrong answer, not as an error.

Output:

after change, smallest: Task(priority=9, name='a')
pop order: ['a', 'b', 'c']

The task b has priority 2, so it should come first. The heap still has a at the front, because the heap was built when a had priority 1. The rule to remember is: the key must not change while the item is in the heap. If it has to change, remove the item, change the key, and push the item again. The heapq module has no remove function, so the example takes the item out of the list, rebuilds the heap with heapq.heapify, and pushes the item back:

Output:

pop order after fix: ['b', 'c', 'a']

Common mistakes

Mistake 1: forgetting the second key. Two items have equal keys, and the output order looks random. Add a tie-break key, such as arrival time or a sequence number.

Mistake 2: putting the minus sign on the wrong key. Using sorted(..., reverse=True) reverses every key in each tuple. Negate only the key that should go in reverse, and check the output with two items that tie on the first key.

Mistake 3: negating a string. The error is TypeError: bad operand type for unary -: 'str'. Use a class with __lt__, or cmp_to_key, for a string that must go in reverse.

Mistake 4: returning a boolean from a comparison function. Python gives no error. The heap just keeps the wrong order. Return a negative number, zero or a positive number.

Mistake 5: using a class that has no order. The error is TypeError: '<' not supported between instances of .... Add @dataclass(order=True) or write __lt__.

Mistake 6: changing a key in place. The heap returns items in the wrong order, and no error is shown. Remove the item before changing its key, rebuild the heap, then push the item again.

Practice

Exercise 1. Write a heap that orders songs by plays from highest to lowest, and by year from oldest to newest when the plays are equal. Use tuples. Push three songs, and print their titles in order.

Show the answer

Push (-plays, year, title) for each song. The minus sign reverses only the plays, so the most-played song comes first. The year is not negated, so the oldest song comes first among songs with equal plays. The title is the last element, which keeps the order fixed if two songs have the same plays and year.

Output:

['Beta', 'Gamma', 'Alpha']

Exercise 2. Put words in a heap so that the shortest word comes first, and words of the same length come out alphabetically. Explain why a subtraction of lengths is safe here, and what is still missing if you use only the length.

Show the answer

The lengths are small whole numbers, so subtracting them is safe in Python, and the sign of the result is always right. Using only the length leaves words of the same length in an arbitrary order. A tuple (len(word), word) gives the length first and the alphabetical order second.

Output:

['fig', 'kiwi', 'pear', 'apple']

Exercise 3. Explain why a tuple (value, index) needs no comparison function to put equal values in index order. Push (5, 2), (5, 0), (1, 7) and (5, 1) into a heap, and say what order comes out.

Show the answer

A tuple is compared element by element. The values are compared first, and the index is compared only when the values are equal. So the pairs with value 5 come out in index order.

Output:

[(1, 7), (5, 0), (5, 1), (5, 2)]

Exercise 4. The comparison -1 if a.priority <= b.priority else 1 is used for a heap. Show with two items of priority 2 why this breaks the heap, and write a correct comparison.

Show the answer

With two items of equal priority, the comparison returns -1 in both directions. The first item is less than the second, and the second is less than the first. That contradicts itself, so the heap cannot give a consistent order for equal items. The fix returns zero when the priorities are equal:

Output:

x < y: False  y < x: False

Exercise 5. A job queue uses a dataclass with priority and arrival as its compared fields. Two jobs have the same priority and the same arrival number. Explain what order you can expect, and add one field that fixes it.

Show the answer

The queue makes no promise about their order. Both comparisons are equal, so the heap treats them as equal, and heapq does not define the order of equal items. To fix it, add a third compared field that is unique for each job, such as a sequence number given when the job is added. Put it last, so it is used only as the final tie-break.

Output:

['a', 'b', 'c']

Summary

• A comparison decides which item is less. heapq only asks "is a less than b?", so a class needs __lt__, a dataclass with order=True, a tuple, or a cmp_to_key wrapper.
• Put the main key first and the tie-break key second. For a tuple, the order of the elements is the order of the keys.
• When items have no natural second key, add a sequence number from itertools.count() as the last key, so equal items come out in the order they were added.
• Negate a number to reverse it. Put the minus sign on the one key that should be reversed, and read reverse=True as a change to every key.
• A comparison must never say that a is less than b and also that b is less than a. Return a number, not a boolean, and never change a key while the item is in the heap.