Schedule Jobs with heapq

Select a timestamp to watch that moment on YouTube.

1. 00:00

   A support queue serves the oldest job first, but a priority queue has a different promise: serve the most urgent priority. In this lesson a smaller integer means more urgent. If test and deploy both have priority one, we also want their original arrival order to decide the tie. That gives us a clear expected sequence: test, deploy, then build at priority two. Python's heapq can efficiently push new jobs and pop the next minimum. Yet a simple tuple of priority and payload can fail when priorities tie. We will reproduce a real TypeError using dictionary payloads, inspect the tuple comparison that causes it, and add a counter that makes ties stable.

2. 00:43

   Then we will build schedule_jobs as a small, checked function. A heap is not a fully sorted list; its useful guarantee is about the smallest entry at the root. The companion lesson offers runnable examples and a task checker, so you can observe both correct ordering and wrong assumptions. Before running the broken code, predict why the second push might need to look beyond the equal priority numbers. Python has to compare something to decide which heap entry comes first. The first push succeeds because the heap has nothing else to compare. On the second push, the priority values are both one. Python compares tuple fields from left to right.

3. 01:25

   Since the first fields tie, it tries to order the second fields: two dictionaries. Dictionaries do not define a less-than ordering, so the comparison raises TypeError. Catching it here lets our demonstration continue, but catching and ignoring this error would not make a working queue. Even if the payloads were strings and the comparison succeeded, their alphabetic order might replace the arrival-order policy we wanted. The failure is therefore both a type problem and a contract problem. We need a second field that is always comparable and represents an intentional rule. An increasing insertion index does exactly that.

4. 02:05

   With entries shaped as priority, index, payload, equal priorities are resolved by index. The payload is never reached as a comparison field because two arrivals do not share the same index. This also lets payloads be dictionaries, callables, or other objects that should not decide scheduling order. Before the fix, inspect a simple tuple comparison to see the rule directly. When first fields tie at one, zero is less than one, so the earlier index sorts first. A priority of two is not less than priority one, regardless of the second field. The minimum tuple here is one, three. This is the ordering heapq uses when it compares tuple entries.

5. 02:48

   It does not know what priority means in our application; it simply relies on Python's normal ordering. By placing priority first and arrival index second, we encode the scheduling policy. The third field can be the actual task name or payload. We do not need to manually sort the whole heap each time a new job arrives. Push and pop maintain the heap invariant in logarithmic time. Printing the internal heap list, however, would not prove global ordering; elements below the root may appear in an arrangement that is valid as a heap but not sorted from left to right. To get the service sequence, repeatedly call heappop.

6. 03:28

   For a one-time small collection, sorted can be simpler, but a heap teaches a useful pattern for work that arrives dynamically. We will now apply the tuple key and verify the queue does not mutate its input list. The two priority-one jobs leave first. test precedes deploy because test had the smaller arrival index, not because its name happens to sort earlier. build leaves last at priority two. The second line shows that the caller's jobs list is unchanged; the function built its own heap rather than modifying the input. enumerate supplies a unique index for each job. A lower numeric priority wins first, and only equal priorities consult that index.

7. 04:13

   The heappop loop extracts the task name from field two, counting from zero, and returns a simple list of names. This implementation accepts integer priorities, including negative integers. If your application uses labels such as urgent and normal, map them to a consistent comparable key before pushing. Mixing a string priority with an integer priority can raise a different TypeError, and this counter does not repair invalid first fields. The counter also does not make the raw heap list sorted. It makes repeated pops deterministic. Read the tuple shape aloud before using it: priority, arrival index, task.

8. 04:53

   If a scheduling bug appears, inspect those fields in that order and compare them with the stated policy. The checks confirm the main order, a negative priority, stable ties, empty input, and dictionary payloads that used to trigger TypeError. They also confirm that submitting the payload list does not mutate it. The function was described with job names, but its ordering logic works with those unorderable dictionaries because the index resolves each tie before the payload is considered. An empty heap produces an empty result without a special exception. Keep the difference between priority and arrival in mind: priority dominates; arrival matters only when priorities tie.

9. 05:37

   The browser lesson asks you to implement the same core function. If your first attempt fails, print each heap entry as it is pushed and say which tuple field should settle a tie. Do not fix the problem by converting a dictionary to a string solely to make comparison possible; that invents a meaningless ordering. Add a deliberate comparable key. In larger systems you may also need cancellation, updated priorities, and concurrent producers. This small example is about the foundation: use heappush and heappop, encode policy in an ordered tuple, and prove the result with distinct jobs whose order you can recognize.