Pairing heaps
John Stasko, Jeffrey Scott Vitter · Communications of the ACM · 1987
The pairing heap has recently been introduced as a new data structure for priority queues. Pairing heaps are extremely simple to implement and seem to be very efficient in practice, but they are difficult to analyze theoretically, and open problems remain. It has been conjectured that they achieve the same amortized time bounds as Fibonacci heaps, namely, O (log n ) time for delete and delete_min and O(1) for all other operations, where n is the size of the priority queue at the time of the operation. We provide empirical evidence that supports this conjecture. The most promising algorithm in our simulations is a new variant of the twopass method, called auxiliary twopass. We prove that, assuming no decrease_key operations are performed, it achieves the same amortized time bounds as Fibonacci heaps.
Cited by 78 works. doi:10.1145/214748.214759 Open-access PDF
Authors
References
- The Design and Analysis of Computer Algorithms
- Amortized Computational Complexity
- Algorithm 232: Heapsort
- A data structure for manipulating priority queues
- Fibonacci Heaps And Their Uses In Improved Network Optimization Algorithms
- An empirical comparison of priority-queue and event-set implementations
- Implementation and Analysis of Binomial Queue Algorithms
- The pairing heap: A new form of self-adjusting heap
- Linear lists and priority queues as balanced binary trees