§2, p. 600 — from no heaps, the total amortized time bounds the total actual time
ProvedFibHeap.Amort.sum_cost_le_sum_amortizedamortized-analysisp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-functiontelescoping
Consider a sequence of F-heap operations starting from no heaps, passing through collections . Let be the actual time of the th operation and its amortized time, where is the potential (number of trees plus twice the number of marked nonroot nodes). Then
The reason is that the initial potential is zero and the potential is always nonnegative.
Formalization Note The paper makes this remark on p. 600 for the potential "number of trees"; p. 604 extends the potential by twice the number of marked nonroot nodes, and the statement is about the extended potential.
Preamble
import Mathlib import Definitions.Def_FibHeap_Amort_Model
Formal statement
namespace FibHeap.Amort
theorem sum_cost_le_sum_amortized (T : ℕ) (s : ℕ → Coll) (op : ℕ → Op) (d : ℕ → StepData)
(hrun : IsRun T s op d) :
(∑ t ∈ Finset.range T, (cost (d t) : ℤ)) ≤
∑ t ∈ Finset.range T, amortized (d t) (s t) (s (t + 1)) := by sorry
end FibHeap.Amort
Source
Fredman and Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM 34 (1987), p. 600, §2 (potential technique), with the potential of p. 604
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.