internlm/Lean-Github huggingface dataset:
Theorem: project.deleteMin_non_empty
Proof state before:
α : Type u_1
le : α → α → Bool
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
ts : List (BinTree α)
n : ℕ
btxn : BinTree α × ℕ
bt : BinTree α
ts₂ : List (BinTree α)
bt₂ : BinTree α
n₂ : ℕ
lebt : le bt₂.val bt.val = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
eqeq : t₁ = bt₂ ∧ 0 = n₂
hne₂ : True
heqh : h = t₁ ∧ hs = bt :: ts₂
dmeq :
  (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.val = y ∧
    merge le (Heap.heap (List.eraseIdx (t₁ :: bt :: ts₂) (findMin le ts₂ (1 + 1) (bt₂, n₂)).snd))
        (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.children =
      ys
ys₂ xs₃ : Heap α
ts₃ ts₄ : List (HeapNodeAux α (Heap α))
heq₂ : (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.children = Heap.heap ts₄
heq :
  (match t₁ :: bt :: ts₂, (findMin le ts₂ (1 + 1) (bt₂, n₂)).snd with
    | [], x => []
    | head :: as, 0 => as
    | a :: as, Nat.succ n => a :: List.eraseIdx as n) =
    ts₃
h₁₂ : IsMinHeap le (Heap.heap ts₃)
⊢ IsMinHeap le (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.children
Tactic:
apply children_IsMinHeap
Proof state after:
case a
α : Type u_1
le : α → α → Bool
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
ts : List (BinTree α)
n : ℕ
btxn : BinTree α × ℕ
bt : BinTree α
ts₂ : List (BinTree α)
bt₂ : BinTree α
n₂ : ℕ
lebt : le bt₂.val bt.val = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
eqeq : t₁ = bt₂ ∧ 0 = n₂
hne₂ : True
heqh : h = t₁ ∧ hs = bt :: ts₂
dmeq :
  (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.val = y ∧
    merge le (Heap.heap (List.eraseIdx (t₁ :: bt :: ts₂) (findMin le ts₂ (1 + 1) (bt₂, n₂)).snd))
        (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.children =
      ys
ys₂ xs₃ : Heap α
ts₃ ts₄ : List (HeapNodeAux α (Heap α))
heq₂ : (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.children = Heap.heap ts₄
heq :
  (match t₁ :: bt :: ts₂, (findMin le ts₂ (1 + 1) (bt₂, n₂)).snd with
    | [], x => []
    | head :: as, 0 => as
    | a :: as, Nat.succ n => a :: List.eraseIdx as n) =
    ts₃
h₁₂ : IsMinHeap le (Heap.heap ts₃)
⊢ IsMinHeap le (Heap.heap [(findMin le ts₂ (1 + 1) (bt₂, n₂)).fst])
Theorem: project.deleteMin_non_empty
Proof state before:
case a.a
α : Type u_1
le : α → α → Bool
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
ts : List (BinTree α)
n : ℕ
btxn : BinTree α × ℕ
bt : BinTree α
ts₂ : List (BinTree α)
bt₂ : BinTree α
n₂ : ℕ
lebt : le bt₂.val bt.val = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
eqeq : t₁ = bt₂ ∧ 0 = n₂
hne₂ : True
heqh : h = t₁ ∧ hs = bt :: ts₂
dmeq :
  (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.val = y ∧
    merge le (Heap.heap (List.eraseIdx (t₁ :: bt :: ts₂) (findMin le ts₂ (1 + 1) (bt₂, n₂)).snd))
        (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.children =
      ys
ys₂ xs₃ : Heap α
ts₃ ts₄ : List (HeapNodeAux α (Heap α))
heq₂ : (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.children = Heap.heap ts₄
heq :
  (match t₁ :: bt :: ts₂, (findMin le ts₂ (1 + 1) (bt₂, n₂)).snd with
    | [], x => []
    | head :: as, 0 => as
    | a :: as, Nat.succ n => a :: List.eraseIdx as n) =
    ts₃
h₁₂ : IsMinHeap le (Heap.heap ts₃)
⊢ IsMinHeap le (Heap.heap [])
Tactic:
. constructor
Proof state after:
no goals
Theorem: project.deleteMin_non_empty
Proof state before:
case a.a.a.cons
α : Type u_1
le : α → α → Bool
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
ts : List (BinTree α)
n : ℕ
btxn : BinTree α × ℕ
bt : BinTree α
ts₂ : List (BinTree α)
bt₂ : BinTree α
n₂ : ℕ
lebt : le bt₂.val bt.val = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
eqeq : t₁ = bt₂ ∧ 0 = n₂
hne₂ : True
heqh : h = t₁ ∧ hs = bt :: ts₂
dmeq :
  (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.val = y ∧
    merge le (Heap.heap (List.eraseIdx (t₁ :: bt :: ts₂) (findMin le ts₂ (1 + 1) (bt₂, n₂)).snd))
        (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.children =
      ys
ys₂ xs₃ : Heap α
ts₃ ts₄ : List (HeapNodeAux α (Heap α))
heq₂ : (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.children = Heap.heap ts₄
heq :
  (match t₁ :: bt :: ts₂, (findMin le ts₂ (1 + 1) (bt₂, n₂)).snd with
    | [], x => []
    | head :: as, 0 => as
    | a :: as, Nat.succ n => a :: List.eraseIdx as n) =
    ts₃
h₁₂ : IsMinHeap le (Heap.heap ts₃)
a✝ : IsSearchTree le h
mh : IsMinHeap le (Heap.heap (bt :: ts₂))
⊢ IsMinHeap le (Heap.heap ts₂)
Tactic:
cases mh
Proof state after:
case a.a.a.cons.cons
α : Type u_1
le : α → α → Bool
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
ts : List (BinTree α)
n : ℕ
btxn : BinTree α × ℕ
bt : BinTree α
ts₂ : List (BinTree α)
bt₂ : BinTree α
n₂ : ℕ
lebt : le bt₂.val bt.val = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
eqeq : t₁ = bt₂ ∧ 0 = n₂
hne₂ : True
heqh : h = t₁ ∧ hs = bt :: ts₂
dmeq :
  (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.val = y ∧
    merge le (Heap.heap (List.eraseIdx (t₁ :: bt :: ts₂) (findMin le ts₂ (1 + 1) (bt₂, n₂)).snd))
        (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.children =
      ys
ys₂ xs₃ : Heap α
ts₃ ts₄ : List (HeapNodeAux α (Heap α))
heq₂ : (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.children = Heap.heap ts₄
heq :
  (match t₁ :: bt :: ts₂, (findMin le ts₂ (1 + 1) (bt₂, n₂)).snd with
    | [], x => []
    | head :: as, 0 => as
    | a :: as, Nat.succ n => a :: List.eraseIdx as n) =
    ts₃
h₁₂ : IsMinHeap le (Heap.heap ts₃)
a✝² : IsSearchTree le h
a✝¹ : IsSearchTree le bt
a✝ : IsMinHeap le (Heap.heap ts₂)
⊢ IsMinHeap le (Heap.heap ts₂)
Theorem: project.deleteMin_non_empty
Proof state before:
case a.a.a.cons.cons
α : Type u_1
le : α → α → Bool
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
ts : List (BinTree α)
n : ℕ
btxn : BinTree α × ℕ
bt : BinTree α
ts₂ : List (BinTree α)
bt₂ : BinTree α
n₂ : ℕ
lebt : le bt₂.val bt.val = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
eqeq : t₁ = bt₂ ∧ 0 = n₂
hne₂ : True
heqh : h = t₁ ∧ hs = bt :: ts₂
dmeq :
  (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.val = y ∧
    merge le (Heap.heap (List.eraseIdx (t₁ :: bt :: ts₂) (findMin le ts₂ (1 + 1) (bt₂, n₂)).snd))
        (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.children =
      ys
ys₂ xs₃ : Heap α
ts₃ ts₄ : List (HeapNodeAux α (Heap α))
heq₂ : (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.children = Heap.heap ts₄
heq :
  (match t₁ :: bt :: ts₂, (findMin le ts₂ (1 + 1) (bt₂, n₂)).snd with
    | [], x => []
    | head :: as, 0 => as
    | a :: as, Nat.succ n => a :: List.eraseIdx as n) =
    ts₃
h₁₂ : IsMinHeap le (Heap.heap ts₃)
a✝² : IsSearchTree le h
a✝¹ : IsSearchTree le bt
a✝ : IsMinHeap le (Heap.heap ts₂)
⊢ IsMinHeap le (Heap.heap ts₂)
Tactic:
assumption
Proof state after:
no goals
Theorem: project.deleteMin_non_empty
Proof state before:
case h_3.h_2.inl.right.a
α : Type u_1
le : α → α → Bool
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
ts : List (BinTree α)
n : ℕ
btxn : BinTree α × ℕ
bt : BinTree α
ts₂ : List (BinTree α)
bt₂ : BinTree α
n₂ : ℕ
lebt : le bt₂.val bt.val = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
eqeq : t₁ = bt₂ ∧ 0 = n₂
hne₂ : True
heqh : h = t₁ ∧ hs = bt :: ts₂
dmeq :
  (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.val = y ∧
    merge le (Heap.heap (List.eraseIdx (t₁ :: bt :: ts₂) (findMin le ts₂ (1 + 1) (bt₂, n₂)).snd))
        (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.children =
      ys
ys₂ xs₃ : Heap α
ts₃ ts₄ : List (HeapNodeAux α (Heap α))
heq₂ : (findMin le ts₂ (1 + 1) (bt₂, n₂)).fst.children = Heap.heap ts₄
heq :
  (match t₁ :: bt :: ts₂, (findMin le ts₂ (1 + 1) (bt₂, n₂)).snd with
    | [], x => []
    | head :: as, 0 => as
    | a :: as, Nat.succ n => a :: List.eraseIdx as n) =
    ts₃
h₁₂ : IsMinHeap le (Heap.heap ts₃)
h₁₃ : IsMinHeap le (Heap.heap ts₄)
⊢ IsMinHeap le (Heap.heap ts₄)
Tactic:
assumption
Proof state after:
no goals
Theorem: project.deleteMin_non_empty
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
heqh : Heap.heap (h :: hs) = Heap.heap (t₁ :: bt :: ts)
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
⊢ IsHeap (Heap.heap ts₂)
Tactic:
rw[← heq₃]
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
heqh : Heap.heap (h :: hs) = Heap.heap (t₁ :: bt :: ts)
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
⊢ IsHeap (Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd))
Theorem: project.deleteMin_non_empty
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
heqh : Heap.heap (h :: hs) = Heap.heap (t₁ :: bt :: ts)
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
⊢ IsHeap (Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd))
Tactic:
unfold IsHeap
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
heqh : Heap.heap (h :: hs) = Heap.heap (t₁ :: bt :: ts)
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
⊢ IsHeapForest (Heap.nodes (Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd)))
Theorem: project.deleteMin_non_empty
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
heqh : Heap.heap (h :: hs) = Heap.heap (t₁ :: bt :: ts)
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
⊢ IsHeapForest (Heap.nodes (Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd)))
Tactic:
unfold IsHeapForest
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
heqh : Heap.heap (h :: hs) = Heap.heap (t₁ :: bt :: ts)
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
⊢ IsHeapForest' 0 (Heap.nodes (Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd)))
Theorem: project.deleteMin_non_empty
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
heqh : Heap.heap (h :: hs) = Heap.heap (t₁ :: bt :: ts)
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
⊢ IsHeapForest' 0 (Heap.nodes (Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd)))
Tactic:
apply IsHeapForest'_eraseIdx
Proof state after:
case a
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
heqh : Heap.heap (h :: hs) = Heap.heap (t₁ :: bt :: ts)
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
⊢ IsHeapForest' 0 (t₁ :: bt :: ts)
Theorem: project.deleteMin_non_empty
Proof state before:
case a
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
heqh : Heap.heap (h :: hs) = Heap.heap (t₁ :: bt :: ts)
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
⊢ IsHeapForest' 0 (t₁ :: bt :: ts)
Tactic:
simp at heqh
Proof state after:
case a
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
heqh : h = t₁ ∧ hs = bt :: ts
⊢ IsHeapForest' 0 (t₁ :: bt :: ts)
Theorem: project.deleteMin_non_empty
Proof state before:
case a.a
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
heqh : h = t₁ ∧ hs = bt :: ts
⊢ IsBinTree t₁

case a.a
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
heqh : h = t₁ ∧ hs = bt :: ts
⊢ IsHeapForest' t₁.rank (bt :: ts)
Tactic:
. rw[← heqh.left]
  cases h₁
  assumption
Proof state after:
case a.a
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
heqh : h = t₁ ∧ hs = bt :: ts
⊢ IsHeapForest' t₁.rank (bt :: ts)