DSA Priority Queues

How it works

heapq orders tuple fields lexicographically. A monotonically increasing sequence number gives equal-priority tasks a deterministic arrival tie-break without comparing their dictionary payloads. The heap list itself is not fully sorted. This fixture removes every item to make the ordering visible, while a service scheduler would normally interleave insertions and removals and define policies for cancellation, changed priorities and stale entries.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as priority-queue.py and run python priority-queue.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

import heapq
from itertools import count

sequence = count()
pending = []
for priority, task in [(2, "check shed"), (1, "water gate"), (1, "water pond")]:
    heapq.heappush(pending, (priority, next(sequence), {"task": task}))
result = []
while pending:
    _, _, payload = heapq.heappop(pending)
    result.append(payload["task"])
print(result)

Expected result

['water gate', 'water pond', 'check shed']

The two urgent watering tasks retain arrival order, followed by the lower-priority inspection. The sequence field prevents a tie from requiring dictionary ordering. Dijkstra’s later heap entries use another explicit tie and stale-entry policy for their own problem.

Time, space and assumptions

Each push/pop costs O(log n) for n queued entries, with O(n) stored entries. Selecting the root alone is O(1); producing the entire ordered result costs O(n log n).