# Pairing heap

Invented by Fredman, Sedgewick, Sleator, Tarjan (1986) fast in practice all operations have $O(\log n)$ amortized complexity from theoretical point of view, the data structure has been surpassed the exact complexity of pairing heaps is still an open problem
• 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]