Pairing Heap

Hauke Brinkop 📧 and Tobias Nipkow 🌐

July 14, 2016

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.


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

Extra 0

Origin: This library was extracted from Amortized Complexity and extended.


Related publications

Session Pairing_Heap