Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left (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
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'
State after:
no goals

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))]
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

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  _)
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

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]
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

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
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✝ :
  ∀
    (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]
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

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
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✝ :
  ∀
    (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_neg hlk, if_neg <| Nat.ne_of_lt <| trans (lt_child_left 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] = 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[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] = 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[k] = false
Tactic:
exact heap_left.not_lt_of_descendant k hdk
State after:
no goals

State before:
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
hx : lt x[i] x[2 * i + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ lt x[i] x[2 * i + 1] = false
Tactic:
exact hx
State after:
no goals

State before:
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
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✝ :
  ∀
    (hl :
      2 * (2 * i + 2) + 1 < 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) + 1) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 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_right i))]
State after:
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
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✝ :
  ∀
    (hl :
      2 * (2 * i + 2) + 1 < 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) + 1) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 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 + 2, isLt := hr })[i] y[2 * i + 1] = false

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

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

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

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

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

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

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

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

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

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

State before:
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
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : lt x[i] x[2 * i + 2] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ lt x[i] x[2 * i + 1] = false
Tactic:
exact LawfulLTBRel.ntrans hx hx'
State after:
no goals

State before:
case node_odd_next
α : 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[i] x[2 * i + 1] = true
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]
      (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[2 * i + 1] =
    false
Tactic:
rewrite [Subarray.getElem_swap_left, Subarray.getElem_swap_right]
State after:
case node_odd_next
α : 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[i] x[2 * i + 1] = true
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ lt x[↑{ val := 2 * i + 1, isLt := hl✝ }] x[↑{ val := i, isLt := hi }] = false

State before:
case node_odd_next
α : 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[i] x[2 * i + 1] = true
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ lt x[↑{ val := 2 * i + 1, isLt := hl✝ }] x[↑{ val := i, isLt := hi }] = false
Tactic:
exact LawfulLTBRel.asymm hx
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
hx : lt x[i] x[2 * i + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ lt x[i] x[2 * i + 1] = false
Tactic:
exact hx
State after:
no goals

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