Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Project: audit four priority-queue contracts

Last updated: 3 Oct 202630 min read
project
IntermediateBy AITrove Editorial

A regional dispatcher has to join two task queues, process nondecreasing route distances, and occasionally remove both the cheapest and most urgent task. These are different operation contracts. Build an exact sorted reference for each queue and compare every result after each mutation. Test pairing and binomial heaps against merged reference queues, a radix heap against nonnegative integer priorities that never fall below the last extraction, and the dual heap against the smallest and largest live task keys. Keep distinct incident IDs and explicit insertion order. A queue that gives correct output on one fixed list can still fail after a donor is reused, a degree carry is missed, or a stale opposite-heap entry is returned twice.

Acceptance trace

Give East priorities 47 and 19, West priorities 19 and 61, then meld them. Both meldable queues must leave West empty and return the four IDs by priority, preserving the two priority-19 arrivals in their global order. Insert integer priorities 47, 19, 61, and 19 into the radix queue and check the extracted numeric order. After the first priority-19 removal, reject a new priority 18. In the double-ended queue, remove minimum 19 and maximum 61, then verify that neither incident can reappear from the opposite heap.

Expected review record

Output
melded-order=[valve-19, sensor-61, pump-47, grid-83]
radix-order=[19, 19, 47, 61] late-priority-18=rejected
dual-min=valve-19 dual-max=sensor-61

Boundary and cost review

Test an empty pop, a self-meld, equal priorities from separate queues, a binomial forest with repeated carries, a radix bucket containing several distinct priorities, reuse of a removed ID, and a long run that leaves stale entries in one dual heap. Distinguish worst-case latency from amortized sequence cost. The pairing pop can scan many children, radix redistribution can move many entries at once, and dual-heap cleanup can rebuild both arrays. State which APIs expose meld, which accept only monotone integer priorities, and which support both minimum and maximum removal.

Common Mistakes

  • Do not call every heap meld a copy.
  • Do not leave duplicate binomial root degrees.
  • Do not insert below the radix queue's last extraction.
  • Do not return stale entries from the opposite heap.

Connected lessons

data structures
projects
Storage details