§2, pp. 600–601 and 604 — make heap, find min and meld leave the potential unchanged; insert raises it by one
ProvedFibHeap.Amort.potential_makeHeap_findMin_insert_meldamortized-analysisfibonacci-heapp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-function
Let be the potential of a collection of F-heaps: the number of trees plus twice the number of marked nonroot nodes. If a collection becomes by one operation, then
- for a make heap, find min or meld operation, ;
- for an insert operation, .
Since each of these operations costs one unit, their amortized time is .
Formalization Note No reachability hypothesis is needed: the identity holds for every collection on which the operation can be performed.
Preamble
import Mathlib import Definitions.Def_FibHeap_Amort_Model
Formal statement
namespace FibHeap.Amort
theorem potential_makeHeap_findMin_insert_meld (s s' : Coll) (op : Op) (d : StepData)
(hstep : Step s op s' d) :
((op = .makeHeap ∨ (∃ h, op = .findMin h) ∨ (∃ h₁ h₂, op = .meld h₁ h₂)) →
potential s' = potential s) ∧
(∀ (i : ℕ) (k : ℝ) (h : ℕ), op = .insert i k h →
potential s' = potential s + 1) := by sorry
end FibHeap.Amort
Source
Fredman and Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM 34 (1987), pp. 600–601 and p. 604, §2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.