The pairing heap is an efficient, easy-to-implement self-adjusting heap which is in widespread practical use. Multiple variants of this heap have been proposed in the original paper by Fredman, Sedgewick, Sleator and Tarjan, but these have proven difficult to analyse. Furthermore, a related heap – the smooth heap – has recently been proposed and partial theoretical analysis of this heap appears promising. Stable linking, which is a twist on the linking operation used by pairing heaps, is a characteristic operation of this heap. This operation can be retrofitted into the pairing heap, giving rise to further heap variants. We implement these variants and measure efficiency by counting the number of link operations and the number of comparisons performed overall in various experimental settings, viz. in sorting mode and when used as priority queues in Dijkstra’s algorithm forshortest paths.

The results suggest that the original variant of the pairing heap is generally superior to its other variants, and that the smooth heap may outperform the pairing heap and its variants in certain cases. The smooth heap performs particularly well in sorting mode – when sorting inputs which contain many sorted subsequences – and perhaps also in use cases where the number of decrease-key operations dominates the others. In these cases, smooth heaps perform fewer comparisons and fewer link operations than the pairing heap and its variants. Furthermore, in more general settings the smooth heap appears to perform fewer link operations than all pairing heap variants, at the cost of requiring slightly more comparisons. Depending on the relative cost of linking operations and comparisons this might mean that the smooth heap outperforms the pairing heap in practice even in general cases.

It is also shown that none of the heaps considered here are capable of sorting Jordan permutations, a special permutation class, in linear time.

Furthermore, two theoretical results for related heaps are shown: First, that the sort heap, proposed by Iacono and Özkan as an instance of their pure heap model which has amortised cost O(log log n) insert and decrease-key operations and O(log n log log n) amortised delete-min, does not in fact conform to those worst-case bounds, because the proof of this bound for decrease-key is flawed.

Finally, we show a property of instances of the stable heap model, to which the smooth heap conforms. We prove that the order in which stable-links are performed during consolidation of the forest into a single heap is not relevant for the outcome, because any resulting tree can also be constructed using a sequence of stable-links which requires only O(n) pointer moves.