Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_right (Algdata/Data/BinaryHeap/Lemmas.lean)

State before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
i : Nat
y : Subarray α
h : heapifyDown.OpSpec lt x i y
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt y[i] y[2 * i + 2] = false
Tactic:
induction h <;> try exact absurd hr <| Nat.not_lt_of_le ‹_›
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✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = true
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 1] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }) (2 * i✝ + 1) y✝
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i✝ + 1) + 2 <
        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) + 2) →
      lt y✝[2 * i✝ + 1] y✝[2 * (2 * i✝ + 1) + 2] = false
hr : 2 * i✝ + 2 < Subarray.size x✝
heap_right : IsHeap lt x✝ (2 * i✝ + 2)
⊢ lt y✝[i✝] y✝[2 * i✝ + 2] = false

case node_end_left
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝¹ : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = true
a✝ : lt x✝[i✝] x✝[2 * i✝ + 1] = false
hr : 2 * i✝ + 2 < Subarray.size x✝
heap_right : IsHeap lt x✝ (2 * i✝ + 2)
⊢ lt x✝[i✝] x✝[2 * i✝ + 2] = false

case node_next_right
α : 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✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = false
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 2] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }) (2 * i✝ + 2) y✝
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i✝ + 2) + 2 <
        Subarray.size (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ })),
    IsHeap lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }) (2 * (2 * i✝ + 2) + 2) →
      lt y✝[2 * i✝ + 2] y✝[2 * (2 * i✝ + 2) + 2] = false
hr : 2 * i✝ + 2 < Subarray.size x✝
heap_right : IsHeap lt x✝ (2 * i✝ + 2)
⊢ lt y✝[i✝] y✝[2 * i✝ + 2] = false

case node_end_right
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
hr✝ : 2 * i✝ + 2 < Subarray.size x✝
a✝¹ : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = false
a✝ : lt x✝[i✝] x✝[2 * i✝ + 2] = false
hr : 2 * i✝ + 2 < Subarray.size x✝
heap_right : IsHeap lt x✝ (2 * i✝ + 2)
⊢ lt x✝[i✝] x✝[2 * i✝ + 2] = false

case leaf
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
a✝ : 2 * i✝ + 1 ≥ Subarray.size x✝
hr : 2 * i✝ + 2 < Subarray.size x✝
heap_right : IsHeap lt x✝ (2 * i✝ + 2)
⊢ lt x✝[i✝] x✝[2 * i✝ + 2] = false

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✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < 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) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt y[i] y[2 * i + 2] = false
Tactic:
case node_next_left x i y hi hl _ hx' hx h _ =>
  rewrite [h.get_not_descendant i (fun h => Nat.not_lt_of_le h.le (lt_child_left i))]
  rewrite [h.get_not_descendant (2*i+2) (Descendant.sibling_not i)]
  rw [Subarray.getElem_swap_left, Subarray.getElem_swap_ne, LawfulLTBRel.asymm hx']
  . show i ≠ 2*i+2; exact Nat.ne_of_lt (lt_child_right i)
  . show 2*i+1 ≠ 2*i+1+1; exact Nat.ne_of_lt .refl
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
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] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt x[i] x[2 * i + 2] = false
Tactic:
case node_end_left x i _ _ _ hx' hx =>
  exact LawfulLTBRel.ntrans hx <| LawfulLTBRel.asymm hx'
State after:
no goals

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] = false
hx : lt x[i] x[2 * i + 2] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * i + 2) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 2) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * (2 * i + 2) + 2) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt y[i] y[2 * i + 2] = false
Tactic:
case node_next_right x i y hi hl _ hx' hx h _ =>
  rewrite [h.get_not_descendant i (fun h => Nat.not_lt_of_le h.le (lt_child_right i))]
  have ⟨k,hk,hdk,h⟩ := h.exists_get_descendant (2*i+2) hr (.refl _)
  rewrite [Subarray.getElem_swap_left, h, Subarray.getElem_swap]
  if hrk : 2*i+2 = k then
    simp only [if_pos hrk]; exact LawfulLTBRel.asymm hx
  else
    simp only [if_neg hrk, if_neg <| Nat.ne_of_lt <| trans (lt_child_right i) hdk.le]
    exact heap_right.not_lt_of_descendant k hdk
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
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] = false
hx : lt x[i] x[2 * i + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt x[i] x[2 * i + 2] = false
Tactic:
case node_end_right x i hi _ _ hx' hx =>
  exact hx
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hl' : 2 * i + 1 ≥ Subarray.size x
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt x[i] x[2 * i + 2] = false
Tactic:
case leaf x i hl' =>
  exact absurd hr <| Nat.not_lt_of_le <| trans hl' (2*i+1).le_succ
State after:
no goals

State before:
case node_odd_end
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
a✝¹ : 2 * i✝ + 2 ≥ Subarray.size x✝
a✝ : lt x✝[i✝] x✝[2 * i✝ + 1] = false
hr : 2 * i✝ + 2 < Subarray.size x✝
heap_right : IsHeap lt x✝ (2 * i✝ + 2)
⊢ lt x✝[i✝] x✝[2 * i✝ + 2] = false
Tactic:
exact absurd hr <| Nat.not_lt_of_le ‹_›
State after:
no goals

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✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < 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) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt y[i] y[2 * i + 2] = false
Tactic:
rewrite [h.get_not_descendant i (fun h => Nat.not_lt_of_le h.le (lt_child_left i))]
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✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < 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) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[i] y[2 * i + 2] = false

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✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < 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) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[i] y[2 * i + 2] = false
Tactic:
rewrite [h.get_not_descendant (2*i+2) (Descendant.sibling_not i)]
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✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < 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) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[i]
      (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[2 * i + 2] =
    false

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✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < 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) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[i]
      (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[2 * i + 2] =
    false
Tactic:
rw [Subarray.getElem_swap_left, Subarray.getElem_swap_ne, LawfulLTBRel.asymm hx']
State after:
case hik
α : 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✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < 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) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ ↑{ val := i, isLt := hi } ≠ 2 * i + 2

case hjk
α : 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✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < 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) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ ↑{ val := 2 * i + 1, isLt := hl } ≠ 2 * i + 2

State before:
case hik
α : 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✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < 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) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ ↑{ val := i, isLt := hi } ≠ 2 * i + 2

case hjk
α : 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✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < 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) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ ↑{ val := 2 * i + 1, isLt := hl } ≠ 2 * i + 2
Tactic:
. show i ≠ 2*i+2; exact Nat.ne_of_lt (lt_child_right i)
State after:
case hjk
α : 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✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < 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) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ ↑{ val := 2 * i + 1, isLt := hl } ≠ 2 * i + 2

State before:
case hjk
α : 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✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < 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) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ ↑{ val := 2 * i + 1, isLt := hl } ≠ 2 * i + 2
Tactic:
. show 2*i+1 ≠ 2*i+1+1; exact Nat.ne_of_lt .refl
State after:
no goals

State before:
case hik
α : 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✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < 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) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ ↑{ val := i, isLt := hi } ≠ 2 * i + 2
Tactic:
show i ≠ 2*i+2
State after:
case hik
α : 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✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < 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) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ i ≠ 2 * i + 2

State before:
case hik
α : 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✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < 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) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ i ≠ 2 * i + 2
Tactic:
exact Nat.ne_of_lt (lt_child_right i)
State after:
no goals

State before:
case hjk
α : 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✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < 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) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ ↑{ val := 2 * i + 1, isLt := hl } ≠ 2 * i + 2
Tactic:
show 2*i+1 ≠ 2*i+1+1
State after:
case hjk
α : 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✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < 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) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ 2 * i + 1 ≠ 2 * i + 1 + 1

State before:
case hjk
α : 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✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < 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) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ 2 * i + 1 ≠ 2 * i + 1 + 1
Tactic:
exact Nat.ne_of_lt .refl
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
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] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt x[i] x[2 * i + 2] = false
Tactic:
exact LawfulLTBRel.ntrans hx <| LawfulLTBRel.asymm hx'
State after:
no goals

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] = false
hx : lt x[i] x[2 * i + 2] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * i + 2) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 2) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * (2 * i + 2) + 2) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt y[i] y[2 * i + 2] = false
Tactic:
rewrite [h.get_not_descendant i (fun h => Nat.not_lt_of_le h.le (lt_child_right i))]
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] = false
hx : lt x[i] x[2 * i + 2] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * i + 2) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 2) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * (2 * i + 2) + 2) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })[i] y[2 * i + 2] = false

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] = false
hx : lt x[i] x[2 * i + 2] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * i + 2) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 2) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * (2 * i + 2) + 2) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })[i] y[2 * i + 2] = false
Tactic:
have ⟨k,hk,hdk,h⟩ := h.exists_get_descendant (2*i+2) hr (.refl _)
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] = false
hx : lt x[i] x[2 * i + 2] = true
h✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * i + 2) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 2) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * (2 * i + 2) + 2) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
k : Nat
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })
hdk : Descendant (2 * i + 2) k
h : y[2 * i + 2] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })[k]
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })[i] y[2 * i + 2] = false

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] = false
hx : lt x[i] x[2 * i + 2] = true
h✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * i + 2) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 2) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * (2 * i + 2) + 2) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
k : Nat
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })
hdk : Descendant (2 * i + 2) k
h : y[2 * i + 2] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })[k]
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })[i] y[2 * i + 2] = false
Tactic:
rewrite [Subarray.getElem_swap_left, h, Subarray.getElem_swap]
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] = false
hx : lt x[i] x[2 * i + 2] = true
h✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * i + 2) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 2) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * (2 * i + 2) + 2) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
k : Nat
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })
hdk : Descendant (2 * i + 2) k
h : y[2 * i + 2] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })[k]
⊢ lt x[↑{ val := 2 * i + 2, isLt := hr✝ }]
      (if ↑{ val := 2 * i + 2, isLt := hr✝ } = k then x[↑{ val := i, isLt := hi }]
      else if ↑{ val := i, isLt := hi } = k then x[↑{ val := 2 * i + 2, isLt := hr✝ }] else x[k]) =
    false

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] = false
hx : lt x[i] x[2 * i + 2] = true
h✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * i + 2) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 2) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * (2 * i + 2) + 2) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
k : Nat
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })
hdk : Descendant (2 * i + 2) k
h : y[2 * i + 2] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })[k]
⊢ lt x[↑{ val := 2 * i + 2, isLt := hr✝ }]
      (if ↑{ val := 2 * i + 2, isLt := hr✝ } = k then x[↑{ val := i, isLt := hi }]
      else if ↑{ val := i, isLt := hi } = k then x[↑{ val := 2 * i + 2, isLt := hr✝ }] else x[k]) =
    false
Tactic:
if hrk : 2*i+2 = k then
  simp only [if_pos hrk]; exact LawfulLTBRel.asymm hx
else
  simp only [if_neg hrk, if_neg <| Nat.ne_of_lt <| trans (lt_child_right i) hdk.le]
  exact heap_right.not_lt_of_descendant k hdk
State after:
no goals

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] = false
hx : lt x[i] x[2 * i + 2] = true
h✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * i + 2) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 2) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * (2 * i + 2) + 2) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
k : Nat
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })
hdk : Descendant (2 * i + 2) k
h : y[2 * i + 2] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })[k]
hrk : 2 * i + 2 = k
⊢ lt x[↑{ val := 2 * i + 2, isLt := hr✝ }]
      (if ↑{ val := 2 * i + 2, isLt := hr✝ } = k then x[↑{ val := i, isLt := hi }]
      else if ↑{ val := i, isLt := hi } = k then x[↑{ val := 2 * i + 2, isLt := hr✝ }] else x[k]) =
    false
Tactic:
simp only [if_pos hrk]
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] = false
hx : lt x[i] x[2 * i + 2] = true
h✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * i + 2) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 2) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * (2 * i + 2) + 2) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
k : Nat
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })
hdk : Descendant (2 * i + 2) k
h : y[2 * i + 2] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })[k]
hrk : 2 * i + 2 = k
⊢ lt x[2 * i + 2] x[i] = false

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] = false
hx : lt x[i] x[2 * i + 2] = true
h✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * i + 2) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 2) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * (2 * i + 2) + 2) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
k : Nat
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })
hdk : Descendant (2 * i + 2) k
h : y[2 * i + 2] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })[k]
hrk : 2 * i + 2 = k
⊢ lt x[2 * i + 2] x[i] = false
Tactic:
exact LawfulLTBRel.asymm hx
State after:
no goals

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] = false
hx : lt x[i] x[2 * i + 2] = true
h✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * i + 2) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 2) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * (2 * i + 2) + 2) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
k : Nat
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })
hdk : Descendant (2 * i + 2) k
h : y[2 * i + 2] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })[k]
hrk : ¬2 * i + 2 = k
⊢ lt x[↑{ val := 2 * i + 2, isLt := hr✝ }]
      (if ↑{ val := 2 * i + 2, isLt := hr✝ } = k then x[↑{ val := i, isLt := hi }]
      else if ↑{ val := i, isLt := hi } = k then x[↑{ val := 2 * i + 2, isLt := hr✝ }] else x[k]) =
    false
Tactic:
simp only [if_neg hrk, if_neg <| Nat.ne_of_lt <| trans (lt_child_right i) hdk.le]
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] = false
hx : lt x[i] x[2 * i + 2] = true
h✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * i + 2) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 2) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * (2 * i + 2) + 2) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
k : Nat
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })
hdk : Descendant (2 * i + 2) k
h : y[2 * i + 2] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })[k]
hrk : ¬2 * i + 2 = k
⊢ lt x[2 * i + 2] x[k] = false

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] = false
hx : lt x[i] x[2 * i + 2] = true
h✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * i + 2) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 2) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * (2 * i + 2) + 2) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
k : Nat
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })
hdk : Descendant (2 * i + 2) k
h : y[2 * i + 2] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })[k]
hrk : ¬2 * i + 2 = k
⊢ lt x[2 * i + 2] x[k] = false
Tactic:
exact heap_right.not_lt_of_descendant k hdk
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
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] = false
hx : lt x[i] x[2 * i + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt x[i] x[2 * i + 2] = false
Tactic:
exact hx
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hl' : 2 * i + 1 ≥ Subarray.size x
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt x[i] x[2 * i + 2] = false
Tactic:
exact absurd hr <| Nat.not_lt_of_le <| trans hl' (2*i+1).le_succ
State after:
no goals