Communications of the ACM · 1987 · 81 citations · 7 references
ComputingComputer ScienceAlgorithmsData StructuresParallel AlgorithmsAlgorithm AnalysisAmortized AnalysisMemory HierarchyPriority QueuesSorting AlgorithmsTime ComplexityAmortized Running TimeFibonacci Heap AnalysisHeapsPairing Heap AnalysisPriority Queue Implementation
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.
7
Amortized Computational Complexity
Robert E. Tarjan · SIAM Journal on Algebraic and Discrete Methods · 1985 · 525 citations
John W. Williams · Communications of the ACM · 1964 · 471 citations · Full text
A data structure for manipulating priority queues
Jean Vuillemin · Communications of the ACM · 1978 · 317 citations · Full text
The pairing heap: A new form of self-adjusting heap
Michael L. Fredman, Robert Sedgewick, Daniel D. Sleator et al. · Algorithmica · 1986 · 274 citations