Abstract
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.
License
Extra 0
Origin: This library was extracted from Amortized Complexity and extended.
Topics
Related publications
- Nipkow, T., & Brinkop, H. (2018). Amortized Complexity Verified. Journal of Automated Reasoning, 62(3), 367–391. https://doi.org/10.1007/s10817-018-9459-3
- Chapter Pairing Heaps in Functional Data Structures and Algorithms
- Wikipedia