Rank-Pairing Heaps

We introduce the rank-pairing heap, an implementation of heaps that combines the
asymptotic efficiency of Fibonacci heaps with much of the simplicity of pairing heaps. Other heap
implementations that match the bounds of Fibonacci heaps do so by maintaining a balance condition
on the trees representing the heap. In contrast to these structures but like pairing heaps, our trees
can evolve to have arbitrary (unbalanced) structure. Also like pairing heaps, our structure requires
at most one cut and no other restructuring per key decrease, in the worst case: the only changes
that can cascade during a key decrease are changes in node ranks. Although our data structure is
simple, its analysis is not.