internlm/Lean-Github huggingface dataset:
Theorem: Algdata.BinaryHeap.IsHeap.swap
Proof state before:
case node'.refine_2
α : Type u
lt : α → α → Bool
x : Subarray α
i✝ : Nat
j₁ j₂ : Fin (Subarray.size x)
i : Nat
hi : i < Subarray.size x
hx₁ : ∀ (x_1 : 2 * i + 1 < Subarray.size x), lt x[i] x[2 * i + 1] = false
a✝¹ : IsHeap lt x (2 * i + 1)
a✝ : IsHeap lt x (2 * i + 2)
hj₁ : ↑j₁ < i
hj₂ : ↑j₂ < i
IHl : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 1)
IHr : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 2)
hr : 2 * i + 2 < Subarray.size (Subarray.swap x j₁ j₂)
hx₂ : lt x[i] x[2 * i + 2] = false
⊢ lt (Subarray.swap x j₁ j₂)[i] (Subarray.swap x j₁ j₂)[2 * i + 2] = false
Tactic:
simp only [Subarray.getElem_swap]
Proof state after:
case node'.refine_2
α : Type u
lt : α → α → Bool
x : Subarray α
i✝ : Nat
j₁ j₂ : Fin (Subarray.size x)
i : Nat
hi : i < Subarray.size x
hx₁ : ∀ (x_1 : 2 * i + 1 < Subarray.size x), lt x[i] x[2 * i + 1] = false
a✝¹ : IsHeap lt x (2 * i + 1)
a✝ : IsHeap lt x (2 * i + 2)
hj₁ : ↑j₁ < i
hj₂ : ↑j₂ < i
IHl : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 1)
IHr : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 2)
hr : 2 * i + 2 < Subarray.size (Subarray.swap x j₁ j₂)
hx₂ : lt x[i] x[2 * i + 2] = false
⊢ lt (if ↑j₂ = i then x[↑j₁] else if ↑j₁ = i then x[↑j₂] else x[i])
      (if ↑j₂ = 2 * i + 2 then x[↑j₁] else if ↑j₁ = 2 * i + 2 then x[↑j₂] else x[2 * i + 2]) =
    false
Theorem: Algdata.BinaryHeap.IsHeap.swap
Proof state before:
case node'.refine_2.hnc.h
α : Type u
lt : α → α → Bool
x : Subarray α
i✝ : Nat
j₁ j₂ : Fin (Subarray.size x)
i : Nat
hi : i < Subarray.size x
hx₁ : ∀ (x_1 : 2 * i + 1 < Subarray.size x), lt x[i] x[2 * i + 1] = false
a✝¹ : IsHeap lt x (2 * i + 1)
a✝ : IsHeap lt x (2 * i + 2)
hj₁ : ↑j₁ < i
hj₂ : ↑j₂ < i
IHl : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 1)
IHr : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 2)
hr : 2 * i + 2 < Subarray.size (Subarray.swap x j₁ j₂)
hx₂ : lt x[i] x[2 * i + 2] = false
⊢ ↑j₂ < 2 * i + 2

case node'.refine_2.hnc.h
α : Type u
lt : α → α → Bool
x : Subarray α
i✝ : Nat
j₁ j₂ : Fin (Subarray.size x)
i : Nat
hi : i < Subarray.size x
hx₁ : ∀ (x_1 : 2 * i + 1 < Subarray.size x), lt x[i] x[2 * i + 1] = false
a✝¹ : IsHeap lt x (2 * i + 1)
a✝ : IsHeap lt x (2 * i + 2)
hj₁ : ↑j₁ < i
hj₂ : ↑j₂ < i
IHl : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 1)
IHr : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 2)
hr : 2 * i + 2 < Subarray.size (Subarray.swap x j₁ j₂)
hx₂ : lt x[i] x[2 * i + 2] = false
⊢ ↑j₁ < i

case node'.refine_2.hnc.h
α : Type u
lt : α → α → Bool
x : Subarray α
i✝ : Nat
j₁ j₂ : Fin (Subarray.size x)
i : Nat
hi : i < Subarray.size x
hx₁ : ∀ (x_1 : 2 * i + 1 < Subarray.size x), lt x[i] x[2 * i + 1] = false
a✝¹ : IsHeap lt x (2 * i + 1)
a✝ : IsHeap lt x (2 * i + 2)
hj₁ : ↑j₁ < i
hj₂ : ↑j₂ < i
IHl : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 1)
IHr : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 2)
hr : 2 * i + 2 < Subarray.size (Subarray.swap x j₁ j₂)
hx₂ : lt x[i] x[2 * i + 2] = false
⊢ ↑j₂ < i
Tactic:
. exact trans hj₂ (lt_child_right i)
Proof state after:
case node'.refine_2.hnc.h
α : Type u
lt : α → α → Bool
x : Subarray α
i✝ : Nat
j₁ j₂ : Fin (Subarray.size x)
i : Nat
hi : i < Subarray.size x
hx₁ : ∀ (x_1 : 2 * i + 1 < Subarray.size x), lt x[i] x[2 * i + 1] = false
a✝¹ : IsHeap lt x (2 * i + 1)
a✝ : IsHeap lt x (2 * i + 2)
hj₁ : ↑j₁ < i
hj₂ : ↑j₂ < i
IHl : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 1)
IHr : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 2)
hr : 2 * i + 2 < Subarray.size (Subarray.swap x j₁ j₂)
hx₂ : lt x[i] x[2 * i + 2] = false
⊢ ↑j₁ < i

case node'.refine_2.hnc.h
α : Type u
lt : α → α → Bool
x : Subarray α
i✝ : Nat
j₁ j₂ : Fin (Subarray.size x)
i : Nat
hi : i < Subarray.size x
hx₁ : ∀ (x_1 : 2 * i + 1 < Subarray.size x), lt x[i] x[2 * i + 1] = false
a✝¹ : IsHeap lt x (2 * i + 1)
a✝ : IsHeap lt x (2 * i + 2)
hj₁ : ↑j₁ < i
hj₂ : ↑j₂ < i
IHl : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 1)
IHr : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 2)
hr : 2 * i + 2 < Subarray.size (Subarray.swap x j₁ j₂)
hx₂ : lt x[i] x[2 * i + 2] = false
⊢ ↑j₂ < i
Theorem: Algdata.BinaryHeap.IsHeap.swap
Proof state before:
case node'.refine_2.hnc.h
α : Type u
lt : α → α → Bool
x : Subarray α
i✝ : Nat
j₁ j₂ : Fin (Subarray.size x)
i : Nat
hi : i < Subarray.size x
hx₁ : ∀ (x_1 : 2 * i + 1 < Subarray.size x), lt x[i] x[2 * i + 1] = false
a✝¹ : IsHeap lt x (2 * i + 1)
a✝ : IsHeap lt x (2 * i + 2)
hj₁ : ↑j₁ < i
hj₂ : ↑j₂ < i
IHl : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 1)
IHr : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 2)
hr : 2 * i + 2 < Subarray.size (Subarray.swap x j₁ j₂)
hx₂ : lt x[i] x[2 * i + 2] = false
⊢ ↑j₁ < i

case node'.refine_2.hnc.h
α : Type u
lt : α → α → Bool
x : Subarray α
i✝ : Nat
j₁ j₂ : Fin (Subarray.size x)
i : Nat
hi : i < Subarray.size x
hx₁ : ∀ (x_1 : 2 * i + 1 < Subarray.size x), lt x[i] x[2 * i + 1] = false
a✝¹ : IsHeap lt x (2 * i + 1)
a✝ : IsHeap lt x (2 * i + 2)
hj₁ : ↑j₁ < i
hj₂ : ↑j₂ < i
IHl : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 1)
IHr : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 2)
hr : 2 * i + 2 < Subarray.size (Subarray.swap x j₁ j₂)
hx₂ : lt x[i] x[2 * i + 2] = false
⊢ ↑j₂ < i
Tactic:
. exact hj₁
Proof state after:
case node'.refine_2.hnc.h
α : Type u
lt : α → α → Bool
x : Subarray α
i✝ : Nat
j₁ j₂ : Fin (Subarray.size x)
i : Nat
hi : i < Subarray.size x
hx₁ : ∀ (x_1 : 2 * i + 1 < Subarray.size x), lt x[i] x[2 * i + 1] = false
a✝¹ : IsHeap lt x (2 * i + 1)
a✝ : IsHeap lt x (2 * i + 2)
hj₁ : ↑j₁ < i
hj₂ : ↑j₂ < i
IHl : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 1)
IHr : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 2)
hr : 2 * i + 2 < Subarray.size (Subarray.swap x j₁ j₂)
hx₂ : lt x[i] x[2 * i + 2] = false
⊢ ↑j₂ < i
Theorem: Algdata.BinaryHeap.IsHeap.swap
Proof state before:
case node'.refine_2.hnc.h
α : Type u
lt : α → α → Bool
x : Subarray α
i✝ : Nat
j₁ j₂ : Fin (Subarray.size x)
i : Nat
hi : i < Subarray.size x
hx₁ : ∀ (x_1 : 2 * i + 1 < Subarray.size x), lt x[i] x[2 * i + 1] = false
a✝¹ : IsHeap lt x (2 * i + 1)
a✝ : IsHeap lt x (2 * i + 2)
hj₁ : ↑j₁ < i
hj₂ : ↑j₂ < i
IHl : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 1)
IHr : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 2)
hr : 2 * i + 2 < Subarray.size (Subarray.swap x j₁ j₂)
hx₂ : lt x[i] x[2 * i + 2] = false
⊢ ↑j₂ < i
Tactic:
. exact hj₂
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.IsHeap.swap
Proof state before:
case node'.refine_2.hnc
α : Type u
lt : α → α → Bool
x : Subarray α
i✝ : Nat
j₁ j₂ : Fin (Subarray.size x)
i : Nat
hi : i < Subarray.size x
hx₁ : ∀ (x_1 : 2 * i + 1 < Subarray.size x), lt x[i] x[2 * i + 1] = false
a✝¹ : IsHeap lt x (2 * i + 1)
a✝ : IsHeap lt x (2 * i + 2)
hj₁ : ↑j₁ < i
hj₂ : ↑j₂ < i
IHl : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 1)
IHr : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 2)
hr : 2 * i + 2 < Subarray.size (Subarray.swap x j₁ j₂)
hx₂ : lt x[i] x[2 * i + 2] = false
⊢ ¬↑j₂ = i
Tactic:
apply Nat.ne_of_lt
Proof state after:
case node'.refine_2.hnc.h
α : Type u
lt : α → α → Bool
x : Subarray α
i✝ : Nat
j₁ j₂ : Fin (Subarray.size x)
i : Nat
hi : i < Subarray.size x
hx₁ : ∀ (x_1 : 2 * i + 1 < Subarray.size x), lt x[i] x[2 * i + 1] = false
a✝¹ : IsHeap lt x (2 * i + 1)
a✝ : IsHeap lt x (2 * i + 2)
hj₁ : ↑j₁ < i
hj₂ : ↑j₂ < i
IHl : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 1)
IHr : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 2)
hr : 2 * i + 2 < Subarray.size (Subarray.swap x j₁ j₂)
hx₂ : lt x[i] x[2 * i + 2] = false
⊢ ↑j₂ < i
Theorem: Algdata.BinaryHeap.IsHeap.swap
Proof state before:
case node'.refine_2.hnc.h
α : Type u
lt : α → α → Bool
x : Subarray α
i✝ : Nat
j₁ j₂ : Fin (Subarray.size x)
i : Nat
hi : i < Subarray.size x
hx₁ : ∀ (x_1 : 2 * i + 1 < Subarray.size x), lt x[i] x[2 * i + 1] = false
a✝¹ : IsHeap lt x (2 * i + 1)
a✝ : IsHeap lt x (2 * i + 2)
hj₁ : ↑j₁ < i
hj₂ : ↑j₂ < i
IHl : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 1)
IHr : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 2)
hr : 2 * i + 2 < Subarray.size (Subarray.swap x j₁ j₂)
hx₂ : lt x[i] x[2 * i + 2] = false
⊢ ↑j₁ < 2 * i + 2
Tactic:
exact trans hj₁ (lt_child_right i)
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.IsHeap.swap
Proof state before:
case node'.refine_2.hnc.h
α : Type u
lt : α → α → Bool
x : Subarray α
i✝ : Nat
j₁ j₂ : Fin (Subarray.size x)
i : Nat
hi : i < Subarray.size x
hx₁ : ∀ (x_1 : 2 * i + 1 < Subarray.size x), lt x[i] x[2 * i + 1] = false
a✝¹ : IsHeap lt x (2 * i + 1)
a✝ : IsHeap lt x (2 * i + 2)
hj₁ : ↑j₁ < i
hj₂ : ↑j₂ < i
IHl : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 1)
IHr : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 2)
hr : 2 * i + 2 < Subarray.size (Subarray.swap x j₁ j₂)
hx₂ : lt x[i] x[2 * i + 2] = false
⊢ ↑j₂ < 2 * i + 2
Tactic:
exact trans hj₂ (lt_child_right i)
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.IsHeap.swap
Proof state before:
case node'.refine_2.hnc.h
α : Type u
lt : α → α → Bool
x : Subarray α
i✝ : Nat
j₁ j₂ : Fin (Subarray.size x)
i : Nat
hi : i < Subarray.size x
hx₁ : ∀ (x_1 : 2 * i + 1 < Subarray.size x), lt x[i] x[2 * i + 1] = false
a✝¹ : IsHeap lt x (2 * i + 1)
a✝ : IsHeap lt x (2 * i + 2)
hj₁ : ↑j₁ < i
hj₂ : ↑j₂ < i
IHl : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 1)
IHr : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 2)
hr : 2 * i + 2 < Subarray.size (Subarray.swap x j₁ j₂)
hx₂ : lt x[i] x[2 * i + 2] = false
⊢ ↑j₁ < i
Tactic:
exact hj₁
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.IsHeap.swap
Proof state before:
case node'.refine_2.hnc.h
α : Type u
lt : α → α → Bool
x : Subarray α
i✝ : Nat
j₁ j₂ : Fin (Subarray.size x)
i : Nat
hi : i < Subarray.size x
hx₁ : ∀ (x_1 : 2 * i + 1 < Subarray.size x), lt x[i] x[2 * i + 1] = false
a✝¹ : IsHeap lt x (2 * i + 1)
a✝ : IsHeap lt x (2 * i + 2)
hj₁ : ↑j₁ < i
hj₂ : ↑j₂ < i
IHl : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 1)
IHr : IsHeap lt (Subarray.swap x j₁ j₂) (2 * i + 2)
hr : 2 * i + 2 < Subarray.size (Subarray.swap x j₁ j₂)
hx₂ : lt x[i] x[2 * i + 2] = false
⊢ ↑j₂ < i
Tactic:
exact hj₂
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
i : Nat
y : Subarray α
h : heapifyDown.OpSpec lt x i y
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ lt y[i] y[2 * i + 1] = false
Tactic:
induction h with
| node_next_left x i y hi _ hr hx' hx h _ =>
  rewrite [h.get_not_descendant i (fun h => Nat.not_lt_of_le h.le (lt_child_left i))]
  have ⟨k,hk,hdk,h⟩ := h.exists_get_descendant (2*i+1) hl (.refl  _)
  rewrite [Subarray.getElem_swap_left, h, Subarray.getElem_swap]
  if hlk : 2*i+1 = k then
    simp only [if_pos hlk]; exact LawfulLTBRel.asymm hx
  else
    simp only [if_neg hlk, if_neg <| Nat.ne_of_lt <| trans (lt_child_left i) hdk.le]
    exact heap_left.not_lt_of_descendant k hdk
| node_end_left x i _ _ _ _ hx =>
  exact hx
| node_next_right x i y hi _ hr hx' hx h _ =>
  rewrite [h.get_not_descendant i (fun h => Nat.not_lt_of_le h.le (lt_child_right i))]
  rewrite [h.get_not_descendant (2*i+1) (Descendant.sibling_not' i)]
  rw [Subarray.getElem_swap_left, Subarray.getElem_swap_ne, hx']
  . show i ≠ 2*i+1; exact Nat.ne_of_lt (lt_child_left i)
  . show 2*i+1+1 ≠ 2*i+1; exact Nat.ne_of_gt .refl
| node_end_right x i hi _ hr hx' hx =>
  exact LawfulLTBRel.ntrans hx hx'
| node_odd_next x i hi _ hr hx =>
  rewrite [Subarray.getElem_swap_left, Subarray.getElem_swap_right]
  exact LawfulLTBRel.asymm hx
| node_odd_end x i _ _ _ hx =>
  exact hx
| leaf x i  hl' => exact absurd hl <| Nat.not_lt_of_le hl'
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
case node_next_left
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl✝ : 2 * i + 1 < Subarray.size x
hr : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hl :
      2 * (2 * i + 1) + 1 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ }) (2 * (2 * i + 1) + 1) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ lt y[i] y[2 * i + 1] = false
Tactic:
rewrite [h.get_not_descendant i (fun h => Nat.not_lt_of_le h.le (lt_child_left i))]
Proof state after:
case node_next_left
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl✝ : 2 * i + 1 < Subarray.size x
hr : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hl :
      2 * (2 * i + 1) + 1 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ }) (2 * (2 * i + 1) + 1) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[i] y[2 * i + 1] = false
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
case node_next_left
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl✝ : 2 * i + 1 < Subarray.size x
hr : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hl :
      2 * (2 * i + 1) + 1 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ }) (2 * (2 * i + 1) + 1) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[i] y[2 * i + 1] = false
Tactic:
have ⟨k,hk,hdk,h⟩ := h.exists_get_descendant (2*i+1) hl (.refl  _)
Proof state after:
case node_next_left
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl✝ : 2 * i + 1 < Subarray.size x
hr : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hl :
      2 * (2 * i + 1) + 1 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ }) (2 * (2 * i + 1) + 1) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
k : Nat
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hdk : Descendant (2 * i + 1) k
h : y[2 * i + 1] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[k]
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[i] y[2 * i + 1] = false
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
case node_next_left
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl✝ : 2 * i + 1 < Subarray.size x
hr : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hl :
      2 * (2 * i + 1) + 1 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ }) (2 * (2 * i + 1) + 1) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
k : Nat
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hdk : Descendant (2 * i + 1) k
h : y[2 * i + 1] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[k]
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[i] y[2 * i + 1] = false
Tactic:
rewrite [Subarray.getElem_swap_left, h, Subarray.getElem_swap]
Proof state after:
case node_next_left
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl✝ : 2 * i + 1 < Subarray.size x
hr : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hl :
      2 * (2 * i + 1) + 1 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ }) (2 * (2 * i + 1) + 1) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
k : Nat
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hdk : Descendant (2 * i + 1) k
h : y[2 * i + 1] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[k]
⊢ lt x[↑{ val := 2 * i + 1, isLt := hl✝ }]
      (if ↑{ val := 2 * i + 1, isLt := hl✝ } = k then x[↑{ val := i, isLt := hi }]
      else if ↑{ val := i, isLt := hi } = k then x[↑{ val := 2 * i + 1, isLt := hl✝ }] else x[k]) =
    false
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
case node_next_left
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl✝ : 2 * i + 1 < Subarray.size x
hr : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hl :
      2 * (2 * i + 1) + 1 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ }) (2 * (2 * i + 1) + 1) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
k : Nat
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hdk : Descendant (2 * i + 1) k
h : y[2 * i + 1] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[k]
⊢ lt x[↑{ val := 2 * i + 1, isLt := hl✝ }]
      (if ↑{ val := 2 * i + 1, isLt := hl✝ } = k then x[↑{ val := i, isLt := hi }]
      else if ↑{ val := i, isLt := hi } = k then x[↑{ val := 2 * i + 1, isLt := hl✝ }] else x[k]) =
    false
Tactic:
if hlk : 2*i+1 = k then
  simp only [if_pos hlk]; exact LawfulLTBRel.asymm hx
else
  simp only [if_neg hlk, if_neg <| Nat.ne_of_lt <| trans (lt_child_left i) hdk.le]
  exact heap_left.not_lt_of_descendant k hdk
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl✝ : 2 * i + 1 < Subarray.size x
hr : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hl :
      2 * (2 * i + 1) + 1 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ }) (2 * (2 * i + 1) + 1) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
k : Nat
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hdk : Descendant (2 * i + 1) k
h : y[2 * i + 1] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[k]
hlk : 2 * i + 1 = k
⊢ lt x[↑{ val := 2 * i + 1, isLt := hl✝ }]
      (if ↑{ val := 2 * i + 1, isLt := hl✝ } = k then x[↑{ val := i, isLt := hi }]
      else if ↑{ val := i, isLt := hi } = k then x[↑{ val := 2 * i + 1, isLt := hl✝ }] else x[k]) =
    false
Tactic:
simp only [if_pos hlk]
Proof state after:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl✝ : 2 * i + 1 < Subarray.size x
hr : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hl :
      2 * (2 * i + 1) + 1 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ }) (2 * (2 * i + 1) + 1) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
k : Nat
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hdk : Descendant (2 * i + 1) k
h : y[2 * i + 1] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[k]
hlk : 2 * i + 1 = k
⊢ lt x[2 * i + 1] x[i] = false
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl✝ : 2 * i + 1 < Subarray.size x
hr : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hl :
      2 * (2 * i + 1) + 1 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ }) (2 * (2 * i + 1) + 1) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
k : Nat
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hdk : Descendant (2 * i + 1) k
h : y[2 * i + 1] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[k]
hlk : 2 * i + 1 = k
⊢ lt x[2 * i + 1] x[i] = false
Tactic:
exact LawfulLTBRel.asymm hx
Proof state after:
no goals