THEOREM 1, p. 604 — from no F-heaps, total time ≤ Σ C(log n + 1) over delete min/delete + Σ C over other operations
ProvedFibHeap.Amort.theorem_1There is an absolute constant with the following property. Begin with no F-heaps and perform an arbitrary sequence of F-heap operations (make heap, find min, insert, meld, delete min, decrease key, delete), passing through collections . Let be the actual time of : one unit, plus one per linking step, plus one per cut, plus the rank scan of a delete min. Then
where is the number of items in just before .
This is the paper's statement that the total time is at most the total amortized time, where the amortized time is for delete min and delete and for every other operation. It is what yields the bound for Dijkstra's algorithm and the other network-optimization bounds of the paper.
Formalization Note The is pinned to one constant chosen before the sequence of operations. The cost counts every linking step and every cut, as fixed by the step relation; the potential does not appear in the statement. The linking order and the choice among minimum-key roots are arbitrary, and the bound must hold for every choice.
import Mathlib import Definitions.Def_FibHeap_Amort_Model
namespace FibHeap.Amort
theorem theorem_1 :
∃ C : ℝ, 0 < C ∧ ∀ (T : ℕ) (s : ℕ → Coll) (op : ℕ → Op) (d : ℕ → StepData),
IsRun T s op d →
(∑ t ∈ Finset.range T, (cost (d t) : ℝ)) ≤
∑ t ∈ Finset.range T, opBound C (s t) (op t) := by sorry
end FibHeap.Amort
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.