"""Compute and draw heap repairs; Python 3.14 / matplotlib 3.10.7. Run from _media to write binary-heap-sift-operations.png there. """ from itertools import product from pathlib import Path import matplotlib matplotlib.use("Agg") import matplotlib.pyplot as plt from matplotlib.patches import Circle, Rectangle INITIAL = [2, 5, 3, 9, 7, 8, 4] INK = "#173244" UP = "#a65000" DOWN = "#007b78" def check_heap(values): """Dense indices define complete shape; check parent/child identities.""" for i, value in enumerate(values): if i: parent = (i - 1) // 2 assert i in (2 * parent + 1, 2 * parent + 2) assert values[parent] <= value left, right = 2 * i + 1, 2 * i + 2 assert right >= len(values) or left < len(values) def sift_up(values, i): path = [i] states = [values.copy()] while i: parent = (i - 1) // 2 if values[parent] <= values[i]: break values[i], values[parent] = values[parent], values[i] i = parent path.append(i) states.append(values.copy()) return path, states def sift_down(values, i): path = [i] states = [values.copy()] while 2 * i + 1 < len(values): child = 2 * i + 1 if child + 1 < len(values) and values[child + 1] < values[child]: child += 1 if values[i] <= values[child]: break values[i], values[child] = values[child], values[i] i = child path.append(i) states.append(values.copy()) return path, states def insert(values, key): values.append(key) return sift_up(values, len(values) - 1) def extract_min(values): if not values: raise ValueError("empty heap") result = values[0] last = values.pop() if not values: return result, [], [] values[0] = last path, states = sift_down(values, 0) return result, path, states def build_heap(keys): values = list(keys) for i in range(len(values) // 2 - 1, -1, -1): sift_down(values, i) check_heap(values) return values def drain(values): result = [] while values: result.append(extract_min(values)[0]) check_heap(values) return result def verify(): check_heap(INITIAL) values = INITIAL.copy() up_path, up_states = insert(values, 1) assert up_path == [7, 3, 1, 0] assert up_states == [[2, 5, 3, 9, 7, 8, 4, 1], [2, 5, 3, 1, 7, 8, 4, 9], [2, 1, 3, 5, 7, 8, 4, 9], [1, 2, 3, 5, 7, 8, 4, 9]] check_heap(values) result, down_path, down_states = extract_min(values) assert result == 1 and down_path == [0, 1, 3] assert down_states == [[9, 2, 3, 5, 7, 8, 4], [2, 9, 3, 5, 7, 8, 4], INITIAL] assert 2 * down_path[-1] + 1 >= len(values) assert values == INITIAL check_heap(values) extracted = drain(values) assert extracted == [2, 3, 4, 5, 7, 8, 9] cases = 0 # All short arrays over three keys include duplicates and partial last levels. for length in range(8): for keys in product((-1, 0, 1), repeat=length): assert drain(build_heap(keys)) == sorted(keys) heap = [] for key in keys: insert(heap, key) check_heap(heap) assert drain(heap) == sorted(keys) cases += 1 try: extract_min([]) except ValueError: pass else: raise AssertionError("empty extraction must fail") print(f"Insert path {up_path}; extract path {down_path}; returned {result}; " f"original restored; sorted extractions {extracted}; " f"{cases} exhaustive arrays checked by build and insertion") return up_states, down_states, up_path, down_path def position(i): depth = (i + 1).bit_length() - 1 offset = i - (2 ** depth - 1) return (offset + 0.5) * 8 / (2 ** depth), 3.9 - depth * 0.88 def panel(ax, values, path, title, note, color, moving_key, final=False): ax.set(xlim=(-0.25, 8.65), ylim=(-0.45, 6.05), aspect="equal") ax.axis("off") ax.text(0, 5.68, title, fontsize=14, weight="bold", color=INK) ax.text(0, 5.26, note, fontsize=11, color=color) ax.text(0, 4.91, "index", fontsize=9, color="#475569") for i, value in enumerate(values): x = 0.87 + i * 0.94 ax.add_patch(Rectangle((x - 0.4, 4.28), 0.8, 0.48, facecolor="#fff0db" if value == moving_key else "#f3f7fa", edgecolor=color if i in path else "#aab9c5")) ax.text(x, 4.51, str(value), ha="center", va="center", fontsize=12) ax.text(x, 4.91, str(i), ha="center", fontsize=9, color="#475569") for i in range(1, len(values)): x0, y0 = position((i - 1) // 2) x1, y1 = position(i) ax.plot([x0, x1], [y0, y1], color="#b4c0ca", linewidth=1.5, zorder=1) for start, end in zip(path, path[1:]): ax.annotate("", xy=position(end), xytext=position(start), arrowprops={"arrowstyle": "->", "color": color, "lw": 2.6, "shrinkA": 18, "shrinkB": 18}, zorder=2) for i, value in enumerate(values): x, y = position(i) ax.add_patch(Circle((x, y), 0.24, facecolor="#fff0db" if value == moving_key else "white", edgecolor=color if i in path else "#8497a7", linewidth=2 if i in path else 1.3, zorder=3)) ax.text(x, y, str(value), ha="center", va="center", fontsize=13, zorder=4) ax.text(x, y - 0.38, f"i={i}", ha="center", fontsize=9, color="#475569") path_label = " → ".join(str(i) for i in path) ax.text(0, 0.55, f"Key {moving_key} follows indices {path_label}", fontsize=11, color=color) if len(values) == 7: ax.text(0, 0.06, "Length 7: children of index 3 would be 7, 8 — absent.", fontsize=10, color=INK) else: ax.text(0, 0.06, "Heap order restored." if final else "Append at the next free index: 7.", fontsize=10, color=INK) def main(): up_states, down_states, up_path, down_path = verify() plt.rcParams.update({"font.family": "DejaVu Sans", "font.size": 11}) fig, axes = plt.subplots(2, 2, figsize=(12, 8.8), facecolor="white") panel(axes[0, 0], up_states[0], up_path, "1. Insert: append key 1", "Sift up: exchange with keys 9, 5, then 2", UP, 1) panel(axes[0, 1], up_states[-1], up_path, "2. Insert: repaired heap", "Key 1 is now at the root", UP, 1, final=True) panel(axes[1, 0], down_states[0], down_path, "3. Extract: save key 1; move last key 9", "Sift down: choose key 2, then key 5", DOWN, 9) panel(axes[1, 1], down_states[-1], down_path, "4. Extract: repaired heap", "Return 1; the original array is restored", DOWN, 9, final=True) fig.suptitle("Heap repair follows one chain", fontsize=18, weight="bold", y=0.98, color=INK) fig.subplots_adjust(left=0.025, right=0.985, top=0.93, bottom=0.025, wspace=0.09, hspace=0.08) fig.savefig(Path.cwd() / "binary-heap-sift-operations.png", dpi=110, facecolor="white", transparent=False) plt.close(fig) if __name__ == "__main__": main()