{c}

<Michael L. Fredman> co-developed <Fibonacci heaps> with <Robert Tarjan>. Their 1987 paper uses deferred restructuring and <amortized analysis> to obtain constant amortized time for operations including insertion and decrease-key, with logarithmic amortized time for delete-min.<Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms by Michael L. Fredman and Robert Endre Tarjan>[§§2–3, operations and potential analysis]{ref}

This matters in <graph algorithms> that repeatedly lower tentative priorities: reducing the cost of many decrease-key operations can improve a whole algorithm's bound. A single operation can still be expensive. The guarantee concerns the total cost of a sequence, so confusing amortized time with the <worst-case analysis> of each individual operation loses the point of the construction.


 Michael L. Fredman (source code)