ComputingComputer ScienceAlgorithmsCombinatoricsData StructuresAlgorithm AnalysisAmortized AnalysisMemory HierarchyMemory Hierarchy OptimizationTime ComplexityAmortized ComplexityAmortized CostHeap OrganizationHeapsPairing Heap Analysis
We give a variation of the pairing heaps for which the time bounds for all the \noperations match the lower bound proved by Fredman for a family of similar \nself-adjusting heaps.\nNamely, our heap structure requires $O(1)$ for insert and find-min, \n$O(\\log{n})$ for delete-min, and $O(\\log\\log{n})$ for decrease-key and meld \n(all the bounds are in the amortized sense except for find-min).
7
Self-adjusting binary search trees
Daniel D. Sleator, Robert E. Tarjan · Journal of the ACM · 1985 · 1.2K citations · Full text
Amortized Computational Complexity
Robert E. Tarjan · SIAM Journal on Algebraic and Discrete Methods · 1985 · 525 citations
Daniel D. Sleator, Robert E. Tarjan · SIAM Journal on Computing · 1986 · 153 citations
John Stasko, Jeffrey Scott Vitter · Communications of the ACM · 1987 · 81 citations · Full text