FA-4816 / Heap invariants / Open access

Heap arbitrary removal restores invariant · case 01

The operation returns a result or retained state that violates this contract: Remove one matching heap value if present, then restore heap ordering before draining remaining values.

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

ROOT CAUSE

Deleting a position shifts descendants without restoring the heap invariant.

VERIFIED REPAIR

Remove one matching heap value if present, then restore heap ordering before draining remaining values.

Unsuccessful approach: Value filtering removes every equal occurrence instead of exactly one.

Case contract

Remove one matching heap value if present, then restore heap ordering before draining remaining values. 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)
    if y in a: a.remove(y)
    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('removal shifts internal children', solve(['a', 'd', 'b', 'e', 'f', 'c'], 'a'), ['b', 'c', 'd', 'e', 'f'])
check('one duplicate removed', solve(['a', 'a', 'b'], 'a'), ['a', 'b'])
check('missing unchanged', solve(['c', 'a', 'b'], 'z'), ['a', 'b', 'c'])
check('empty', solve([], '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
removal shifts internal children	`['d', 'b', 'c', 'e', 'f']`	`['b', 'c', 'd', 'e', 'f']`	Failed
one duplicate removed	`['a', 'b']`	`['a', 'b']`	Passed
missing unchanged	`['a', 'b', 'c']`	`['a', 'b', 'c']`	Passed
empty	`[]`	`[]`	Passed

SHA-256 / 44523f2b140cbaafe4f274cc7fe5749e95c79852efebffb3300a75be259c4657

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=[v for v in x if v!=y]; 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('removal shifts internal children', solve(['a', 'd', 'b', 'e', 'f', 'c'], 'a'), ['b', 'c', 'd', 'e', 'f'])
check('one duplicate removed', solve(['a', 'a', 'b'], 'a'), ['a', 'b'])
check('missing unchanged', solve(['c', 'a', 'b'], 'z'), ['a', 'b', 'c'])
check('empty', solve([], '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
removal shifts internal children	`['b', 'c', 'd', 'e', 'f']`	`['b', 'c', 'd', 'e', 'f']`	Passed
one duplicate removed	`['b']`	`['a', 'b']`	Failed
missing unchanged	`['a', 'b', 'c']`	`['a', 'b', 'c']`	Passed
empty	`[]`	`[]`	Passed

SHA-256 / 0027d7f69a3807d99dc056aa14cce7b4bfe730ff7736788bf183b663da55e641

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); heapq.heapify(a)
    if y in a: a.remove(y)
    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('removal shifts internal children', solve(['a', 'd', 'b', 'e', 'f', 'c'], 'a'), ['b', 'c', 'd', 'e', 'f'])
check('one duplicate removed', solve(['a', 'a', 'b'], 'a'), ['a', 'b'])
check('missing unchanged', solve(['c', 'a', 'b'], 'z'), ['a', 'b', 'c'])
check('empty', solve([], '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
removal shifts internal children	`['b', 'c', 'd', 'e', 'f']`	`['b', 'c', 'd', 'e', 'f']`	Passed
one duplicate removed	`['a', 'b']`	`['a', 'b']`	Passed
missing unchanged	`['a', 'b', 'c']`	`['a', 'b', 'c']`	Passed
empty	`[]`	`[]`	Passed

SHA-256 / 7a0f4ead96e33975b87f2b3d385227f305b385f9028c7101b02e74aa3c0308fc

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

Case digest / d7aacb62abc117b57603d8831a7d35c2bf2f7bccf65b96f9d8a01b6f8901f1ad