§2, p. 604 — delete min increases the potential by at most log n / log φ minus the number of linking steps
ProvedFibHeap.Amort.potential_deleteMin_leamortized-analysisdelete-minfibonacci-heapp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-function
Let be a collection of F-heaps obtained from no heaps by an arbitrary sequence of F-heap operations, and let be the potential (number of trees plus twice the number of marked nonroot nodes). Suppose a delete min on the heap , which holds items, turns into using linking steps. Then
where .
Together with the cost , this gives delete min an amortized time.
Formalization Note The paper writes "at most minus the number of linking steps". The constant is a rounding slip (), with which the bound would be false for large heaps; the statement uses , the quantity the paper's own argument produces.
Preamble
import Mathlib import Definitions.Def_FibHeap_Amort_Model
Formal statement
namespace FibHeap.Amort
theorem potential_deleteMin_le (s s' : Coll) (hs : Reachable s) (h : ℕ) (d : StepData)
(hstep : Step s (.deleteMin h) s' d) :
(potential s' : ℝ) ≤
potential s + Real.logb Real.goldenRatio (heapSize (s.getD h [])) - d.links := 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.