# Pairing heap

Invented by | Fredman, Sedgewick, Sleator, Tarjan (1986) | |
---|---|---|

Advantages: | - 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.]

## 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]