FAILURE MAP
← Case archive

FA-39921 / Heap invariants / Open access

Leftist orientation audit misses a unary right child · case 01

The bounded leftist ranks certificate reports an incorrect right orphans.

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

ROOT CAUSE

Every non-null right subtree has greater rank than a null left subtree, including a leaf.

VERIFIED REPAIR

Derive right orphans using [i for i,x in enumerate(a) if x[1]==-1 and x[2]!=-1] under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses [i for i,x in enumerate(a) if x[1]==-1 and x[2]!=-1 and rank(x[2])>0] and still violates the stated relation.

Case contract

A leftist-tree certificate has nodes [key,left,right,stored_npl] with missing child=-1 and valid references. Null-path length of null is -1. Report local heap-edge violations, rank recurrence violations, leftist orientation violations, leaves, unary-right nodes, and root-to-right-spine length; spine traversal stops on repeated node.

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):
    a=d['nodes']; root=d['root']
    def rank(i): return -1 if i==-1 else a[i][3]
    spine=[]; q=root
    while q!=-1 and q not in spine:
        spine.append(q); q=a[q][2]
    return {'heap_edges': [[i,j] for i,x in enumerate(a) for j in x[1:3] if j!=-1 and a[j][0]<x[0]],
    'rank_recurrence': [i for i,x in enumerate(a) if x[3]!=1+min(rank(x[1]),rank(x[2]))],
    'orientation': [i for i,x in enumerate(a) if rank(x[1])<rank(x[2])],
    'leaves': [i for i,x in enumerate(a) if x[1]==-1 and x[2]==-1],
    'right_orphans': [i for i,x in enumerate(a) if x[1]!=-1 and x[2]==-1],
    'spine_length': len(spine)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[3, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[4, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[5, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[6, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[7, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})]][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 fixtureActualExpectedOutcome
regression certificate 1{'heap_edges': [], 'leaves': [], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 0}{'heap_edges': [], 'leaves': [], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 0}Passed
regression certificate 2{'heap_edges': [], 'leaves': [0], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 1}{'heap_edges': [], 'leaves': [0], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 1}Passed
regression certificate 3{'heap_edges': [], 'leaves': [1, 2], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 2}{'heap_edges': [], 'leaves': [1, 2], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 2}Passed
regression certificate 4{'heap_edges': [], 'leaves': [1], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [0], 'spine_length': 1}{'heap_edges': [], 'leaves': [1], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 1}Failed
regression certificate 5{'heap_edges': [[0, 1]], 'leaves': [1], 'orientation': [0], 'rank_recurrence': [0], 'right_orphans': [], 'spine_length': 2}{'heap_edges': [[0, 1]], 'leaves': [1], 'orientation': [0], 'rank_recurrence': [0], 'right_orphans': [0], 'spine_length': 2}Failed
regression certificate 6{'heap_edges': [[0, 2]], 'leaves': [1, 3, 4], 'orientation': [0], 'rank_recurrence': [0], 'right_orphans': [], 'spine_length': 3}{'heap_edges': [[0, 2]], 'leaves': [1, 3, 4], 'orientation': [0], 'rank_recurrence': [0], 'right_orphans': [], 'spine_length': 3}Passed
variant-dependent certificate{'heap_edges': [[0, 2]], 'leaves': [1, 3, 4], 'orientation': [0], 'rank_recurrence': [0], 'right_orphans': [], 'spine_length': 3}{'heap_edges': [[0, 2]], 'leaves': [1, 3, 4], 'orientation': [0], 'rank_recurrence': [0], 'right_orphans': [], 'spine_length': 3}Passed

SHA-256 / a5c4b158b757de9b2ce2236e3b79df304e2d843211e34c7a918941736dbb3d95

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    a=d['nodes']; root=d['root']
    def rank(i): return -1 if i==-1 else a[i][3]
    spine=[]; q=root
    while q!=-1 and q not in spine:
        spine.append(q); q=a[q][2]
    return {'heap_edges': [[i,j] for i,x in enumerate(a) for j in x[1:3] if j!=-1 and a[j][0]<x[0]],
    'rank_recurrence': [i for i,x in enumerate(a) if x[3]!=1+min(rank(x[1]),rank(x[2]))],
    'orientation': [i for i,x in enumerate(a) if rank(x[1])<rank(x[2])],
    'leaves': [i for i,x in enumerate(a) if x[1]==-1 and x[2]==-1],
    'right_orphans': [i for i,x in enumerate(a) if x[1]==-1 and x[2]!=-1 and rank(x[2])>0],
    'spine_length': len(spine)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[3, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[4, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[5, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[6, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[7, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})]][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 fixtureActualExpectedOutcome
regression certificate 1{'heap_edges': [], 'leaves': [], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 0}{'heap_edges': [], 'leaves': [], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 0}Passed
regression certificate 2{'heap_edges': [], 'leaves': [0], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 1}{'heap_edges': [], 'leaves': [0], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 1}Passed
regression certificate 3{'heap_edges': [], 'leaves': [1, 2], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 2}{'heap_edges': [], 'leaves': [1, 2], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 2}Passed
regression certificate 4{'heap_edges': [], 'leaves': [1], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 1}{'heap_edges': [], 'leaves': [1], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 1}Passed
regression certificate 5{'heap_edges': [[0, 1]], 'leaves': [1], 'orientation': [0], 'rank_recurrence': [0], 'right_orphans': [], 'spine_length': 2}{'heap_edges': [[0, 1]], 'leaves': [1], 'orientation': [0], 'rank_recurrence': [0], 'right_orphans': [0], 'spine_length': 2}Failed
regression certificate 6{'heap_edges': [[0, 2]], 'leaves': [1, 3, 4], 'orientation': [0], 'rank_recurrence': [0], 'right_orphans': [], 'spine_length': 3}{'heap_edges': [[0, 2]], 'leaves': [1, 3, 4], 'orientation': [0], 'rank_recurrence': [0], 'right_orphans': [], 'spine_length': 3}Passed
variant-dependent certificate{'heap_edges': [[0, 2]], 'leaves': [1, 3, 4], 'orientation': [0], 'rank_recurrence': [0], 'right_orphans': [], 'spine_length': 3}{'heap_edges': [[0, 2]], 'leaves': [1, 3, 4], 'orientation': [0], 'rank_recurrence': [0], 'right_orphans': [], 'spine_length': 3}Passed

SHA-256 / 7163f9f893cdb3c537bd6ced0e393f7bf34024d66d1387a3eadcfcf30e2b7790

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    a=d['nodes']; root=d['root']
    def rank(i): return -1 if i==-1 else a[i][3]
    spine=[]; q=root
    while q!=-1 and q not in spine:
        spine.append(q); q=a[q][2]
    return {'heap_edges': [[i,j] for i,x in enumerate(a) for j in x[1:3] if j!=-1 and a[j][0]<x[0]],
    'rank_recurrence': [i for i,x in enumerate(a) if x[3]!=1+min(rank(x[1]),rank(x[2]))],
    'orientation': [i for i,x in enumerate(a) if rank(x[1])<rank(x[2])],
    'leaves': [i for i,x in enumerate(a) if x[1]==-1 and x[2]==-1],
    'right_orphans': [i for i,x in enumerate(a) if x[1]==-1 and x[2]!=-1],
    'spine_length': len(spine)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[3, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[4, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[5, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[6, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[7, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})]][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 fixtureActualExpectedOutcome
regression certificate 1{'heap_edges': [], 'leaves': [], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 0}{'heap_edges': [], 'leaves': [], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 0}Passed
regression certificate 2{'heap_edges': [], 'leaves': [0], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 1}{'heap_edges': [], 'leaves': [0], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 1}Passed
regression certificate 3{'heap_edges': [], 'leaves': [1, 2], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 2}{'heap_edges': [], 'leaves': [1, 2], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 2}Passed
regression certificate 4{'heap_edges': [], 'leaves': [1], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 1}{'heap_edges': [], 'leaves': [1], 'orientation': [], 'rank_recurrence': [], 'right_orphans': [], 'spine_length': 1}Passed
regression certificate 5{'heap_edges': [[0, 1]], 'leaves': [1], 'orientation': [0], 'rank_recurrence': [0], 'right_orphans': [0], 'spine_length': 2}{'heap_edges': [[0, 1]], 'leaves': [1], 'orientation': [0], 'rank_recurrence': [0], 'right_orphans': [0], 'spine_length': 2}Passed
regression certificate 6{'heap_edges': [[0, 2]], 'leaves': [1, 3, 4], 'orientation': [0], 'rank_recurrence': [0], 'right_orphans': [], 'spine_length': 3}{'heap_edges': [[0, 2]], 'leaves': [1, 3, 4], 'orientation': [0], 'rank_recurrence': [0], 'right_orphans': [], 'spine_length': 3}Passed
variant-dependent certificate{'heap_edges': [[0, 2]], 'leaves': [1, 3, 4], 'orientation': [0], 'rank_recurrence': [0], 'right_orphans': [], 'spine_length': 3}{'heap_edges': [[0, 2]], 'leaves': [1, 3, 4], 'orientation': [0], 'rank_recurrence': [0], 'right_orphans': [], 'spine_length': 3}Passed

SHA-256 / afb1ea1ed9648f06c0ecbcc1d8c3192066cc48d1472c5b9793221119551217c1

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:26.029444+00:00.

Case digest / 8d2e5028d89091093602b46f214234b604de557e23a549b4bf5ed2f470f95e24