Pairing heap
| Invented by | Fredman, Sedgewick, Sleator, Tarjan (1986) | |
|---|---|---|
| Advantages: |
| |
| 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.]
References
- 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]