Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Indexed binary min-heap: determinism and call-to-run facts

Definition
Algo_indexed_heap_Facts

by lunjia · Oct 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

algo2leanalgorithmsclrsdata-structuresrunning-timetextbook

Generated execution facts for indexed_heap.algo, including the relation between a reusable Call witness and any completed Run of the same inputs. The determinism bridge lets ordinary-output and cost corollaries reuse the constructive call theorem without repeating its algorithm analysis.

This bundle depends on the stable algorithm definition and the corresponding facts for imported components. It does not introduce a separate specification of what the program computes.

<!-- algo2lean-provenance-v0.1.4 -->

Algo2Lean provenance and reproduction. These definitions target Algo2Lean v0.1.4, using the compiler source at public commit 0f79d5e4242e6477531c9ee4410409f5b1c92f76, and Lean 4.33.1. The versioned compiler location is Algo2Lean v0.1.4. Compile all supplied .algo files and imports to reproduce the raw generated definitions. Release publication and exact website parity require their separately recorded checks; this metadata alone does not assert them. Prove2Me imports and declaration packaging are mechanically adapted, with original hashes, compiler-reported source ranges, and adaptations recorded in transplant provenance. Exact reproduction does not prove the compiler correct.

Definition code
import Definitions.Def_Algo_indexed_heap_Generated

set_option autoImplicit true
set_option backward.isDefEq.respectTransparency false
set_option backward.defeqAttrib.useBackward true


-- Generated by Algo2Lean 0.1.4 https://github.com/lunjiah/algo2lean

-- Optional proof certificate; execution remains the generated Step relation.
namespace «Algo».«indexed_heap»

open Algo2LeanCore _root_.Algo2LeanGenerated

namespace Algo2LeanGenerated

private def next_MinHeap___init__ (h : Heap) (s : State_MinHeap___init__) (stack : Stack) : Nat → Configuration
  | 1 => (Algo2LeanCore.resumeConfig h (Result.fn_MinHeap___init__ (s.t1)) stack)
  | 2 => (.active h (Frame.fn_MinHeap___init__ 1 { s with t1 := () }) stack)
  | 3 => (.active (set_MinHeap_size h (s.v0) ((0 : Int))) (Frame.fn_MinHeap___init__ 2 s) stack)
  | 4 => (.active (set_MinHeap_keys h (s.t3) (s.t2)) (Frame.fn_MinHeap___init__ 3 s) stack)
  | 5 => (.active h (Frame.fn_MinHeap___init__ 4 { s with t3 := s.v0 }) stack)
  | 6 => (.active (h.allocate (fun _ => s.t4)) (Frame.fn_MinHeap___init__ 5 { s with t2 := h.nextRef }) stack)
  | 7 => (.active h (Frame.fn_MinHeap___init__ 6 { s with t4 := (0 : Int) }) stack)
  | 8 => (.active (set_MinHeap_positions h (s.t6) (s.t5)) (Frame.fn_MinHeap___init__ 7 s) stack)
  | 9 => (.active h (Frame.fn_MinHeap___init__ 8 { s with t6 := s.v0 }) stack)
  | 10 => (.active (h.allocate (fun _ => s.t7)) (Frame.fn_MinHeap___init__ 9 { s with t5 := h.nextRef }) stack)
  | 11 => (.active h (Frame.fn_MinHeap___init__ 10 { s with t7 := (-(1 : Int)) }) stack)
  | 12 => (.active (set_MinHeap_vertices h (s.t9) (s.t8)) (Frame.fn_MinHeap___init__ 11 s) stack)
  | 13 => (.active h (Frame.fn_MinHeap___init__ 12 { s with t9 := s.v0 }) stack)
  | 14 => (.active (h.allocate (fun _ => s.t10)) (Frame.fn_MinHeap___init__ 13 { s with t8 := h.nextRef }) stack)
  | 15 => (.active h (Frame.fn_MinHeap___init__ 14 { s with t10 := (0 : Int) }) stack)
  | pc => .active h (.fn_MinHeap___init__ pc s) stack

private def next_MinHeap_swap (h : Heap) (s : State_MinHeap_swap) (stack : Stack) : Nat → Configuration
  | 1 => (Algo2LeanCore.resumeConfig h (Result.fn_MinHeap_swap (s.t5)) stack)
  | 2 => (.active h (Frame.fn_MinHeap_swap 1 { s with t5 := () }) stack)
  | 3 => (.active (h.tick "heap_swaps" 1) (Frame.fn_MinHeap_swap 2 s) stack)
  | 4 => (.active (h.write ((field_MinHeap_positions h (s.v0)).getD 0) s.v4 s.v1) (Frame.fn_MinHeap_swap 3 s) stack)
  | 5 => (.active (h.write ((field_MinHeap_positions h (s.v0)).getD 0) s.v3 s.v2) (Frame.fn_MinHeap_swap 4 s) stack)
  | 6 => (.active (h.write ((field_MinHeap_vertices h (s.v0)).getD 0) s.v2 s.v3) (Frame.fn_MinHeap_swap 5 s) stack)
  | 7 => (.active (h.write ((field_MinHeap_vertices h (s.v0)).getD 0) s.v1 s.v4) (Frame.fn_MinHeap_swap 6 s) stack)
  | 8 => (.active h (Frame.fn_MinHeap_swap 7 { s with v4 := (h.read ((field_MinHeap_vertices h (s.v0)).getD 0) s.v2) }) stack)
  | 9 => (.active h (Frame.fn_MinHeap_swap 8 { s with v3 := (h.read ((field_MinHeap_vertices h (s.v0)).getD 0) s.v1) }) stack)
  | pc => .active h (.fn_MinHeap_swap pc s) stack

private def next_MinHeap_sift_up (h : Heap) (s : State_MinHeap_sift_up) (stack : Stack) : Nat → Configuration
  | 1 => (Algo2LeanCore.resumeConfig h (Result.fn_MinHeap_sift_up (s.t3)) stack)
  | 2 => (.active h (Frame.fn_MinHeap_sift_up 1 { s with t3 := () }) stack)
  | 3 => if s.t4 then (.active h (Frame.fn_MinHeap_sift_up 16 s) stack) else (.active h (Frame.fn_MinHeap_sift_up 2 s) stack)
  | 4 => (.active h (Frame.fn_MinHeap_sift_up 3 { s with t4 := (decide ((s.v1 > (0 : Int)))) }) stack)
  | 5 => (.active h (Frame.fn_MinHeap_sift_up 4 { s with v1 := s.v2 }) stack)
  | 6 => (.active h (Frame.fn_MinHeap_swap 9 ({ v0 := (s.t6), v1 := s.t7, v2 := s.t8 } : State_MinHeap_swap)) ((fun value => match value with | .fn_MinHeap_swap result => (Frame.fn_MinHeap_sift_up 5 { s with t5 := result }) | _ => .invalid) :: stack))
  | 7 => (.active h (Frame.fn_MinHeap_sift_up 6 { s with t8 := s.v2 }) stack)
  | 8 => (.active h (Frame.fn_MinHeap_sift_up 7 { s with t7 := s.v1 }) stack)
  | 9 => (.active h (Frame.fn_MinHeap_sift_up 8 { s with t6 := s.t6 }) stack)
  | 10 => (.active h (Frame.fn_MinHeap_sift_up 9 { s with t6 := s.v0 }) stack)
  | 11 => (Algo2LeanCore.resumeConfig h (Result.fn_MinHeap_sift_up (s.t10)) stack)
  | 12 => (.active h (Frame.fn_MinHeap_sift_up 11 { s with t10 := () }) stack)
  | 13 => if s.t9 then (.active h (Frame.fn_MinHeap_sift_up 12 s) stack) else (.active h (Frame.fn_MinHeap_sift_up 10 s) stack)
  | 14 => (.active h (Frame.fn_MinHeap_sift_up 13 { s with t9 := (decide (((h.read ((field_MinHeap_keys h (s.v0)).getD 0) (h.read ((field_MinHeap_vertices h (s.v0)).getD 0) s.v2)) ≤ (h.read ((field_MinHeap_keys h (s.v0)).getD 0) (h.read ((field_MinHeap_vertices h (s.v0)).getD 0) s.v1))))) }) stack)
  | 15 => (.active (h.tick "heap_comparisons" 1) (Frame.fn_MinHeap_sift_up 14 s) stack)
  | 16 => (.active h (Frame.fn_MinHeap_sift_up 15 { s with v2 := (Int.fdiv (s.v1 - (1 : Int)) (2 : Int)) }) stack)
  | pc => .active h (.fn_MinHeap_sift_up pc s) stack

private def next_MinHeap_sift_down (h : Heap) (s : State_MinHeap_sift_down) (stack : Stack) : Nat → Configuration
  | 1 => (Algo2LeanCore.resumeConfig h (Result.fn_MinHeap_sift_down (s.t4)) stack)
  | 2 => (.active h (Frame.fn_MinHeap_sift_down 1 { s with t4 := () }) stack)
  | 3 => if s.t5 then (.active h (Frame.fn_MinHeap_sift_down 23 s) stack) else (.active h (Frame.fn_MinHeap_sift_down 2 s) stack)
  | 4 => (.active h (Frame.fn_MinHeap_sift_down 3 { s with t5 := (decide (((((2 : Int) * s.v1) + (1 : Int)) < ((field_MinHeap_size h (s.v0)).getD 0)))) }) stack)
  | 5 => (.active h (Frame.fn_MinHeap_sift_down 4 { s with v1 := s.v2 }) stack)
  | 6 => (.active h (Frame.fn_MinHeap_swap 9 ({ v0 := (s.t7), v1 := s.t8, v2 := s.t9 } : State_MinHeap_swap)) ((fun value => match value with | .fn_MinHeap_swap result => (Frame.fn_MinHeap_sift_down 5 { s with t6 := result }) | _ => .invalid) :: stack))
  | 7 => (.active h (Frame.fn_MinHeap_sift_down 6 { s with t9 := s.v2 }) stack)
  | 8 => (.active h (Frame.fn_MinHeap_sift_down 7 { s with t8 := s.v1 }) stack)
  | 9 => (.active h (Frame.fn_MinHeap_sift_down 8 { s with t7 := s.t7 }) stack)
  | 10 => (.active h (Frame.fn_MinHeap_sift_down 9 { s with t7 := s.v0 }) stack)
  | 11 => (Algo2LeanCore.resumeConfig h (Result.fn_MinHeap_sift_down (s.t11)) stack)
  | 12 => (.active h (Frame.fn_MinHeap_sift_down 11 { s with t11 := () }) stack)
  | 13 => if s.t10 then (.active h (Frame.fn_MinHeap_sift_down 12 s) stack) else (.active h (Frame.fn_MinHeap_sift_down 10 s) stack)
  | 14 => (.active h (Frame.fn_MinHeap_sift_down 13 { s with t10 := (decide (((h.read ((field_MinHeap_keys h (s.v0)).getD 0) (h.read ((field_MinHeap_vertices h (s.v0)).getD 0) s.v1)) ≤ (h.read ((field_MinHeap_keys h (s.v0)).getD 0) (h.read ((field_MinHeap_vertices h (s.v0)).getD 0) s.v2))))) }) stack)
  | 15 => (.active (h.tick "heap_comparisons" 1) (Frame.fn_MinHeap_sift_down 14 s) stack)
  | 16 => (.active h (Frame.fn_MinHeap_sift_down 15 { s with v2 := s.v3 }) stack)
  | 17 => if s.t13 then (.active h (Frame.fn_MinHeap_sift_down 16 s) stack) else (.active h (Frame.fn_MinHeap_sift_down 15 s) stack)
  | 18 => (.active h (Frame.fn_MinHeap_sift_down 17 { s with t13 := (decide (((h.read ((field_MinHeap_keys h (s.v0)).getD 0) (h.read ((field_MinHeap_vertices h (s.v0)).getD 0) s.v3)) < (h.read ((field_MinHeap_keys h (s.v0)).getD 0) (h.read ((field_MinHeap_vertices h (s.v0)).getD 0) s.v2))))) }) stack)
  | 19 => (.active (h.tick "heap_comparisons" 1) (Frame.fn_MinHeap_sift_down 18 s) stack)
  | 20 => if s.t12 then (.active h (Frame.fn_MinHeap_sift_down 19 s) stack) else (.active h (Frame.fn_MinHeap_sift_down 15 s) stack)
  | 21 => (.active h (Frame.fn_MinHeap_sift_down 20 { s with t12 := (decide ((s.v3 < ((field_MinHeap_size h (s.v0)).getD 0)))) }) stack)
  | 22 => (.active h (Frame.fn_MinHeap_sift_down 21 { s with v3 := (s.v2 + (1 : Int)) }) stack)
  | 23 => (.active h (Frame.fn_MinHeap_sift_down 22 { s with v2 := (((2 : Int) * s.v1) + (1 : Int)) }) stack)
  | pc => .active h (.fn_MinHeap_sift_down pc s) stack

private def next_MinHeap_push_or_decrease (h : Heap) (s : State_MinHeap_push_or_decrease) (stack : Stack) : Nat → Configuration
  | 1 => (Algo2LeanCore.resumeConfig h (Result.fn_MinHeap_push_or_decrease (s.t4)) stack)
  | 2 => (.active h (Frame.fn_MinHeap_push_or_decrease 1 { s with t4 := () }) stack)
  | 3 => (.active h (Frame.fn_MinHeap_sift_up 4 ({ v0 := (s.t7), v1 := s.t8 } : State_MinHeap_sift_up)) ((fun value => match value with | .fn_MinHeap_sift_up result => (Frame.fn_MinHeap_push_or_decrease 2 { s with t6 := result }) | _ => .invalid) :: stack))
  | 4 => (.active h (Frame.fn_MinHeap_push_or_decrease 3 { s with t8 := s.v3 }) stack)
  | 5 => (.active h (Frame.fn_MinHeap_push_or_decrease 4 { s with t7 := s.t7 }) stack)
  | 6 => (.active h (Frame.fn_MinHeap_push_or_decrease 5 { s with t7 := s.v0 }) stack)
  | 7 => (.active (set_MinHeap_size h (s.t9) ((s.t10 + s.t11))) (Frame.fn_MinHeap_push_or_decrease 6 s) stack)
  | 8 => (.active h (Frame.fn_MinHeap_push_or_decrease 7 { s with t11 := (1 : Int) }) stack)
  | 9 => (.active h (Frame.fn_MinHeap_push_or_decrease 8 { s with t10 := ((field_MinHeap_size h (s.t9)).getD 0) }) stack)
  | 10 => (.active h (Frame.fn_MinHeap_push_or_decrease 9 { s with t9 := s.v0 }) stack)
  | 11 => (.active (h.write ((field_MinHeap_positions h (s.v0)).getD 0) s.v1 s.v3) (Frame.fn_MinHeap_push_or_decrease 10 s) stack)
  | 12 => (.active (h.write ((field_MinHeap_vertices h (s.v0)).getD 0) s.v3 s.v1) (Frame.fn_MinHeap_push_or_decrease 11 s) stack)
  | 13 => (.active h (Frame.fn_MinHeap_push_or_decrease 12 { s with v3 := ((field_MinHeap_size h (s.v0)).getD 0) }) stack)
  | 14 => (.active (h.write ((field_MinHeap_keys h (s.v0)).getD 0) s.v1 s.v2) (Frame.fn_MinHeap_push_or_decrease 13 s) stack)
  | 15 => (.active h (Frame.fn_MinHeap_sift_up 4 ({ v0 := (s.t14), v1 := s.t15 } : State_MinHeap_sift_up)) ((fun value => match value with | .fn_MinHeap_sift_up result => (Frame.fn_MinHeap_push_or_decrease 2 { s with t13 := result }) | _ => .invalid) :: stack))
  | 16 => (.active h (Frame.fn_MinHeap_push_or_decrease 15 { s with t15 := s.v3 }) stack)
  | 17 => (.active h (Frame.fn_MinHeap_push_or_decrease 16 { s with t14 := s.t14 }) stack)
  | 18 => (.active h (Frame.fn_MinHeap_push_or_decrease 17 { s with t14 := s.v0 }) stack)
  | 19 => (.active (h.write ((field_MinHeap_keys h (s.v0)).getD 0) s.v1 s.v2) (Frame.fn_MinHeap_push_or_decrease 18 s) stack)
  | 20 => if s.t12 then (.active h (Frame.fn_MinHeap_push_or_decrease 19 s) stack) else (.active h (Frame.fn_MinHeap_push_or_decrease 2 s) stack)
  | 21 => (.active h (Frame.fn_MinHeap_push_or_decrease 20 { s with t12 := (decide ((s.v2 < (h.read ((field_MinHeap_keys h (s.v0)).getD 0) s.v1)))) }) stack)
  | 22 => (.active (h.tick "heap_comparisons" 1) (Frame.fn_MinHeap_push_or_decrease 21 s) stack)
  | 23 => if s.t5 then (.active h (Frame.fn_MinHeap_push_or_decrease 14 s) stack) else (.active h (Frame.fn_MinHeap_push_or_decrease 22 s) stack)
  | 24 => (.active h (Frame.fn_MinHeap_push_or_decrease 23 { s with t5 := (decide ((s.v3 < (0 : Int)))) }) stack)
  | 25 => (.active h (Frame.fn_MinHeap_push_or_decrease 24 { s with v3 := (h.read ((field_MinHeap_positions h (s.v0)).getD 0) s.v1) }) stack)
  | pc => .active h (.fn_MinHeap_push_or_decrease pc s) stack

private def next_MinHeap_pop_min (h : Heap) (s : State_MinHeap_pop_min) (stack : Stack) : Nat → Configuration
  | 1 => (Algo2LeanCore.resumeConfig h (Result.fn_MinHeap_pop_min (s.t3)) stack)
  | 2 => (.active h (Frame.fn_MinHeap_pop_min 1 { s with t3 := s.v1 }) stack)
  | 3 => (.active h (Frame.fn_MinHeap_sift_down 4 ({ v0 := (s.t6), v1 := s.t7 } : State_MinHeap_sift_down)) ((fun value => match value with | .fn_MinHeap_sift_down result => (Frame.fn_MinHeap_pop_min 2 { s with t5 := result }) | _ => .invalid) :: stack))
  | 4 => (.active h (Frame.fn_MinHeap_pop_min 3 { s with t7 := (0 : Int) }) stack)
  | 5 => (.active h (Frame.fn_MinHeap_pop_min 4 { s with t6 := s.t6 }) stack)
  | 6 => (.active h (Frame.fn_MinHeap_pop_min 5 { s with t6 := s.v0 }) stack)
  | 7 => if s.t4 then (.active h (Frame.fn_MinHeap_pop_min 6 s) stack) else (.active h (Frame.fn_MinHeap_pop_min 2 s) stack)
  | 8 => (.active h (Frame.fn_MinHeap_pop_min 7 { s with t4 := (decide ((s.v2 > (0 : Int)))) }) stack)
  | 9 => (.active (h.write ((field_MinHeap_positions h (s.v0)).getD 0) s.v1 (-(1 : Int))) (Frame.fn_MinHeap_pop_min 8 s) stack)
  | 10 => (.active (set_MinHeap_size h (s.v0) (s.v2)) (Frame.fn_MinHeap_pop_min 9 s) stack)
  | 11 => (.active h (Frame.fn_MinHeap_swap 9 ({ v0 := (s.t9), v1 := s.t10, v2 := s.t11 } : State_MinHeap_swap)) ((fun value => match value with | .fn_MinHeap_swap result => (Frame.fn_MinHeap_pop_min 10 { s with t8 := result }) | _ => .invalid) :: stack))
  | 12 => (.active h (Frame.fn_MinHeap_pop_min 11 { s with t11 := s.v2 }) stack)
  | 13 => (.active h (Frame.fn_MinHeap_pop_min 12 { s with t10 := (0 : Int) }) stack)
  | 14 => (.active h (Frame.fn_MinHeap_pop_min 13 { s with t9 := s.t9 }) stack)
  | 15 => (.active h (Frame.fn_MinHeap_pop_min 14 { s with t9 := s.v0 }) stack)
  | 16 => (.active h (Frame.fn_MinHeap_pop_min 15 { s with v2 := (((field_MinHeap_size h (s.v0)).getD 0) - (1 : Int)) }) stack)
  | 17 => (.active h (Frame.fn_MinHeap_pop_min 16 { s with v1 := (h.read ((field_MinHeap_vertices h (s.v0)).getD 0) (0 : Int)) }) stack)
  | 18 => (Algo2LeanCore.resumeConfig h (Result.fn_MinHeap_pop_min (s.t13)) stack)
  | 19 => (.active h (Frame.fn_MinHeap_pop_min 18 { s with t13 := (-(1 : Int)) }) stack)
  | 20 => if s.t12 then (.active h (Frame.fn_MinHeap_pop_min 19 s) stack) else (.active h (Frame.fn_MinHeap_pop_min 17 s) stack)
  | 21 => (.active h (Frame.fn_MinHeap_pop_min 20 { s with t12 := (decide ((((field_MinHeap_size h (s.v0)).getD 0) ≤ (0 : Int)))) }) stack)
  | pc => .active h (.fn_MinHeap_pop_min pc s) stack

private def next_MinHeap_is_empty (h : Heap) (s : State_MinHeap_is_empty) (stack : Stack) : Nat → Configuration
  | 1 => (Algo2LeanCore.resumeConfig h (Result.fn_MinHeap_is_empty (s.t1)) stack)
  | 2 => (.active h (Frame.fn_MinHeap_is_empty 1 { s with t1 := (decide ((((field_MinHeap_size h (s.v0)).getD 0) ≤ (0 : Int)))) }) stack)
  | pc => .active h (.fn_MinHeap_is_empty pc s) stack

private def next_MinHeap (h : Heap) (s : State_MinHeap) (stack : Stack) : Nat → Configuration
  | 1 => (Algo2LeanCore.resumeConfig h (Result.fn_MinHeap (s.t1)) stack)
  | 2 => (.active h (Frame.fn_MinHeap 1 { s with t1 := s.v0 }) stack)
  | 3 => (.active h (Frame.fn_MinHeap___init__ 15 ({ v0 := s.t3 } : State_MinHeap___init__)) ((fun value => match value with | .fn_MinHeap___init__ result => (Frame.fn_MinHeap 2 { s with t2 := result }) | _ => .invalid) :: stack))
  | 4 => (.active h (Frame.fn_MinHeap 3 { s with t3 := s.v0 }) stack)
  | 5 => (.active h (Frame.fn_MinHeap 4 { s with v0 := s.t4 }) stack)
  | 6 => (.active (h.allocateObject "indexed_heap.MinHeap") (Frame.fn_MinHeap 5 { s with t4 := h.nextObject }) stack)
  | pc => .active h (.fn_MinHeap pc s) stack

/-- A total projection used only to certify uniqueness of actual transitions. -/
def next : Configuration → Configuration
  | .done h result => .done h result
  | .active h frame stack => match frame with
    | .invalid => .active h .invalid stack
    | .fn_MinHeap___init__ pc s => next_MinHeap___init__ h s stack pc
    | .fn_MinHeap_swap pc s => next_MinHeap_swap h s stack pc
    | .fn_MinHeap_sift_up pc s => next_MinHeap_sift_up h s stack pc
    | .fn_MinHeap_sift_down pc s => next_MinHeap_sift_down h s stack pc
    | .fn_MinHeap_push_or_decrease pc s => next_MinHeap_push_or_decrease h s stack pc
    | .fn_MinHeap_pop_min pc s => next_MinHeap_pop_min h s stack pc
    | .fn_MinHeap_is_empty pc s => next_MinHeap_is_empty h s stack pc
    | .fn_MinHeap pc s => next_MinHeap h s stack pc

/-- Each generated rule agrees with the projection; guards remain in Step. -/
theorem step_next {before after : Configuration} (transition : Step before after) :
    next before = after := by
  cases transition with
  | MinHeap___init___pc1 h s stack => rfl
  | MinHeap___init___pc2 h s stack => rfl
  | MinHeap___init___pc3 h s stack defined => rfl
  | MinHeap___init___pc4 h s stack defined => rfl
  | MinHeap___init___pc5 h s stack => rfl
  | MinHeap___init___pc6 h s stack => rfl
  | MinHeap___init___pc7 h s stack => rfl
  | MinHeap___init___pc8 h s stack defined => rfl
  | MinHeap___init___pc9 h s stack => rfl
  | MinHeap___init___pc10 h s stack => rfl
  | MinHeap___init___pc11 h s stack => rfl
  | MinHeap___init___pc12 h s stack defined => rfl
  | MinHeap___init___pc13 h s stack => rfl
  | MinHeap___init___pc14 h s stack => rfl
  | MinHeap___init___pc15 h s stack => rfl
  | MinHeap_swap_pc1 h s stack => rfl
  | MinHeap_swap_pc2 h s stack => rfl
  | MinHeap_swap_pc3 h s stack => rfl
  | MinHeap_swap_pc4 h s stack defined => rfl
  | MinHeap_swap_pc5 h s stack defined => rfl
  | MinHeap_swap_pc6 h s stack defined => rfl
  | MinHeap_swap_pc7 h s stack defined => rfl
  | MinHeap_swap_pc8 h s stack defined => rfl
  | MinHeap_swap_pc9 h s stack defined => rfl
  | MinHeap_sift_up_pc1 h s stack => rfl
  | MinHeap_sift_up_pc2 h s stack => rfl
  | MinHeap_sift_up_pc3_true h s stack condition => simp [next, next_MinHeap_sift_up, condition]
  | MinHeap_sift_up_pc3_false h s stack condition => simp [next, next_MinHeap_sift_up, condition]
  | MinHeap_sift_up_pc4 h s stack => rfl
  | MinHeap_sift_up_pc5 h s stack => rfl
  | MinHeap_sift_up_pc6 h s stack => rfl
  | MinHeap_sift_up_pc7 h s stack => rfl
  | MinHeap_sift_up_pc8 h s stack => rfl
  | MinHeap_sift_up_pc9 h s stack defined => rfl
  | MinHeap_sift_up_pc10 h s stack => rfl
  | MinHeap_sift_up_pc11 h s stack => rfl
  | MinHeap_sift_up_pc12 h s stack => rfl
  | MinHeap_sift_up_pc13_true h s stack condition => simp [next, next_MinHeap_sift_up, condition]
  | MinHeap_sift_up_pc13_false h s stack condition => simp [next, next_MinHeap_sift_up, condition]
  | MinHeap_sift_up_pc14 h s stack defined => rfl
  | MinHeap_sift_up_pc15 h s stack => rfl
  | MinHeap_sift_up_pc16 h s stack defined => rfl
  | MinHeap_sift_down_pc1 h s stack => rfl
  | MinHeap_sift_down_pc2 h s stack => rfl
  | MinHeap_sift_down_pc3_true h s stack condition => simp [next, next_MinHeap_sift_down, condition]
  | MinHeap_sift_down_pc3_false h s stack condition => simp [next, next_MinHeap_sift_down, condition]
  | MinHeap_sift_down_pc4 h s stack defined => rfl
  | MinHeap_sift_down_pc5 h s stack => rfl
  | MinHeap_sift_down_pc6 h s stack => rfl
  | MinHeap_sift_down_pc7 h s stack => rfl
  | MinHeap_sift_down_pc8 h s stack => rfl
  | MinHeap_sift_down_pc9 h s stack defined => rfl
  | MinHeap_sift_down_pc10 h s stack => rfl
  | MinHeap_sift_down_pc11 h s stack => rfl
  | MinHeap_sift_down_pc12 h s stack => rfl
  | MinHeap_sift_down_pc13_true h s stack condition => simp [next, next_MinHeap_sift_down, condition]
  | MinHeap_sift_down_pc13_false h s stack condition => simp [next, next_MinHeap_sift_down, condition]
  | MinHeap_sift_down_pc14 h s stack defined => rfl
  | MinHeap_sift_down_pc15 h s stack => rfl
  | MinHeap_sift_down_pc16 h s stack => rfl
  | MinHeap_sift_down_pc17_true h s stack condition => simp [next, next_MinHeap_sift_down, condition]
  | MinHeap_sift_down_pc17_false h s stack condition => simp [next, next_MinHeap_sift_down, condition]
  | MinHeap_sift_down_pc18 h s stack defined => rfl
  | MinHeap_sift_down_pc19 h s stack => rfl
  | MinHeap_sift_down_pc20_true h s stack condition => simp [next, next_MinHeap_sift_down, condition]
  | MinHeap_sift_down_pc20_false h s stack condition => simp [next, next_MinHeap_sift_down, condition]
  | MinHeap_sift_down_pc21 h s stack defined => rfl
  | MinHeap_sift_down_pc22 h s stack => rfl
  | MinHeap_sift_down_pc23 h s stack => rfl
  | MinHeap_push_or_decrease_pc1 h s stack => rfl
  | MinHeap_push_or_decrease_pc2 h s stack => rfl
  | MinHeap_push_or_decrease_pc3 h s stack => rfl
  | MinHeap_push_or_decrease_pc4 h s stack => rfl
  | MinHeap_push_or_decrease_pc5 h s stack defined => rfl
  | MinHeap_push_or_decrease_pc6 h s stack => rfl
  | MinHeap_push_or_decrease_pc7 h s stack defined => rfl
  | MinHeap_push_or_decrease_pc8 h s stack => rfl
  | MinHeap_push_or_decrease_pc9 h s stack defined => rfl
  | MinHeap_push_or_decrease_pc10 h s stack => rfl
  | MinHeap_push_or_decrease_pc11 h s stack defined => rfl
  | MinHeap_push_or_decrease_pc12 h s stack defined => rfl
  | MinHeap_push_or_decrease_pc13 h s stack defined => rfl
  | MinHeap_push_or_decrease_pc14 h s stack defined => rfl
  | MinHeap_push_or_decrease_pc15 h s stack => rfl
  | MinHeap_push_or_decrease_pc16 h s stack => rfl
  | MinHeap_push_or_decrease_pc17 h s stack defined => rfl
  | MinHeap_push_or_decrease_pc18 h s stack => rfl
  | MinHeap_push_or_decrease_pc19 h s stack defined => rfl
  | MinHeap_push_or_decrease_pc20_true h s stack condition => simp [next, next_MinHeap_push_or_decrease, condition]
  | MinHeap_push_or_decrease_pc20_false h s stack condition => simp [next, next_MinHeap_push_or_decrease, condition]
  | MinHeap_push_or_decrease_pc21 h s stack defined => rfl
  | MinHeap_push_or_decrease_pc22 h s stack => rfl
  | MinHeap_push_or_decrease_pc23_true h s stack condition => simp [next, next_MinHeap_push_or_decrease, condition]
  | MinHeap_push_or_decrease_pc23_false h s stack condition => simp [next, next_MinHeap_push_or_decrease, condition]
  | MinHeap_push_or_decrease_pc24 h s stack => rfl
  | MinHeap_push_or_decrease_pc25 h s stack defined => rfl
  | MinHeap_pop_min_pc1 h s stack => rfl
  | MinHeap_pop_min_pc2 h s stack => rfl
  | MinHeap_pop_min_pc3 h s stack => rfl
  | MinHeap_pop_min_pc4 h s stack => rfl
  | MinHeap_pop_min_pc5 h s stack defined => rfl
  | MinHeap_pop_min_pc6 h s stack => rfl
  | MinHeap_pop_min_pc7_true h s stack condition => simp [next, next_MinHeap_pop_min, condition]
  | MinHeap_pop_min_pc7_false h s stack condition => simp [next, next_MinHeap_pop_min, condition]
  | MinHeap_pop_min_pc8 h s stack => rfl
  | MinHeap_pop_min_pc9 h s stack defined => rfl
  | MinHeap_pop_min_pc10 h s stack defined => rfl
  | MinHeap_pop_min_pc11 h s stack => rfl
  | MinHeap_pop_min_pc12 h s stack => rfl
  | MinHeap_pop_min_pc13 h s stack => rfl
  | MinHeap_pop_min_pc14 h s stack defined => rfl
  | MinHeap_pop_min_pc15 h s stack => rfl
  | MinHeap_pop_min_pc16 h s stack defined => rfl
  | MinHeap_pop_min_pc17 h s stack defined => rfl
  | MinHeap_pop_min_pc18 h s stack => rfl
  | MinHeap_pop_min_pc19 h s stack => rfl
  | MinHeap_pop_min_pc20_true h s stack condition => simp [next, next_MinHeap_pop_min, condition]
  | MinHeap_pop_min_pc20_false h s stack condition => simp [next, next_MinHeap_pop_min, condition]
  | MinHeap_pop_min_pc21 h s stack defined => rfl
  | MinHeap_is_empty_pc1 h s stack => rfl
  | MinHeap_is_empty_pc2 h s stack defined => rfl
  | MinHeap_pc1 h s stack defined => rfl
  | MinHeap_pc2 h s stack => rfl
  | MinHeap_pc3 h s stack => rfl
  | MinHeap_pc4 h s stack => rfl
  | MinHeap_pc5 h s stack => rfl
  | MinHeap_pc6 h s stack => rfl

/-- Imported determinism composes without reopening imported transition rules. -/
theorem deterministic : Deterministic Step := by
  intro before left right first second
  exact (step_next first).symm.trans (step_next second)

end Algo2LeanGenerated

end «Algo».«indexed_heap»

namespace Algo.«indexed_heap»

open Algo2LeanCore _root_.Algo2LeanGenerated Algo2LeanGenerated

theorem MinHeap.__init__.Run.eq_of_call {before after expectedHeap input output expected}
    (run : _root_.Algo.«indexed_heap».MinHeap.__init__.Run before input after output)
    (call : _root_.Algo.«indexed_heap».MinHeap.__init__.Call before input expectedHeap expected) :
    after = expectedHeap ∧ output = expected := by
  have same := Reaches.eq_of_terminal (step := Step) deterministic
    run.2 call.2.root (terminal _ _) (terminal _ _)
  cases same
  exact ⟨rfl, rfl⟩

theorem MinHeap.swap.Run.eq_of_call {before after expectedHeap input output expected}
    (run : _root_.Algo.«indexed_heap».MinHeap.swap.Run before input after output)
    (call : _root_.Algo.«indexed_heap».MinHeap.swap.Call before input expectedHeap expected) :
    after = expectedHeap ∧ output = expected := by
  have same := Reaches.eq_of_terminal (step := Step) deterministic
    run.2 call.2.root (terminal _ _) (terminal _ _)
  cases same
  exact ⟨rfl, rfl⟩

theorem MinHeap.sift_up.Run.eq_of_call {before after expectedHeap input output expected}
    (run : _root_.Algo.«indexed_heap».MinHeap.sift_up.Run before input after output)
    (call : _root_.Algo.«indexed_heap».MinHeap.sift_up.Call before input expectedHeap expected) :
    after = expectedHeap ∧ output = expected := by
  have same := Reaches.eq_of_terminal (step := Step) deterministic
    run.2 call.2.root (terminal _ _) (terminal _ _)
  cases same
  exact ⟨rfl, rfl⟩

theorem MinHeap.sift_down.Run.eq_of_call {before after expectedHeap input output expected}
    (run : _root_.Algo.«indexed_heap».MinHeap.sift_down.Run before input after output)
    (call : _root_.Algo.«indexed_heap».MinHeap.sift_down.Call before input expectedHeap expected) :
    after = expectedHeap ∧ output = expected := by
  have same := Reaches.eq_of_terminal (step := Step) deterministic
    run.2 call.2.root (terminal _ _) (terminal _ _)
  cases same
  exact ⟨rfl, rfl⟩

theorem MinHeap.push_or_decrease.Run.eq_of_call {before after expectedHeap input output expected}
    (run : _root_.Algo.«indexed_heap».MinHeap.push_or_decrease.Run before input after output)
    (call : _root_.Algo.«indexed_heap».MinHeap.push_or_decrease.Call before input expectedHeap expected) :
    after = expectedHeap ∧ output = expected := by
  have same := Reaches.eq_of_terminal (step := Step) deterministic
    run.2 call.2.root (terminal _ _) (terminal _ _)
  cases same
  exact ⟨rfl, rfl⟩

theorem MinHeap.pop_min.Run.eq_of_call {before after expectedHeap input output expected}
    (run : _root_.Algo.«indexed_heap».MinHeap.pop_min.Run before input after output)
    (call : _root_.Algo.«indexed_heap».MinHeap.pop_min.Call before input expectedHeap expected) :
    after = expectedHeap ∧ output = expected := by
  have same := Reaches.eq_of_terminal (step := Step) deterministic
    run.2 call.2.root (terminal _ _) (terminal _ _)
  cases same
  exact ⟨rfl, rfl⟩

theorem MinHeap.is_empty.Run.eq_of_call {before after expectedHeap input output expected}
    (run : _root_.Algo.«indexed_heap».MinHeap.is_empty.Run before input after output)
    (call : _root_.Algo.«indexed_heap».MinHeap.is_empty.Call before input expectedHeap expected) :
    after = expectedHeap ∧ output = expected := by
  have same := Reaches.eq_of_terminal (step := Step) deterministic
    run.2 call.2.root (terminal _ _) (terminal _ _)
  cases same
  exact ⟨rfl, rfl⟩

theorem MinHeap.Run.eq_of_call {before after expectedHeap input output expected}
    (run : _root_.Algo.«indexed_heap».MinHeap.Run before input after output)
    (call : _root_.Algo.«indexed_heap».MinHeap.Call before input expectedHeap expected) :
    after = expectedHeap ∧ output = expected := by
  have same := Reaches.eq_of_terminal (step := Step) deterministic
    run.2 call.2.root (terminal _ _) (terminal _ _)
  cases same
  exact ⟨rfl, rfl⟩

end Algo.«indexed_heap»
Source
https://github.com/lunjiah/algo2lean/blob/0f79d5e4242e6477531c9ee4410409f5b1c92f76/examples/kruskal/indexed_heap.algo

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me