Experiments and implementations · Intermediate

Implementing a heap-based priority queue

Build a small job queue and verify its heap invariant, equal-priority ordering and removal behavior.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Test a heap rather than a sorted list
  2. Define equal-priority ordering
  3. Execute insertions and removals
  4. Vary inputs and check empty cases
  5. Interpret costs and missing operations
  6. Compare incremental insertion with heapify
  7. Ask Logeia about this articleCheck your understanding

Test a heap rather than a sorted list

Use Python heapq to remove the lowest numeric priority first. A heap requires parents to compare no greater than their children; it does not require the internal list to be globally sorted. Insert three labeled jobs with priorities two, one and two, then check parent-child relationships and the removal sequence. The aim is to test a data-structure contract with a small visible example, rather than copy an entire production implementation. The program uses only the longstanding min-heap API, so it does not depend on newer max-heap functions. Run it in an ordinary Python interpreter without external packages.

Define equal-priority ordering

A pair containing priority and label compares labels when priorities tie. That does not preserve submission order unless the labels happen to have the desired order. Store a priority, increasing sequence number and payload instead. The sequence resolves equal priorities and prevents comparison from reaching arbitrary non-orderable payload objects. Specify whether a smaller number means greater urgency, because a user interface may use the opposite convention. The tuple is part of the queue’s policy, not a universal property of heaps. Replacing this tuple layout changes the ordering contract even when heappush and heappop remain unchanged.

Execute insertions and removals

The program checks every parent-child relationship after each insertion. That extra assertion is intentionally linear work per insertion and should not be confused with the cost of heappush alone. Finally it removes all three jobs and asserts urgent, first, second. Checking the externally returned sequence matters more than assuming that one printed internal array represents a fully sorted collection. If an assertion fails, inspect the sequence numbers and the tuple components being compared first. The program is deterministic for these inputs; timing it is unnecessary to establish this ordering behavior. Keep validation work outside any later performance measurement.

Python 3
import heapq
jobs = [(2, "first"), (1, "urgent"), (2, "second")]
heap = []
for sequence, (priority, label) in enumerate(jobs):
    heapq.heappush(heap, (priority, sequence, label))
    assert all(heap[(i-1)//2] <= heap[i] for i in range(1, len(heap)))
result = [heapq.heappop(heap)[2] for _ in range(len(heap))]
assert result == ["urgent", "first", "second"]
print(result)

Vary inputs and check empty cases

Set all priorities equal to test submission order, then make them distinct to confirm that spelling does not determine urgency. Removing from an empty heap is a separate case that the standard API reports with an exception. Changing an item’s priority after insertion also needs an explicit update policy; mutating stored ordering state is not a general repair of the heap. Cancellation or reprioritization can use invalidation and replacement schemes, but those introduce questions about duplicate identifiers and removal of stale entries. Do not infer support for these operations merely because basic insertion and minimum removal work.

Interpret costs and missing operations

For n items, ordinary heap insertion and minimum removal have logarithmic cost, while inspecting the root is constant time. Building from an existing list with heapify is linear and should be distinguished from repeated individual insertions. A heap does not automatically provide constant-time lookup by job identifier or a sorted enumeration of every item. A real scheduler also needs policies for deadlines and starvation, not just numeric priorities. This small experiment establishes tuple ordering and the invariant under standard operations. It does not establish fairness, cancellation semantics, concurrency safety or a production service’s response-time behavior.

Compare incremental insertion with heapify

As a follow-up, put the same three tuples into a list and call heapify. Removing all items should produce the same contractually ordered result as incremental insertion. The internal lists need not look identical if both satisfy the invariant and removal ordering. Preserve the same sequence-number tie breaker in both versions. Changing payload types or tuple layout during the comparison can change which objects are compared, so save input representation and ordering policy together as reproduction conditions. This comparison checks equivalent queue behavior rather than assuming identical internal arrangement is required.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 9

Choose a learning path