FA-40596 / Heap invariants / Open access

Complete heap leaf boundary includes the middle node in an odd-size tree · case 01

The bounded bottomup schedule certificate reports an incorrect leaves.

Verified by executionVariant 1 · 7 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

Complete heap leaf boundary includes the middle node in an odd-size tree.

VERIFIED REPAIR

Derive leaves using list(range(n//2,n)) under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses list(range((n+1)//2,n)) and still violates the stated relation.

Case contract

For building a complete zero-based binary heap of n nodes, report descending internal-node repair schedule, leaf indices, level spans as inclusive [start,end], right-child-less internal node, parent dependency edges [child,parent], and number of internal nodes. This describes the build work graph, not sorted output.

Why this case matters

This isolates an internal heap representation or priority-structure invariant using deterministic finite records.

1 / The failure

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    n=d['size']; internal=list(range(n//2-1,-1,-1)); levels=[]; start=0; width=1
    while start<n:
        levels.append([start,min(n-1,start+width-1)]); start+=width; width*=2
    return {'schedule': internal,
    'leaves': list(range(n//2+1,n)),
    'levels': levels,
    'unpaired_parent': n//2-1 if n>0 and n%2==0 else None,
    'dependencies': [[i,(i-1)//2] for i in range(1,n//2)],
    'internal_count': n//2}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 16}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 15]], 'unpaired_parent': 7, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 17}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15, 16], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 16]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 18}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 17]], 'unpaired_parent': 8, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 19}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17, 18], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 18]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 20}, {'schedule': [9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [10, 11, 12, 13, 14, 15, 16, 17, 18, 19], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 19]], 'unpaired_parent': 9, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3], [9, 4]], 'internal_count': 10})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
regression certificate 1	`{'dependencies': [], 'internal_count': 0, 'leaves': [], 'levels': [], 'schedule': [], 'unpaired_parent': None}`	`{'dependencies': [], 'internal_count': 0, 'leaves': [], 'levels': [], 'schedule': [], 'unpaired_parent': None}`	Passed
regression certificate 2	`{'dependencies': [], 'internal_count': 0, 'leaves': [], 'levels': [[0, 0]], 'schedule': [], 'unpaired_parent': None}`	`{'dependencies': [], 'internal_count': 0, 'leaves': [0], 'levels': [[0, 0]], 'schedule': [], 'unpaired_parent': None}`	Failed
regression certificate 3	`{'dependencies': [], 'internal_count': 1, 'leaves': [], 'levels': [[0, 0], [1, 1]], 'schedule': [0], 'unpaired_parent': 0}`	`{'dependencies': [], 'internal_count': 1, 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'schedule': [0], 'unpaired_parent': 0}`	Failed
regression certificate 4	`{'dependencies': [[1, 0]], 'internal_count': 2, 'leaves': [3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'schedule': [1, 0], 'unpaired_parent': None}`	`{'dependencies': [[1, 0]], 'internal_count': 2, 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'schedule': [1, 0], 'unpaired_parent': None}`	Failed
regression certificate 5	`{'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4, 'leaves': [5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'schedule': [3, 2, 1, 0], 'unpaired_parent': 3}`	`{'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4, 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'schedule': [3, 2, 1, 0], 'unpaired_parent': 3}`	Failed
regression certificate 6	`{'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7, 'leaves': [8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'schedule': [6, 5, 4, 3, 2, 1, 0], 'unpaired_parent': None}`	`{'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7, 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'schedule': [6, 5, 4, 3, 2, 1, 0], 'unpaired_parent': None}`	Failed
variant-dependent certificate	`{'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8, 'leaves': [9, 10, 11, 12, 13, 14, 15], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 15]], 'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'unpaired_parent': 7}`	`{'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8, 'leaves': [8, 9, 10, 11, 12, 13, 14, 15], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 15]], 'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'unpaired_parent': 7}`	Failed

SHA-256 / 8336c1ffeb8cbd8f1fdfd8a8e9d436803e59588be107927290c45df4775fffea

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    n=d['size']; internal=list(range(n//2-1,-1,-1)); levels=[]; start=0; width=1
    while start<n:
        levels.append([start,min(n-1,start+width-1)]); start+=width; width*=2
    return {'schedule': internal,
    'leaves': list(range((n+1)//2,n)),
    'levels': levels,
    'unpaired_parent': n//2-1 if n>0 and n%2==0 else None,
    'dependencies': [[i,(i-1)//2] for i in range(1,n//2)],
    'internal_count': n//2}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 16}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 15]], 'unpaired_parent': 7, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 17}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15, 16], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 16]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 18}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 17]], 'unpaired_parent': 8, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 19}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17, 18], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 18]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 20}, {'schedule': [9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [10, 11, 12, 13, 14, 15, 16, 17, 18, 19], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 19]], 'unpaired_parent': 9, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3], [9, 4]], 'internal_count': 10})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
regression certificate 1	`{'dependencies': [], 'internal_count': 0, 'leaves': [], 'levels': [], 'schedule': [], 'unpaired_parent': None}`	`{'dependencies': [], 'internal_count': 0, 'leaves': [], 'levels': [], 'schedule': [], 'unpaired_parent': None}`	Passed
regression certificate 2	`{'dependencies': [], 'internal_count': 0, 'leaves': [], 'levels': [[0, 0]], 'schedule': [], 'unpaired_parent': None}`	`{'dependencies': [], 'internal_count': 0, 'leaves': [0], 'levels': [[0, 0]], 'schedule': [], 'unpaired_parent': None}`	Failed
regression certificate 3	`{'dependencies': [], 'internal_count': 1, 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'schedule': [0], 'unpaired_parent': 0}`	`{'dependencies': [], 'internal_count': 1, 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'schedule': [0], 'unpaired_parent': 0}`	Passed
regression certificate 4	`{'dependencies': [[1, 0]], 'internal_count': 2, 'leaves': [3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'schedule': [1, 0], 'unpaired_parent': None}`	`{'dependencies': [[1, 0]], 'internal_count': 2, 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'schedule': [1, 0], 'unpaired_parent': None}`	Failed
regression certificate 5	`{'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4, 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'schedule': [3, 2, 1, 0], 'unpaired_parent': 3}`	`{'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4, 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'schedule': [3, 2, 1, 0], 'unpaired_parent': 3}`	Passed
regression certificate 6	`{'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7, 'leaves': [8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'schedule': [6, 5, 4, 3, 2, 1, 0], 'unpaired_parent': None}`	`{'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7, 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'schedule': [6, 5, 4, 3, 2, 1, 0], 'unpaired_parent': None}`	Failed
variant-dependent certificate	`{'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8, 'leaves': [8, 9, 10, 11, 12, 13, 14, 15], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 15]], 'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'unpaired_parent': 7}`	`{'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8, 'leaves': [8, 9, 10, 11, 12, 13, 14, 15], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 15]], 'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'unpaired_parent': 7}`	Passed

SHA-256 / 9db456534ba9176d7c96f1f791433eeb601d84cc148026b5f7c7771b835cd521

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    n=d['size']; internal=list(range(n//2-1,-1,-1)); levels=[]; start=0; width=1
    while start<n:
        levels.append([start,min(n-1,start+width-1)]); start+=width; width*=2
    return {'schedule': internal,
    'leaves': list(range(n//2,n)),
    'levels': levels,
    'unpaired_parent': n//2-1 if n>0 and n%2==0 else None,
    'dependencies': [[i,(i-1)//2] for i in range(1,n//2)],
    'internal_count': n//2}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 16}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 15]], 'unpaired_parent': 7, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 17}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15, 16], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 16]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 18}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 17]], 'unpaired_parent': 8, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 19}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17, 18], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 18]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 20}, {'schedule': [9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [10, 11, 12, 13, 14, 15, 16, 17, 18, 19], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 19]], 'unpaired_parent': 9, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3], [9, 4]], 'internal_count': 10})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
regression certificate 1	`{'dependencies': [], 'internal_count': 0, 'leaves': [], 'levels': [], 'schedule': [], 'unpaired_parent': None}`	`{'dependencies': [], 'internal_count': 0, 'leaves': [], 'levels': [], 'schedule': [], 'unpaired_parent': None}`	Passed
regression certificate 2	`{'dependencies': [], 'internal_count': 0, 'leaves': [0], 'levels': [[0, 0]], 'schedule': [], 'unpaired_parent': None}`	`{'dependencies': [], 'internal_count': 0, 'leaves': [0], 'levels': [[0, 0]], 'schedule': [], 'unpaired_parent': None}`	Passed
regression certificate 3	`{'dependencies': [], 'internal_count': 1, 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'schedule': [0], 'unpaired_parent': 0}`	`{'dependencies': [], 'internal_count': 1, 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'schedule': [0], 'unpaired_parent': 0}`	Passed
regression certificate 4	`{'dependencies': [[1, 0]], 'internal_count': 2, 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'schedule': [1, 0], 'unpaired_parent': None}`	`{'dependencies': [[1, 0]], 'internal_count': 2, 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'schedule': [1, 0], 'unpaired_parent': None}`	Passed
regression certificate 5	`{'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4, 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'schedule': [3, 2, 1, 0], 'unpaired_parent': 3}`	`{'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4, 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'schedule': [3, 2, 1, 0], 'unpaired_parent': 3}`	Passed
regression certificate 6	`{'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7, 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'schedule': [6, 5, 4, 3, 2, 1, 0], 'unpaired_parent': None}`	`{'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7, 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'schedule': [6, 5, 4, 3, 2, 1, 0], 'unpaired_parent': None}`	Passed
variant-dependent certificate	`{'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8, 'leaves': [8, 9, 10, 11, 12, 13, 14, 15], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 15]], 'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'unpaired_parent': 7}`	`{'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8, 'leaves': [8, 9, 10, 11, 12, 13, 14, 15], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 15]], 'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'unpaired_parent': 7}`	Passed

SHA-256 / d6aabcd0fdd83a6201b0bf1f41342a438c9551d278b577e22bd564a9198d092e

Verification & scope

A stipulated offline diagnostic model; it does not implement a production allocator, concurrency protocol, or complete heap library. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:43:32.620736+00:00.

Case digest / da7eab3c95c0f8433a7612251a1b37221dfa1c8150631555314030c000217bee