Pairing Heap

Hauke Brinkop and Tobias Nipkow

14 July 2016


This library defines three different versions of pairing heaps: a functional version of the original design based on binary trees [Fredman et al. 1986], the version by Okasaki [1998] and a modified version of the latter that is free of structural invariants.

The amortized complexity of pairing heaps is analyzed in the AFP article Amortized Complexity.

BSD License


This library was extracted from Amortized Complexity and extended.

Used by