6 / 7 Heaps & Priority Queues

The Pushes Were Fine

import heapq

class Job:
    def __init__(self, name):
        self.name = name

q = []
heapq.heappush(q, (5, Job("backup")))    # line A
heapq.heappush(q, (3, Job("index")))     # line B
heapq.heappush(q, (5, Job("email")))     # line C
print(heapq.heappop(q))                  # line D

Job defines no comparison methods. Which line raises TypeError, and why?

A

No line raises. Tuple comparison stops at the first element whenever the priorities differ, and here they always do.

B

Line D. After the root is removed, the last element is sifted down and compared against a sibling of equal priority 5, so Python falls through to comparing two Job objects.

C

Line C, because it pushes a priority already present in the heap, and heappush compares the new tuple against every element at the same priority.

D

Line B, because the new item has to travel up past a tuple whose second element is not comparable.