  The pairing heap is a simple "self-adjusting" implementation of a heap
(priority queue). Inserting an item into a pairing heap or decreasing the key
of an item takes O(1) time worst-case, as does melding two heaps. But deleting
an item of minimum key can take time linear in the heap size in the worst case.
The paper that introduced the pairing heap proved an O(log n) amortized time
bound for each heap operation, where n is the number of items in the heap or
heaps involved in the operation, by charging all but O(log n) of the time for
each deletion to non-deletion operations, O(log n) to each. Later Iacono found
a way to reduce the amortized time per insertion to O(1) and that of meld to
zero while preserving the O(log n) amortized time bound for the other update
operations. We give a simpler proof of Iacono's result with significantly
smaller constant factors. Our analysis uses the natural representation of
pairing heaps instead of the conversion to a binary tree used in the original
analysis and in Iacono's.
