§2, p. 604 — decrease key increases the potential by at most three minus the number of cascading cuts
ProvedFibHeap.Amort.potential_decreaseKey_leamortized-analysiscascading-cutfibonacci-heapp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-function
Let be the potential of a collection of F-heaps (number of trees plus twice the number of marked nonroot nodes). If a decrease key operation turns the collection into and makes cascading cuts, then
With one unit charged per cut, decrease key costs when the item is not in a root, so its amortized time is at most .
Formalization Note No reachability hypothesis is needed: the bound holds for every collection on which the operation can be performed. When the item is in a root, no cut is made and .
Preamble
import Mathlib import Definitions.Def_FibHeap_Amort_Model
Formal statement
namespace FibHeap.Amort
theorem potential_decreaseKey_le (s s' : Coll) (Δ : ℝ) (i h : ℕ) (d : StepData)
(hstep : Step s (.decreaseKey Δ i h) s' d) :
potential s' + d.cascading ≤ potential s + 3 := 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 decrease key
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.