FA-4806 / Heap invariants / Open access

Heappushpop can return new smallest · case 01

The operation returns a result or retained state that violates this contract: Push then pop returns the smaller of the new value and previous heap minimum, retaining the other; empty heap returns the new value and remains empty.

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

ROOT CAUSE

Heap replacement always removes an old item even when the new item should be returned immediately.

VERIFIED REPAIR

Push then pop returns the smaller of the new value and previous heap minimum, retaining the other; empty heap returns the new value and remains empty.

Unsuccessful approach: Push alone retains an extra item and returns no removed value.

Case contract

Push then pop returns the smaller of the new value and previous heap minimum, retaining the other; empty heap returns the new value and remains empty. 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.heapreplace(a,y) if a else y; return [v,sorted(a)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('new smallest immediately returned', solve(['b', 'c'], 'a'), ['a', ['b', 'c']])
check('new largest retained', solve(['a', 'b'], 'c'), ['a', ['b', 'c']])
check('empty', solve([], 'a'), ['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
new smallest immediately returned	`['b', ['a', 'c']]`	`['a', ['b', 'c']]`	Failed
new largest retained	`['a', ['b', 'c']]`	`['a', ['b', 'c']]`	Passed
empty	`['a', []]`	`['a', []]`	Passed
equal minimum	`['a', ['a', 'b']]`	`['a', ['a', 'b']]`	Passed

SHA-256 / a61db9a5fb79e44bf187c88f2f0658767b28bed1b7ba6ba9c6e74046f7635253

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.heappush(a,y); return [None,sorted(a)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('new smallest immediately returned', solve(['b', 'c'], 'a'), ['a', ['b', 'c']])
check('new largest retained', solve(['a', 'b'], 'c'), ['a', ['b', 'c']])
check('empty', solve([], 'a'), ['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
new smallest immediately returned	`[None, ['a', 'b', 'c']]`	`['a', ['b', 'c']]`	Failed
new largest retained	`[None, ['a', 'b', 'c']]`	`['a', ['b', 'c']]`	Failed
empty	`[None, ['a']]`	`['a', []]`	Failed
equal minimum	`[None, ['a', 'a', 'b']]`	`['a', ['a', 'b']]`	Failed

SHA-256 / 4561f68cbbd243e1a9bd1a6e87835f007e67f9aa9fa685c6c904a90dc0d59131

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.heappushpop(a,y); return [v,sorted(a)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('new smallest immediately returned', solve(['b', 'c'], 'a'), ['a', ['b', 'c']])
check('new largest retained', solve(['a', 'b'], 'c'), ['a', ['b', 'c']])
check('empty', solve([], 'a'), ['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
new smallest immediately returned	`['a', ['b', 'c']]`	`['a', ['b', 'c']]`	Passed
new largest retained	`['a', ['b', 'c']]`	`['a', ['b', 'c']]`	Passed
empty	`['a', []]`	`['a', []]`	Passed
equal minimum	`['a', ['a', 'b']]`	`['a', ['a', 'b']]`	Passed

SHA-256 / 3280a90485d8ea70d11153e583e27488fda5bb9c6bd7119f60f31dd1b0a64d61

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

Case digest / f65928c307c475859daff634d933efe96ed7ec6678e77ea37050fd1c79218959