COROLLARY 1, p. 604 — a node of rank k has at least F_{k+2} ≥ φ^k descendants, including itself
ProvedFibHeap.Amort.corollary_1fibonacci-heapfibonacci-numbersgolden-ratiop2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1rank
Let be a collection of F-heaps obtained from no heaps by an arbitrary sequence of F-heap operations, and let be a node of rank in a heap of . Write for the number of descendants of , including itself, for the th Fibonacci number (, , for ) and for the golden ratio. Then
This is the source of the name "Fibonacci heap": it bounds the rank of every node by a logarithm of the heap's size.
Formalization Note The statement quantifies over reachable collections only.
Preamble
import Mathlib import Definitions.Def_FibHeap_Amort_Model
Formal statement
namespace FibHeap.Amort
theorem corollary_1 (s : Coll) (hs : Reachable s) :
∀ r ∈ s, ∀ τ ∈ r, ∀ x ∈ τ.subtrees,
Nat.fib (x.rank + 2) ≤ x.size ∧
Real.goldenRatio ^ x.rank ≤ (Nat.fib (x.rank + 2) : ℝ) := by sorry
end FibHeap.Amort
Source
Fredman and Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM 34 (1987), p. 604, COROLLARY 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.