FA-4811 / Heap invariants / Open access

Heapreplace always evicts old minimum · case 01

The operation returns a result or retained state that violates this contract: For a nonempty heap, replace and return the old minimum even if the new value is smaller.

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

ROOT CAUSE

Push-pop can discard the new item rather than the required old minimum.

VERIFIED REPAIR

For a nonempty heap, replace and return the old minimum even if the new value is smaller.

Unsuccessful approach: Popping without inserting loses the replacement item.

Case contract

For a nonempty heap, replace and return the old minimum even if the new value is smaller. 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); v=heapq.heappushpop(a,y); return [v,sorted(a)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('smaller replacement retained', solve(['b', 'c'], 'a'), ['b', ['a', 'c']])
check('larger replacement retained', solve(['a', 'b'], 'c'), ['a', ['b', 'c']])
check('singleton replacement', solve(['b'], 'a'), ['b', ['a']])
check('equal minimum', solve(['a', 'b'], 'a'), ['a', ['a', 'b']])
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
smaller replacement retained	`['a', ['b', 'c']]`	`['b', ['a', 'c']]`	Failed
larger replacement retained	`['a', ['b', 'c']]`	`['a', ['b', 'c']]`	Passed
singleton replacement	`['a', ['b']]`	`['b', ['a']]`	Failed
equal minimum	`['a', ['a', 'b']]`	`['a', ['a', 'b']]`	Passed

SHA-256 / 6fc4bff0a0b06c4b5f087292183804711e17ce1251fa005998da0ddc9cf2cdf0

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); heapq.heapify(a); v=heapq.heappop(a); return [v,sorted(a)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('smaller replacement retained', solve(['b', 'c'], 'a'), ['b', ['a', 'c']])
check('larger replacement retained', solve(['a', 'b'], 'c'), ['a', ['b', 'c']])
check('singleton replacement', solve(['b'], 'a'), ['b', ['a']])
check('equal minimum', solve(['a', 'b'], 'a'), ['a', ['a', 'b']])
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
smaller replacement retained	`['b', ['c']]`	`['b', ['a', 'c']]`	Failed
larger replacement retained	`['a', ['b']]`	`['a', ['b', 'c']]`	Failed
singleton replacement	`['b', []]`	`['b', ['a']]`	Failed
equal minimum	`['a', ['b']]`	`['a', ['a', 'b']]`	Failed

SHA-256 / 03177d5e185cd02feebd202ccd7a2485e00e3f0993d86c2c720cae05038977cd

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); v=heapq.heapreplace(a,y); return [v,sorted(a)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('smaller replacement retained', solve(['b', 'c'], 'a'), ['b', ['a', 'c']])
check('larger replacement retained', solve(['a', 'b'], 'c'), ['a', ['b', 'c']])
check('singleton replacement', solve(['b'], 'a'), ['b', ['a']])
check('equal minimum', solve(['a', 'b'], 'a'), ['a', ['a', 'b']])
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
smaller replacement retained	`['b', ['a', 'c']]`	`['b', ['a', 'c']]`	Passed
larger replacement retained	`['a', ['b', 'c']]`	`['a', ['b', 'c']]`	Passed
singleton replacement	`['b', ['a']]`	`['b', ['a']]`	Passed
equal minimum	`['a', ['a', 'b']]`	`['a', ['a', 'b']]`	Passed

SHA-256 / 1cc99fd3c1e7bced7e81af1052063d85cdeef0d0bd049aae6b86d337b2051bf8

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

Case digest / 70e46641333da0b568ae396b173c8821ea8deeef0541d2c0920a92429a391fd5