A pairing heap is a simple, easy-to-code, general tree data structure that enjoys logn amortized cost for standard heap operations. It is described here as an alternative to Fibonacci heaps, in that it also handles a decrease key operation efficiently, and in experimental studies it has superior performance. Its simplicity and good behavior are good reasons for using it in implementations.

The main result in this paper is that, contrary to belief until now, a pairing heap does not accommodate the decrease key operation in constant amortized time. Rather, under some circumstances, the decrease key operation can require loglogn operations. In showing this, Fredman uses a more general structure that he calls a “generalized pairing heap,” which allows balance information to be stored in the trees’ nodes and includes the Fibonacci heap as a special case. He further shows that a Fibonacci heap is optimal (a lower bound) in its need for not more than loglogn bits per node.

The author clearly discusses why the experimental results are not confirmed by theory.