FA-4821 / Heap invariants / Open access

Heap key replacement reheapifies · case 01

The operation returns a result or retained state that violates this contract: Replace exactly one selected original list item, then heapify and drain; changing a key requires restoring heap order.

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

ROOT CAUSE

Changing a key after heapification invalidates heap order and can target a rearranged position.

VERIFIED REPAIR

Replace exactly one selected original list item, then heapify and drain; changing a key requires restoring heap order.

Unsuccessful approach: Equality-based replacement changes all equal-valued items instead of the requested original position.

Case contract

Replace exactly one selected original list item, then heapify and drain; changing a key requires restoring heap order. Inputs are the finite Python values shown by the executable fixtures; no concurrent execution is assumed.

Why this case matters

A controlled local-runtime regression for collection APIs, language semantics, or ownership wrappers. Fixtures include boundary and interaction cases.

1 / The failure

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
from collections import Counter, ChainMap, deque
import heapq
N = 1
observations = []
def solve(x, y=None):
    a=list(x); heapq.heapify(a); a[y[0]]=y[1]; return [heapq.heappop(a) for _ in range(len(a))]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('decrease nonroot', solve(['b', 'c', 'd'], [2, 'a']), ['a', 'b', 'c'])
check('duplicate one occurrence', solve(['b', 'b', 'c'], [1, 'a']), ['a', 'b', 'c'])
check('increase root', solve(['a', 'b', 'c'], [0, 'd']), ['b', 'c', 'd'])
check('singleton', solve(['b'], [0, 'a']), ['a'])
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
decrease nonroot	`['b', 'a', 'c']`	`['a', 'b', 'c']`	Failed
duplicate one occurrence	`['b', 'a', 'c']`	`['a', 'b', 'c']`	Failed
increase root	`['d', 'b', 'c']`	`['b', 'c', 'd']`	Failed
singleton	`['a']`	`['a']`	Passed

SHA-256 / 15ad263215dc3f25a89789221592fb178196ba7bf33b6e4a6378dbb879a46c27

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
from collections import Counter, ChainMap, deque
import heapq
N = 1
observations = []
def solve(x, y=None):
    a=list(x); a=[y[1] if v==x[y[0]] else v for v in a]; heapq.heapify(a); return [heapq.heappop(a) for _ in range(len(a))]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('decrease nonroot', solve(['b', 'c', 'd'], [2, 'a']), ['a', 'b', 'c'])
check('duplicate one occurrence', solve(['b', 'b', 'c'], [1, 'a']), ['a', 'b', 'c'])
check('increase root', solve(['a', 'b', 'c'], [0, 'd']), ['b', 'c', 'd'])
check('singleton', solve(['b'], [0, 'a']), ['a'])
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
decrease nonroot	`['a', 'b', 'c']`	`['a', 'b', 'c']`	Passed
duplicate one occurrence	`['a', 'a', 'c']`	`['a', 'b', 'c']`	Failed
increase root	`['b', 'c', 'd']`	`['b', 'c', 'd']`	Passed
singleton	`['a']`	`['a']`	Passed

SHA-256 / dc0127827c3af17cd9dae3729e61b1662442e8bcf018e3b4ecba34198fe55266

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json
from collections import Counter, ChainMap, deque
import heapq
N = 1
observations = []
def solve(x, y=None):
    a=list(x); a[y[0]]=y[1]; heapq.heapify(a); return [heapq.heappop(a) for _ in range(len(a))]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('decrease nonroot', solve(['b', 'c', 'd'], [2, 'a']), ['a', 'b', 'c'])
check('duplicate one occurrence', solve(['b', 'b', 'c'], [1, 'a']), ['a', 'b', 'c'])
check('increase root', solve(['a', 'b', 'c'], [0, 'd']), ['b', 'c', 'd'])
check('singleton', solve(['b'], [0, 'a']), ['a'])
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
decrease nonroot	`['a', 'b', 'c']`	`['a', 'b', 'c']`	Passed
duplicate one occurrence	`['a', 'b', 'c']`	`['a', 'b', 'c']`	Passed
increase root	`['b', 'c', 'd']`	`['b', 'c', 'd']`	Passed
singleton	`['a']`	`['a']`	Passed

SHA-256 / 31ffde4ec4fd48b0bd35eae21914674f2d8b6e3fea69f113e948667ba65bee6c

Verification & scope

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

Case digest / 541693229aa1c6465f529dd52b8463aaaa5d2fba4b4ff6f03b2dce891cb7f221