Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

THEOREM 1, p. 604 — from no F-heaps, total time ≤ Σ C(log n + 1) over delete min/delete + Σ C over other operations

Proved
FibHeap.Amort.theorem_1

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

amortized-analysisfibonacci-heapp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1priority-queuerunning-time

There is an absolute constant C>0C > 0C>0 with the following property. Begin with no F-heaps and perform an arbitrary sequence of TTT F-heap operations o0,…,oT−1o_0, \ldots, o_{T-1}o0​,…,oT−1​ (make heap, find min, insert, meld, delete min, decrease key, delete), passing through collections S0=∅,S1,…,ST\mathcal S_0 = \emptyset, \mathcal S_1, \ldots, \mathcal S_TS0​=∅,S1​,…,ST​. Let costt\mathrm{cost}_tcostt​ be the actual time of oto_tot​: one unit, plus one per linking step, plus one per cut, plus the rank scan of a delete min. Then

∑t=0T−1costt  ≤  ∑t=0T−1bt,bt={C (log⁡2nt+1)if ot is a delete min or delete on heap ht,Cotherwise,\sum_{t=0}^{T-1} \mathrm{cost}_t \;\le\; \sum_{t=0}^{T-1} b_t, \qquad b_t = \begin{cases} C\,(\log_2 n_t + 1) & \text{if } o_t \text{ is a delete min or delete on heap } h_t,\\ C & \text{otherwise,}\end{cases}t=0∑T−1​costt​≤t=0∑T−1​bt​,bt​={C(log2​nt​+1)C​if ot​ is a delete min or delete on heap ht​,otherwise,​

where ntn_tnt​ is the number of items in hth_tht​ just before oto_tot​.

This is the paper's statement that the total time is at most the total amortized time, where the amortized time is O(log⁡n)O(\log n)O(logn) for delete min and delete and O(1)O(1)O(1) for every other operation. It is what yields the O(nlog⁡n+m)O(n \log n + m)O(nlogn+m) bound for Dijkstra's algorithm and the other network-optimization bounds of the paper.

Formalization Note The O(⋅)O(\cdot)O(⋅) is pinned to one constant CCC 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.

Preamble
import Mathlib
import Definitions.Def_FibHeap_Amort_Model
Formal statement
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
Source
Fredman and Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM 34 (1987), p. 604, THEOREM 1
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me