LEMMA 1, p. 604 — the ith child of a node, in linking order, has rank at least i − 2
ProvedFibHeap.Amort.lemma_1Let be a collection of F-heaps obtained from no heaps by an arbitrary sequence of F-heap operations. Let be any node in a heap of , and arrange the children of in the order in which they were linked to , from earliest to latest. Then for every up to the rank of , the th child of satisfies
This lemma is what forces every tree of an F-heap, although not necessarily a binomial tree, to have size exponential in the rank of its root (Corollary 1).
Formalization Note Children are stored in linking order, so the th child is the list entry at index . The inequality is written to avoid truncated natural-number subtraction. The statement quantifies over reachable collections only; for arbitrary forests it is false.
import Mathlib import Definitions.Def_FibHeap_Amort_Model
namespace FibHeap.Amort
theorem lemma_1 (s : Coll) (hs : Reachable s) :
∀ r ∈ s, ∀ τ ∈ r, ∀ x ∈ τ.subtrees, ∀ (j : ℕ) (hj : j < x.children.length),
j + 1 ≤ (x.children[j]'hj).rank + 2 := by sorry
end FibHeap.Amort
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.