Heaps and Priority Queues

A priority queue returns the next item according to an ordering rule. A heap is one common implementation that keeps the next extreme value accessible without sorting the entire collection after every insertion. It is useful for selecting pending work, combining ordered streams, and maintaining a bounded set of leading values.

Before choosing the structure, specify what priority means, which direction comes first, and how ties behave. A queue that returns the mathematically smallest key can still violate the application’s policy if equal-priority work must remain in arrival order.

TL;DR

Quick Example

This complete Python example uses an increasing sequence number to order equal-priority dictionary payloads. Its second operation maintains the largest k numeric values in a bounded min-heap.

The exact assertions passed locally: tied jobs retained insertion order, top-three results preserved duplicate values, and zero-k and empty-input cases returned empty lists. This is an in-memory demonstration, not a concurrent scheduler, persistent queue, deadline guarantee, or performance benchmark.

Core Concepts

Heap invariant

Python 3.12 heapq implements a min-heap: parents compare no greater than their children, and the smallest element is at the root. That invariant does not fully sort the backing list. heapq interface

Tie policy

Tuple comparison can reach a payload when priorities tie. An explicit unique sequence key both avoids comparing dictionaries and defines arrival-order ties. Python documents this priority-queue pattern along with update and removal considerations. Priority queue notes

Application policy

The data structure chooses according to its comparison key. It does not decide fairness, admission, resource limits, execution, retries, or durability. Those responsibilities belong in the surrounding queue design.

Choose from the operations you actually need

For a binary heap of n entries, insertion and root removal follow a path whose height grows logarithmically; inspecting the root takes constant time. Building through heapify has a documented linear-time interface in Python. These are structural costs, not a measured latency claim for an application. Heap operations

The top-k example retains at most k values and compares each later value with the smallest retained one. Its general processing bound is O(n log k) for positive k, with O(k) retained heap storage, followed by ordering the retained results. For k=1 or tiny inputs, constants and simpler operations can dominate; measure if performance matters.

Define duplicate behavior. The example retains duplicate values as separate observations. A request for the k largest distinct values needs additional uniqueness state and has a different memory and update contract.

Handle changing priorities and cancellation

Do not mutate a key inside the heap and assume the structure repairs itself. The backing list can then violate the invariant, causing later pops to return the wrong item. Use a supported indexed update or a deliberate replacement strategy.

One strategy stores a current version for each job and inserts a new entry when its priority changes. On pop, skip entries whose version is no longer current. Cancellation can similarly mark a job inactive. This avoids searching for every old entry, but stale entries still occupy memory until removed or compacted.

Bound that overhead and define when to rebuild. A workload with many updates and few pops can accumulate far more stored entries than live jobs. Track both counts. If updates dominate, an indexed priority queue may make the operating costs easier to control.

Treat fairness separately. A continual stream of high-priority work can delay lower-priority work indefinitely. Aging, quotas, separate queues, or admission controls may be appropriate, but they change the scheduling policy. Encode and test that policy rather than assuming a heap provides it automatically.

Verify ordering before using it to schedule work

Test identical priorities with payloads that cannot be compared, empty queues, duplicate values, cancellation, and repeated updates. Use finite, well-defined keys; values such as NaN can undermine ordinary ordering assumptions.

For scheduling, distinguish a due time from permission to run. A task can be next in the heap while a concurrency limit or unavailable dependency prevents execution. A persistent job system also needs ownership, acknowledgement, retry, and recovery after a worker dies.

If several threads or processes share the queue, choose synchronization appropriate to that design. The simple heapq example does not make compound operations atomic. Check the authoritative queue state before claiming a job only once.

Adopt the heap when the required operations fit it and the measured lifecycle cost is acceptable. If the application simply sorts a small batch once, sorting may be clearer and entirely sufficient.

Best Practices

Make comparison keys explicit

Keep priority, tie breaker, and payload separate. Document which end is selected first and why.

Bound retained state

Measure live jobs, stale entries, and top-k storage independently. Include update-heavy and duplicate-heavy cases.

Test the queue policy

Verify fairness, cancellation, recovery, and concurrency outside the heap’s ordering tests when those behaviors are required.

Common Mistakes

Bad: A heap list is sorted.

Correct: Only the parent/child invariant is guaranteed; pop repeatedly or sort when a fully ordered result is needed.

Bad: Changing an entry’s priority updates the queue automatically.

Correct: Repair through a supported update or insert a versioned replacement and discard stale entries.

Bad: The heap guarantees jobs meet their deadlines.

Correct: Account for execution time, admission, concurrency, dependencies, and recovery in the scheduler.

FAQ

Why does the example need a counter?

It defines stable arrival-order ties and prevents Python from comparing dictionary payloads when priorities are equal.

Should top-k always use a heap?

No. Consider k relative to input size, whether all data is already available, and whether simplicity or measured cost favors sorting.

Can cancelled items remain in memory?

With lazy removal, yes. Bound and compact stale entries or use a structure designed for direct removal.

Related Topics

References