Project: audit search layouts, range roots, melds, and numeric constraints

Acceptance trace

The sorted case catalog contains 19, 29, 47, 61, 83, 103; lower bound 52 is 61 at rank three. Readings 47, 19, 19, 61, 29, 83 return a first minimum of 19 at position one for range one through four. Merging East and West dispatch heaps yields priorities one, two, three, four, four with case-ID tie order. Depot constraints of plus 47 then minus 19 imply plus 28; a plus-29 constraint is rejected. Assert the donor heap is empty after merge and the earlier depot difference survives the rejected equation.

Failure and cost review

Fuzz catalog lower bounds against bisect on sorted unique IDs, Cartesian ranges against a direct minimum with leftmost tie, heap pops against a sorted multiset, and accepted difference constraints against a small graph traversal. Inject an Eytzinger unsorted append, duplicate Cartesian readings, a self-heap-merge request, and a contradictory depot equation. Document which operations rebuild static structures, which mutate nodes, and which rejected operations leave logical contents unchanged. Inspect tree child links and null-path ranks after each heap mutation; a correct output sequence alone will miss latent pointer damage.

Common Mistakes

• Do not read the Eytzinger array as though its slots are sorted.
• Do not discard a duplicate reading before Cartesian construction.
• Do not keep two public owners of melded heap nodes.
• Do not accept a contradictory numeric offset as a new union.

Connected lessons

• Eytzinger arrays: store a search tree in breadth-first order
• Cartesian trees: preserve sequence order under a heap minimum
• Leftist heaps: keep the right spine short for meld
• Potential disjoint sets: preserve numeric differences across merges
• Projects
• Quizzes
• Data Structures