Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.exists_get_descendant (Algdata/Data/BinaryHeap/Basic.lean)

State before:
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y : Subarray α
h : heapifyDown.OpSpec lt x i y
k : Nat
hk : k < Subarray.size x
hdesc : Descendant i k
⊢ ∃ l hl, Descendant i l ∧ y[k] = x[l]
Tactic:
induction h <;> try exact ⟨k,hk,hdesc,rfl⟩
State after:
case node_next_left
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y : Subarray α
k : Nat
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✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ })),
    Descendant (2 * i✝ + 1) k →
      ∃ l hl,
        Descendant (2 * i✝ + 1) l ∧
          y✝[k] = (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ })[l]
hk : k < Subarray.size x✝
hdesc : Descendant i✝ k
⊢ ∃ l hl, Descendant i✝ l ∧ y✝[k] = x✝[l]

case node_next_right
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y : Subarray α
k : Nat
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✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ })),
    Descendant (2 * i✝ + 2) k →
      ∃ l hl,
        Descendant (2 * i✝ + 2) l ∧
          y✝[k] = (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ })[l]
hk : k < Subarray.size x✝
hdesc : Descendant i✝ k
⊢ ∃ l hl, Descendant i✝ l ∧ y✝[k] = x✝[l]

case node_odd_next
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y : Subarray α
k : Nat
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] = true
hk : k < Subarray.size x✝
hdesc : Descendant i✝ k
⊢ ∃ l hl, Descendant i✝ l ∧ (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ })[k] = x✝[l]

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    Descendant (2 * i + 1) k →
      ∃ l hl_1,
        Descendant (2 * i + 1) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
⊢ ∃ l hl_1, Descendant i l ∧ y[k] = x[l]
Tactic:
case node_next_left x i y hi hl hr hx' hx h IH =>
  if hdesc' : Descendant (2*i+1) k then
    have ⟨l,hl,hld,IH⟩ := @IH hk hdesc'
    simp only [IH, Subarray.getElem_swap]
    if hll : 2*i+1 = l then
      cases hll; simp only [ite_true]
      exact ⟨i, hi, .refl i, rfl⟩
    else
      rewrite [if_neg hll, if_neg <| Nat.ne_of_lt <| trans (lt_child_left i) hld.le]
      exact ⟨l, hl, .trans (.child_left i) hld, rfl⟩
  else
    simp only [h.get_not_descendant k hdesc', Subarray.getElem_swap]
    rewrite [if_neg (c:=2*i+1=k) fun h => by cases h; exact hdesc' (.refl _)]
    if hik : i = k then
      cases hik; simp only [ite_true]
      exact ⟨2*k+1, hl, .child_left k, rfl⟩
    else
      simp only [if_neg hik]
      exact ⟨k, hk, hdesc, rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
⊢ ∃ l hl_1, Descendant i l ∧ y[k] = x[l]
Tactic:
case node_next_right x i y hi hl hr hx' hx h IH =>
  if hdesc' : Descendant (2*i+2) k then
    have ⟨l,hl,hld,IH⟩ := @IH hk hdesc'
    simp only [IH, Subarray.getElem_swap]
    if hrl : 2*i+2 = l then
      cases hrl; simp only [ite_true]
      exact ⟨i, hi, .refl i, rfl⟩
    else
      rewrite [if_neg hrl, if_neg <| Nat.ne_of_lt <| trans (lt_child_right i) hld.le]
      exact ⟨l, hl, .trans (.child_right i) hld, rfl⟩
  else
    simp only [h.get_not_descendant k hdesc', Subarray.getElem_swap]
    rewrite [if_neg (c:=2*i+2=k) fun h => by cases h; exact hdesc' (.refl _)]
    if hik : i = k then
      cases hik; simp only [ite_true]
      exact ⟨2*k+2, hr, .child_right k, rfl⟩
    else
      simp only [if_neg hik]
      exact ⟨k, hk, hdesc, rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
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
hk : k < Subarray.size x
hdesc : Descendant i k
⊢ ∃ l hl_1, Descendant i l ∧ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[k] = x[l]
Tactic:
case node_odd_next x i hi hl hr hx =>
  simp only [Subarray.getElem_swap]
  if hlk : 2*i+1 = k then
    cases hlk; simp only [ite_true]
    exact ⟨i, hi, .refl i, rfl⟩
  else if hik : i = k then
    cases hik; simp only [if_neg hlk, ite_true]
    exact ⟨2*k+1, hl, .child_left k, rfl⟩
  else
    simp only [if_neg hlk, if_neg hik]
    exact ⟨k, hk, hdesc, rfl⟩
State after:
no goals

State before:
case leaf
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y : Subarray α
k : Nat
x✝ : Subarray α
i✝ : Nat
a✝ : 2 * i✝ + 1 ≥ Subarray.size x✝
hk : k < Subarray.size x✝
hdesc : Descendant i✝ k
⊢ ∃ l hl, Descendant i✝ l ∧ x✝[k] = x✝[l]
Tactic:
exact ⟨k,hk,hdesc,rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    Descendant (2 * i + 1) k →
      ∃ l hl_1,
        Descendant (2 * i + 1) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
⊢ ∃ l hl_1, Descendant i l ∧ y[k] = x[l]
Tactic:
if hdesc' : Descendant (2*i+1) k then
  have ⟨l,hl,hld,IH⟩ := @IH hk hdesc'
  simp only [IH, Subarray.getElem_swap]
  if hll : 2*i+1 = l then
    cases hll; simp only [ite_true]
    exact ⟨i, hi, .refl i, rfl⟩
  else
    rewrite [if_neg hll, if_neg <| Nat.ne_of_lt <| trans (lt_child_left i) hld.le]
    exact ⟨l, hl, .trans (.child_left i) hld, rfl⟩
else
  simp only [h.get_not_descendant k hdesc', Subarray.getElem_swap]
  rewrite [if_neg (c:=2*i+1=k) fun h => by cases h; exact hdesc' (.refl _)]
  if hik : i = k then
    cases hik; simp only [ite_true]
    exact ⟨2*k+1, hl, .child_left k, rfl⟩
  else
    simp only [if_neg hik]
    exact ⟨k, hk, hdesc, rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    Descendant (2 * i + 1) k →
      ∃ l hl_1,
        Descendant (2 * i + 1) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 1) k
⊢ ∃ l hl_1, Descendant i l ∧ y[k] = x[l]
Tactic:
have ⟨l,hl,hld,IH⟩ := @IH hk hdesc'
State after:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    Descendant (2 * i + 1) k →
      ∃ l hl,
        Descendant (2 * i + 1) l ∧
          y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 1) k
l : Nat
hl : l < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hld : Descendant (2 * i + 1) l
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[l]
⊢ ∃ l hl, Descendant i l ∧ y[k] = x[l]

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    Descendant (2 * i + 1) k →
      ∃ l hl,
        Descendant (2 * i + 1) l ∧
          y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 1) k
l : Nat
hl : l < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hld : Descendant (2 * i + 1) l
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[l]
⊢ ∃ l hl, Descendant i l ∧ y[k] = x[l]
Tactic:
simp only [IH, Subarray.getElem_swap]
State after:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    Descendant (2 * i + 1) k →
      ∃ l hl,
        Descendant (2 * i + 1) l ∧
          y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 1) k
l : Nat
hl : l < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hld : Descendant (2 * i + 1) l
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[l]
⊢ ∃ l_1 hl_1, Descendant i l_1 ∧ (if 2 * i + 1 = l then x[i] else if i = l then x[2 * i + 1] else x[l]) = x[l_1]

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    Descendant (2 * i + 1) k →
      ∃ l hl,
        Descendant (2 * i + 1) l ∧
          y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 1) k
l : Nat
hl : l < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hld : Descendant (2 * i + 1) l
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[l]
⊢ ∃ l_1 hl_1, Descendant i l_1 ∧ (if 2 * i + 1 = l then x[i] else if i = l then x[2 * i + 1] else x[l]) = x[l_1]
Tactic:
if hll : 2*i+1 = l then
  cases hll; simp only [ite_true]
  exact ⟨i, hi, .refl i, rfl⟩
else
  rewrite [if_neg hll, if_neg <| Nat.ne_of_lt <| trans (lt_child_left i) hld.le]
  exact ⟨l, hl, .trans (.child_left i) hld, rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    Descendant (2 * i + 1) k →
      ∃ l hl,
        Descendant (2 * i + 1) l ∧
          y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 1) k
l : Nat
hl : l < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hld : Descendant (2 * i + 1) l
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[l]
hll : 2 * i + 1 = l
⊢ ∃ l_1 hl_1, Descendant i l_1 ∧ (if 2 * i + 1 = l then x[i] else if i = l then x[2 * i + 1] else x[l]) = x[l_1]
Tactic:
cases hll
State after:
case refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    Descendant (2 * i + 1) k →
      ∃ l hl,
        Descendant (2 * i + 1) l ∧
          y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 1) k
hl : 2 * i + 1 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hld : Descendant (2 * i + 1) (2 * i + 1)
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[2 * i + 1]
⊢ ∃ l hl_1,
    Descendant i l ∧
      (if 2 * i + 1 = 2 * i + 1 then x[i] else if i = 2 * i + 1 then x[2 * i + 1] else x[2 * i + 1]) = x[l]

State before:
case refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    Descendant (2 * i + 1) k →
      ∃ l hl,
        Descendant (2 * i + 1) l ∧
          y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 1) k
hl : 2 * i + 1 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hld : Descendant (2 * i + 1) (2 * i + 1)
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[2 * i + 1]
⊢ ∃ l hl_1,
    Descendant i l ∧
      (if 2 * i + 1 = 2 * i + 1 then x[i] else if i = 2 * i + 1 then x[2 * i + 1] else x[2 * i + 1]) = x[l]
Tactic:
simp only [ite_true]
State after:
case refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    Descendant (2 * i + 1) k →
      ∃ l hl,
        Descendant (2 * i + 1) l ∧
          y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 1) k
hl : 2 * i + 1 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hld : Descendant (2 * i + 1) (2 * i + 1)
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[2 * i + 1]
⊢ ∃ l hl, Descendant i l ∧ x[i] = x[l]

State before:
case refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    Descendant (2 * i + 1) k →
      ∃ l hl,
        Descendant (2 * i + 1) l ∧
          y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 1) k
hl : 2 * i + 1 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hld : Descendant (2 * i + 1) (2 * i + 1)
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[2 * i + 1]
⊢ ∃ l hl, Descendant i l ∧ x[i] = x[l]
Tactic:
exact ⟨i, hi, .refl i, rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    Descendant (2 * i + 1) k →
      ∃ l hl,
        Descendant (2 * i + 1) l ∧
          y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 1) k
l : Nat
hl : l < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hld : Descendant (2 * i + 1) l
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[l]
hll : ¬2 * i + 1 = l
⊢ ∃ l_1 hl_1, Descendant i l_1 ∧ (if 2 * i + 1 = l then x[i] else if i = l then x[2 * i + 1] else x[l]) = x[l_1]
Tactic:
rewrite [if_neg hll, if_neg <| Nat.ne_of_lt <| trans (lt_child_left i) hld.le]
State after:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    Descendant (2 * i + 1) k →
      ∃ l hl,
        Descendant (2 * i + 1) l ∧
          y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 1) k
l : Nat
hl : l < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hld : Descendant (2 * i + 1) l
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[l]
hll : ¬2 * i + 1 = l
⊢ ∃ l_1 hl_1, Descendant i l_1 ∧ x[l] = x[l_1]

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })),
    Descendant (2 * i + 1) k →
      ∃ l hl,
        Descendant (2 * i + 1) l ∧
          y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 1) k
l : Nat
hl : l < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hld : Descendant (2 * i + 1) l
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[l]
hll : ¬2 * i + 1 = l
⊢ ∃ l_1 hl_1, Descendant i l_1 ∧ x[l] = x[l_1]
Tactic:
exact ⟨l, hl, .trans (.child_left i) hld, rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    Descendant (2 * i + 1) k →
      ∃ l hl_1,
        Descendant (2 * i + 1) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : ¬Descendant (2 * i + 1) k
⊢ ∃ l hl_1, Descendant i l ∧ y[k] = x[l]
Tactic:
simp only [h.get_not_descendant k hdesc', Subarray.getElem_swap]
State after:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    Descendant (2 * i + 1) k →
      ∃ l hl_1,
        Descendant (2 * i + 1) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : ¬Descendant (2 * i + 1) k
⊢ ∃ l hl_1, Descendant i l ∧ (if 2 * i + 1 = k then x[i] else if i = k then x[2 * i + 1] else x[k]) = x[l]

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    Descendant (2 * i + 1) k →
      ∃ l hl_1,
        Descendant (2 * i + 1) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : ¬Descendant (2 * i + 1) k
⊢ ∃ l hl_1, Descendant i l ∧ (if 2 * i + 1 = k then x[i] else if i = k then x[2 * i + 1] else x[k]) = x[l]
Tactic:
rewrite [if_neg (c:=2*i+1=k) fun h => by cases h; exact hdesc' (.refl _)]
State after:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    Descendant (2 * i + 1) k →
      ∃ l hl_1,
        Descendant (2 * i + 1) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : ¬Descendant (2 * i + 1) k
⊢ ∃ l hl_1, Descendant i l ∧ (if i = k then x[2 * i + 1] else x[k]) = x[l]

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    Descendant (2 * i + 1) k →
      ∃ l hl_1,
        Descendant (2 * i + 1) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : ¬Descendant (2 * i + 1) k
⊢ ∃ l hl_1, Descendant i l ∧ (if i = k then x[2 * i + 1] else x[k]) = x[l]
Tactic:
if hik : i = k then
  cases hik; simp only [ite_true]
  exact ⟨2*k+1, hl, .child_left k, rfl⟩
else
  simp only [if_neg hik]
  exact ⟨k, hk, hdesc, rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    Descendant (2 * i + 1) k →
      ∃ l hl_1,
        Descendant (2 * i + 1) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : ¬Descendant (2 * i + 1) k
h : 2 * i + 1 = k
⊢ False
Tactic:
cases h
State after:
case refl
α : Type u
lt : α → α → Bool
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
IH :
  ∀ (hk : 2 * i + 1 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    Descendant (2 * i + 1) (2 * i + 1) →
      ∃ l hl_1,
        Descendant (2 * i + 1) l ∧
          y[2 * i + 1] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[l]
hk : 2 * i + 1 < Subarray.size x
hdesc : Descendant i (2 * i + 1)
hdesc' : ¬Descendant (2 * i + 1) (2 * i + 1)
⊢ False

State before:
case refl
α : Type u
lt : α → α → Bool
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
IH :
  ∀ (hk : 2 * i + 1 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    Descendant (2 * i + 1) (2 * i + 1) →
      ∃ l hl_1,
        Descendant (2 * i + 1) l ∧
          y[2 * i + 1] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[l]
hk : 2 * i + 1 < Subarray.size x
hdesc : Descendant i (2 * i + 1)
hdesc' : ¬Descendant (2 * i + 1) (2 * i + 1)
⊢ False
Tactic:
exact hdesc' (.refl _)
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    Descendant (2 * i + 1) k →
      ∃ l hl_1,
        Descendant (2 * i + 1) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : ¬Descendant (2 * i + 1) k
hik : i = k
⊢ ∃ l hl_1, Descendant i l ∧ (if i = k then x[2 * i + 1] else x[k]) = x[l]
Tactic:
cases hik
State after:
case refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i : Nat
y✝ : Subarray α
k : Nat
x y : Subarray α
hk hi : k < Subarray.size x
hl : 2 * k + 1 < Subarray.size x
hr : 2 * k + 2 < Subarray.size x
hx' : lt x[2 * k + 2] x[2 * k + 1] = true
hx : lt x[k] x[2 * k + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 1, isLt := hl }) (2 * k + 1) y
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 1, isLt := hl })),
    Descendant (2 * k + 1) k →
      ∃ l hl_1,
        Descendant (2 * k + 1) l ∧ y[k] = (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 1, isLt := hl })[l]
hdesc : Descendant k k
hdesc' : ¬Descendant (2 * k + 1) k
⊢ ∃ l hl_1, Descendant k l ∧ (if k = k then x[2 * k + 1] else x[k]) = x[l]

State before:
case refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i : Nat
y✝ : Subarray α
k : Nat
x y : Subarray α
hk hi : k < Subarray.size x
hl : 2 * k + 1 < Subarray.size x
hr : 2 * k + 2 < Subarray.size x
hx' : lt x[2 * k + 2] x[2 * k + 1] = true
hx : lt x[k] x[2 * k + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 1, isLt := hl }) (2 * k + 1) y
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 1, isLt := hl })),
    Descendant (2 * k + 1) k →
      ∃ l hl_1,
        Descendant (2 * k + 1) l ∧ y[k] = (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 1, isLt := hl })[l]
hdesc : Descendant k k
hdesc' : ¬Descendant (2 * k + 1) k
⊢ ∃ l hl_1, Descendant k l ∧ (if k = k then x[2 * k + 1] else x[k]) = x[l]
Tactic:
simp only [ite_true]
State after:
case refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i : Nat
y✝ : Subarray α
k : Nat
x y : Subarray α
hk hi : k < Subarray.size x
hl : 2 * k + 1 < Subarray.size x
hr : 2 * k + 2 < Subarray.size x
hx' : lt x[2 * k + 2] x[2 * k + 1] = true
hx : lt x[k] x[2 * k + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 1, isLt := hl }) (2 * k + 1) y
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 1, isLt := hl })),
    Descendant (2 * k + 1) k →
      ∃ l hl_1,
        Descendant (2 * k + 1) l ∧ y[k] = (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 1, isLt := hl })[l]
hdesc : Descendant k k
hdesc' : ¬Descendant (2 * k + 1) k
⊢ ∃ l hl_1, Descendant k l ∧ x[2 * k + 1] = x[l]

State before:
case refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i : Nat
y✝ : Subarray α
k : Nat
x y : Subarray α
hk hi : k < Subarray.size x
hl : 2 * k + 1 < Subarray.size x
hr : 2 * k + 2 < Subarray.size x
hx' : lt x[2 * k + 2] x[2 * k + 1] = true
hx : lt x[k] x[2 * k + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 1, isLt := hl }) (2 * k + 1) y
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 1, isLt := hl })),
    Descendant (2 * k + 1) k →
      ∃ l hl_1,
        Descendant (2 * k + 1) l ∧ y[k] = (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 1, isLt := hl })[l]
hdesc : Descendant k k
hdesc' : ¬Descendant (2 * k + 1) k
⊢ ∃ l hl_1, Descendant k l ∧ x[2 * k + 1] = x[l]
Tactic:
exact ⟨2*k+1, hl, .child_left k, rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    Descendant (2 * i + 1) k →
      ∃ l hl_1,
        Descendant (2 * i + 1) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : ¬Descendant (2 * i + 1) k
hik : ¬i = k
⊢ ∃ l hl_1, Descendant i l ∧ (if i = k then x[2 * i + 1] else x[k]) = x[l]
Tactic:
simp only [if_neg hik]
State after:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    Descendant (2 * i + 1) k →
      ∃ l hl_1,
        Descendant (2 * i + 1) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : ¬Descendant (2 * i + 1) k
hik : ¬i = k
⊢ ∃ l hl_1, Descendant i l ∧ x[k] = x[l]

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    Descendant (2 * i + 1) k →
      ∃ l hl_1,
        Descendant (2 * i + 1) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : ¬Descendant (2 * i + 1) k
hik : ¬i = k
⊢ ∃ l hl_1, Descendant i l ∧ x[k] = x[l]
Tactic:
exact ⟨k, hk, hdesc, rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
⊢ ∃ l hl_1, Descendant i l ∧ y[k] = x[l]
Tactic:
if hdesc' : Descendant (2*i+2) k then
  have ⟨l,hl,hld,IH⟩ := @IH hk hdesc'
  simp only [IH, Subarray.getElem_swap]
  if hrl : 2*i+2 = l then
    cases hrl; simp only [ite_true]
    exact ⟨i, hi, .refl i, rfl⟩
  else
    rewrite [if_neg hrl, if_neg <| Nat.ne_of_lt <| trans (lt_child_right i) hld.le]
    exact ⟨l, hl, .trans (.child_right i) hld, rfl⟩
else
  simp only [h.get_not_descendant k hdesc', Subarray.getElem_swap]
  rewrite [if_neg (c:=2*i+2=k) fun h => by cases h; exact hdesc' (.refl _)]
  if hik : i = k then
    cases hik; simp only [ite_true]
    exact ⟨2*k+2, hr, .child_right k, rfl⟩
  else
    simp only [if_neg hik]
    exact ⟨k, hk, hdesc, rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 2) k
⊢ ∃ l hl_1, Descendant i l ∧ y[k] = x[l]
Tactic:
have ⟨l,hl,hld,IH⟩ := @IH hk hdesc'
State after:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 2) k
l : Nat
hl : l < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })
hld : Descendant (2 * i + 2) l
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
⊢ ∃ l hl, Descendant i l ∧ y[k] = x[l]

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 2) k
l : Nat
hl : l < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })
hld : Descendant (2 * i + 2) l
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
⊢ ∃ l hl, Descendant i l ∧ y[k] = x[l]
Tactic:
simp only [IH, Subarray.getElem_swap]
State after:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 2) k
l : Nat
hl : l < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })
hld : Descendant (2 * i + 2) l
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
⊢ ∃ l_1 hl_1, Descendant i l_1 ∧ (if 2 * i + 2 = l then x[i] else if i = l then x[2 * i + 2] else x[l]) = x[l_1]

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 2) k
l : Nat
hl : l < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })
hld : Descendant (2 * i + 2) l
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
⊢ ∃ l_1 hl_1, Descendant i l_1 ∧ (if 2 * i + 2 = l then x[i] else if i = l then x[2 * i + 2] else x[l]) = x[l_1]
Tactic:
if hrl : 2*i+2 = l then
  cases hrl; simp only [ite_true]
  exact ⟨i, hi, .refl i, rfl⟩
else
  rewrite [if_neg hrl, if_neg <| Nat.ne_of_lt <| trans (lt_child_right i) hld.le]
  exact ⟨l, hl, .trans (.child_right i) hld, rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 2) k
l : Nat
hl : l < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })
hld : Descendant (2 * i + 2) l
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hrl : 2 * i + 2 = l
⊢ ∃ l_1 hl_1, Descendant i l_1 ∧ (if 2 * i + 2 = l then x[i] else if i = l then x[2 * i + 2] else x[l]) = x[l_1]
Tactic:
cases hrl
State after:
case refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 2) k
hl : 2 * i + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })
hld : Descendant (2 * i + 2) (2 * i + 2)
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[2 * i + 2]
⊢ ∃ l hl_1,
    Descendant i l ∧
      (if 2 * i + 2 = 2 * i + 2 then x[i] else if i = 2 * i + 2 then x[2 * i + 2] else x[2 * i + 2]) = x[l]

State before:
case refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 2) k
hl : 2 * i + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })
hld : Descendant (2 * i + 2) (2 * i + 2)
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[2 * i + 2]
⊢ ∃ l hl_1,
    Descendant i l ∧
      (if 2 * i + 2 = 2 * i + 2 then x[i] else if i = 2 * i + 2 then x[2 * i + 2] else x[2 * i + 2]) = x[l]
Tactic:
simp only [ite_true]
State after:
case refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 2) k
hl : 2 * i + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })
hld : Descendant (2 * i + 2) (2 * i + 2)
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[2 * i + 2]
⊢ ∃ l hl, Descendant i l ∧ x[i] = x[l]

State before:
case refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 2) k
hl : 2 * i + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })
hld : Descendant (2 * i + 2) (2 * i + 2)
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[2 * i + 2]
⊢ ∃ l hl, Descendant i l ∧ x[i] = x[l]
Tactic:
exact ⟨i, hi, .refl i, rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 2) k
l : Nat
hl : l < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })
hld : Descendant (2 * i + 2) l
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hrl : ¬2 * i + 2 = l
⊢ ∃ l_1 hl_1, Descendant i l_1 ∧ (if 2 * i + 2 = l then x[i] else if i = l then x[2 * i + 2] else x[l]) = x[l_1]
Tactic:
rewrite [if_neg hrl, if_neg <| Nat.ne_of_lt <| trans (lt_child_right i) hld.le]
State after:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 2) k
l : Nat
hl : l < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })
hld : Descendant (2 * i + 2) l
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hrl : ¬2 * i + 2 = l
⊢ ∃ l_1 hl_1, Descendant i l_1 ∧ x[l] = x[l_1]

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH✝ :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : Descendant (2 * i + 2) k
l : Nat
hl : l < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })
hld : Descendant (2 * i + 2) l
IH : y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hrl : ¬2 * i + 2 = l
⊢ ∃ l_1 hl_1, Descendant i l_1 ∧ x[l] = x[l_1]
Tactic:
exact ⟨l, hl, .trans (.child_right i) hld, rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : ¬Descendant (2 * i + 2) k
⊢ ∃ l hl_1, Descendant i l ∧ y[k] = x[l]
Tactic:
simp only [h.get_not_descendant k hdesc', Subarray.getElem_swap]
State after:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : ¬Descendant (2 * i + 2) k
⊢ ∃ l hl_1, Descendant i l ∧ (if 2 * i + 2 = k then x[i] else if i = k then x[2 * i + 2] else x[k]) = x[l]

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : ¬Descendant (2 * i + 2) k
⊢ ∃ l hl_1, Descendant i l ∧ (if 2 * i + 2 = k then x[i] else if i = k then x[2 * i + 2] else x[k]) = x[l]
Tactic:
rewrite [if_neg (c:=2*i+2=k) fun h => by cases h; exact hdesc' (.refl _)]
State after:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : ¬Descendant (2 * i + 2) k
⊢ ∃ l hl_1, Descendant i l ∧ (if i = k then x[2 * i + 2] else x[k]) = x[l]

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : ¬Descendant (2 * i + 2) k
⊢ ∃ l hl_1, Descendant i l ∧ (if i = k then x[2 * i + 2] else x[k]) = x[l]
Tactic:
if hik : i = k then
  cases hik; simp only [ite_true]
  exact ⟨2*k+2, hr, .child_right k, rfl⟩
else
  simp only [if_neg hik]
  exact ⟨k, hk, hdesc, rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : ¬Descendant (2 * i + 2) k
h : 2 * i + 2 = k
⊢ False
Tactic:
cases h
State after:
case refl
α : Type u
lt : α → α → Bool
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
IH :
  ∀ (hk : 2 * i + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) (2 * i + 2) →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧
          y[2 * i + 2] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : 2 * i + 2 < Subarray.size x
hdesc : Descendant i (2 * i + 2)
hdesc' : ¬Descendant (2 * i + 2) (2 * i + 2)
⊢ False

State before:
case refl
α : Type u
lt : α → α → Bool
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
IH :
  ∀ (hk : 2 * i + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) (2 * i + 2) →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧
          y[2 * i + 2] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : 2 * i + 2 < Subarray.size x
hdesc : Descendant i (2 * i + 2)
hdesc' : ¬Descendant (2 * i + 2) (2 * i + 2)
⊢ False
Tactic:
exact hdesc' (.refl _)
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : ¬Descendant (2 * i + 2) k
hik : i = k
⊢ ∃ l hl_1, Descendant i l ∧ (if i = k then x[2 * i + 2] else x[k]) = x[l]
Tactic:
cases hik
State after:
case refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i : Nat
y✝ : Subarray α
k : Nat
x y : Subarray α
hk hi : k < Subarray.size x
hl : 2 * k + 1 < Subarray.size x
hr : 2 * k + 2 < Subarray.size x
hx' : lt x[2 * k + 2] x[2 * k + 1] = false
hx : lt x[k] x[2 * k + 2] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 2, isLt := hr }) (2 * k + 2) y
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 2, isLt := hr })),
    Descendant (2 * k + 2) k →
      ∃ l hl,
        Descendant (2 * k + 2) l ∧ y[k] = (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 2, isLt := hr })[l]
hdesc : Descendant k k
hdesc' : ¬Descendant (2 * k + 2) k
⊢ ∃ l hl_1, Descendant k l ∧ (if k = k then x[2 * k + 2] else x[k]) = x[l]

State before:
case refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i : Nat
y✝ : Subarray α
k : Nat
x y : Subarray α
hk hi : k < Subarray.size x
hl : 2 * k + 1 < Subarray.size x
hr : 2 * k + 2 < Subarray.size x
hx' : lt x[2 * k + 2] x[2 * k + 1] = false
hx : lt x[k] x[2 * k + 2] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 2, isLt := hr }) (2 * k + 2) y
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 2, isLt := hr })),
    Descendant (2 * k + 2) k →
      ∃ l hl,
        Descendant (2 * k + 2) l ∧ y[k] = (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 2, isLt := hr })[l]
hdesc : Descendant k k
hdesc' : ¬Descendant (2 * k + 2) k
⊢ ∃ l hl_1, Descendant k l ∧ (if k = k then x[2 * k + 2] else x[k]) = x[l]
Tactic:
simp only [ite_true]
State after:
case refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i : Nat
y✝ : Subarray α
k : Nat
x y : Subarray α
hk hi : k < Subarray.size x
hl : 2 * k + 1 < Subarray.size x
hr : 2 * k + 2 < Subarray.size x
hx' : lt x[2 * k + 2] x[2 * k + 1] = false
hx : lt x[k] x[2 * k + 2] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 2, isLt := hr }) (2 * k + 2) y
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 2, isLt := hr })),
    Descendant (2 * k + 2) k →
      ∃ l hl,
        Descendant (2 * k + 2) l ∧ y[k] = (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 2, isLt := hr })[l]
hdesc : Descendant k k
hdesc' : ¬Descendant (2 * k + 2) k
⊢ ∃ l hl, Descendant k l ∧ x[2 * k + 2] = x[l]

State before:
case refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i : Nat
y✝ : Subarray α
k : Nat
x y : Subarray α
hk hi : k < Subarray.size x
hl : 2 * k + 1 < Subarray.size x
hr : 2 * k + 2 < Subarray.size x
hx' : lt x[2 * k + 2] x[2 * k + 1] = false
hx : lt x[k] x[2 * k + 2] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 2, isLt := hr }) (2 * k + 2) y
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 2, isLt := hr })),
    Descendant (2 * k + 2) k →
      ∃ l hl,
        Descendant (2 * k + 2) l ∧ y[k] = (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 2, isLt := hr })[l]
hdesc : Descendant k k
hdesc' : ¬Descendant (2 * k + 2) k
⊢ ∃ l hl, Descendant k l ∧ x[2 * k + 2] = x[l]
Tactic:
exact ⟨2*k+2, hr, .child_right k, rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : ¬Descendant (2 * i + 2) k
hik : ¬i = k
⊢ ∃ l hl_1, Descendant i l ∧ (if i = k then x[2 * i + 2] else x[k]) = x[l]
Tactic:
simp only [if_neg hik]
State after:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : ¬Descendant (2 * i + 2) k
hik : ¬i = k
⊢ ∃ l hl_1, Descendant i l ∧ x[k] = x[l]

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
IH :
  ∀ (hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })),
    Descendant (2 * i + 2) k →
      ∃ l hl,
        Descendant (2 * i + 2) l ∧ y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[l]
hk : k < Subarray.size x
hdesc : Descendant i k
hdesc' : ¬Descendant (2 * i + 2) k
hik : ¬i = k
⊢ ∃ l hl_1, Descendant i l ∧ x[k] = x[l]
Tactic:
exact ⟨k, hk, hdesc, rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
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
hk : k < Subarray.size x
hdesc : Descendant i k
⊢ ∃ l hl_1, Descendant i l ∧ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[k] = x[l]
Tactic:
simp only [Subarray.getElem_swap]
State after:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
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
hk : k < Subarray.size x
hdesc : Descendant i k
⊢ ∃ l hl_1, Descendant i l ∧ (if 2 * i + 1 = k then x[i] else if i = k then x[2 * i + 1] else x[k]) = x[l]

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
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
hk : k < Subarray.size x
hdesc : Descendant i k
⊢ ∃ l hl_1, Descendant i l ∧ (if 2 * i + 1 = k then x[i] else if i = k then x[2 * i + 1] else x[k]) = x[l]
Tactic:
if hlk : 2*i+1 = k then
  cases hlk; simp only [ite_true]
  exact ⟨i, hi, .refl i, rfl⟩
else if hik : i = k then
  cases hik; simp only [if_neg hlk, ite_true]
  exact ⟨2*k+1, hl, .child_left k, rfl⟩
else
  simp only [if_neg hlk, if_neg hik]
  exact ⟨k, hk, hdesc, rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
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
hk : k < Subarray.size x
hdesc : Descendant i k
hlk : 2 * i + 1 = k
⊢ ∃ l hl_1, Descendant i l ∧ (if 2 * i + 1 = k then x[i] else if i = k then x[2 * i + 1] else x[k]) = x[l]
Tactic:
cases hlk
State after:
case refl
α : Type u
lt : α → α → Bool
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
hk : 2 * i + 1 < Subarray.size x
hdesc : Descendant i (2 * i + 1)
⊢ ∃ l hl_1,
    Descendant i l ∧
      (if 2 * i + 1 = 2 * i + 1 then x[i] else if i = 2 * i + 1 then x[2 * i + 1] else x[2 * i + 1]) = x[l]

State before:
case refl
α : Type u
lt : α → α → Bool
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
hk : 2 * i + 1 < Subarray.size x
hdesc : Descendant i (2 * i + 1)
⊢ ∃ l hl_1,
    Descendant i l ∧
      (if 2 * i + 1 = 2 * i + 1 then x[i] else if i = 2 * i + 1 then x[2 * i + 1] else x[2 * i + 1]) = x[l]
Tactic:
simp only [ite_true]
State after:
case refl
α : Type u
lt : α → α → Bool
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
hk : 2 * i + 1 < Subarray.size x
hdesc : Descendant i (2 * i + 1)
⊢ ∃ l hl, Descendant i l ∧ x[i] = x[l]

State before:
case refl
α : Type u
lt : α → α → Bool
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
hk : 2 * i + 1 < Subarray.size x
hdesc : Descendant i (2 * i + 1)
⊢ ∃ l hl, Descendant i l ∧ x[i] = x[l]
Tactic:
exact ⟨i, hi, .refl i, rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
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
hk : k < Subarray.size x
hdesc : Descendant i k
hlk : ¬2 * i + 1 = k
⊢ ∃ l hl_1, Descendant i l ∧ (if 2 * i + 1 = k then x[i] else if i = k then x[2 * i + 1] else x[k]) = x[l]
Tactic:
if hik : i = k then
cases hik; simp only [if_neg hlk, ite_true]
exact ⟨2*k+1, hl, .child_left k, rfl⟩
else
simp only [if_neg hlk, if_neg hik]
exact ⟨k, hk, hdesc, rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
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
hk : k < Subarray.size x
hdesc : Descendant i k
hlk : ¬2 * i + 1 = k
hik : i = k
⊢ ∃ l hl_1, Descendant i l ∧ (if 2 * i + 1 = k then x[i] else if i = k then x[2 * i + 1] else x[k]) = x[l]
Tactic:
cases hik
State after:
case refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i : Nat
y : Subarray α
k : Nat
x : Subarray α
hk hi : k < Subarray.size x
hl : 2 * k + 1 < Subarray.size x
hr : 2 * k + 2 ≥ Subarray.size x
hx : lt x[k] x[2 * k + 1] = true
hdesc : Descendant k k
hlk : ¬2 * k + 1 = k
⊢ ∃ l hl_1, Descendant k l ∧ (if 2 * k + 1 = k then x[k] else if k = k then x[2 * k + 1] else x[k]) = x[l]

State before:
case refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i : Nat
y : Subarray α
k : Nat
x : Subarray α
hk hi : k < Subarray.size x
hl : 2 * k + 1 < Subarray.size x
hr : 2 * k + 2 ≥ Subarray.size x
hx : lt x[k] x[2 * k + 1] = true
hdesc : Descendant k k
hlk : ¬2 * k + 1 = k
⊢ ∃ l hl_1, Descendant k l ∧ (if 2 * k + 1 = k then x[k] else if k = k then x[2 * k + 1] else x[k]) = x[l]
Tactic:
simp only [if_neg hlk, ite_true]
State after:
case refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i : Nat
y : Subarray α
k : Nat
x : Subarray α
hk hi : k < Subarray.size x
hl : 2 * k + 1 < Subarray.size x
hr : 2 * k + 2 ≥ Subarray.size x
hx : lt x[k] x[2 * k + 1] = true
hdesc : Descendant k k
hlk : ¬2 * k + 1 = k
⊢ ∃ l hl_1, Descendant k l ∧ x[2 * k + 1] = x[l]

State before:
case refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i : Nat
y : Subarray α
k : Nat
x : Subarray α
hk hi : k < Subarray.size x
hl : 2 * k + 1 < Subarray.size x
hr : 2 * k + 2 ≥ Subarray.size x
hx : lt x[k] x[2 * k + 1] = true
hdesc : Descendant k k
hlk : ¬2 * k + 1 = k
⊢ ∃ l hl_1, Descendant k l ∧ x[2 * k + 1] = x[l]
Tactic:
exact ⟨2*k+1, hl, .child_left k, rfl⟩
State after:
no goals

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
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
hk : k < Subarray.size x
hdesc : Descendant i k
hlk : ¬2 * i + 1 = k
hik : ¬i = k
⊢ ∃ l hl_1, Descendant i l ∧ (if 2 * i + 1 = k then x[i] else if i = k then x[2 * i + 1] else x[k]) = x[l]
Tactic:
simp only [if_neg hlk, if_neg hik]
State after:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
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
hk : k < Subarray.size x
hdesc : Descendant i k
hlk : ¬2 * i + 1 = k
hik : ¬i = k
⊢ ∃ l hl_1, Descendant i l ∧ x[k] = x[l]

State before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
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
hk : k < Subarray.size x
hdesc : Descendant i k
hlk : ¬2 * i + 1 = k
hik : ¬i = k
⊢ ∃ l hl_1, Descendant i l ∧ x[k] = x[l]
Tactic:
exact ⟨k, hk, hdesc, rfl⟩
State after:
no goals