§2, p. 604, potential analysis of delete min — a node of rank k in an n-item heap has φ^k ≤ n, so k ≤ log n / log φ
ProvedFibHeap.Amort.rank_le_logbfibonacci-heapgolden-ratiologarithmp2o-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, let be a heap of with items, and let be a node of of rank . Then
where .
This bounds the rank of every node, in particular of the minimum node removed by delete min, by .
Formalization Note The paper states this for the minimum node and continues "". That last constant is a rounding slip: , and a node of rank can sit in a heap of items, for which once is large. The statement therefore keeps the exact bound , and it is stated for every node, which is what the analysis of delete needs.
Preamble
import Mathlib import Definitions.Def_FibHeap_Amort_Model
Formal statement
namespace FibHeap.Amort
theorem rank_le_logb (s : Coll) (hs : Reachable s) :
∀ r ∈ s, ∀ τ ∈ r, ∀ x ∈ τ.subtrees,
Real.goldenRatio ^ x.rank ≤ (heapSize r : ℝ) ∧
(x.rank : ℝ) ≤ Real.logb Real.goldenRatio (heapSize r) := 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, §2, potential analysis of delete min
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.