Pairing heap

Invented by Fredman, Sedgewick, Sleator, Tarjan (1986)
  • fast in practice
  • all operations have \(O(\log n)\) amortized complexity
Disadvantages: from theoretical point of view, the data structure has been surpassed
Note: the exact complexity of pairing heaps is still an open problem
[You can download the application for offline viewing.]


  • M.L. Fredman, R. Sedgewick, D.D. Sleator, and R.E. Tarjan. The pairing heap: A new form of self-adjusting heap. Algorithmica, 1(1):111-129, 1986. [bib] [pdf]
  • J.T. Stasko and J.S. Vitter. Pairing heaps: experiments and analysis. Communications of the ACM, 30(3):234-249, 1987. [bib] [pdf]
  • S. Pettie. Towards a final analysis of pairing heaps. In Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on, pages 174-183. IEEE, 2005. [bib] [pdf]
  • A. Elmasry. Pairing heaps with $O(\log\log n)$ decrease cost. In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 471-476. Society for Industrial and Applied Mathematics, 2009. [bib] [pdf]
  • S. Pettie, V. Ramachandran, and S. Sridhar. Experimental evaluation of a new shortest path algorithm. Algorithm Engineering and Experiments, pages 105-120, 2002. [bib] [pdf]
  • B. Moret and H. Shapiro. An empirical analysis of algorithms for constructing a minimum spanning tree. Algorithms and Data Structures, pages 400-411, 1991. [bib] [pdf]