A Linear Potential Function for Pairing Heaps
arXiv:1606.06389
Abstract
We present the first potential function for pairing heaps with linear range. This implies that the runtime of a short sequence of operations is faster than previously known. It is also simpler than the only other potential function known to give amortized constant amortized time for insertion.