Self-Adjusting Heaps

DOI10.1137/0215004MaRDI QIDQ4728230zbMATH OpenOpenAlexFDO

Authors Daniel Dominic Sleator, Robert E. Tarjan

Publication date 1986

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/8e2008b892a974eab3dd7a711cbf71b6ca452e2a

zbMATH Keywords

amortizationamortized computational complexitydata structuresmergeable heappriority queueself- adjustmentself-organizing data structureskew heap

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Recommendations

• Toward optimal self-adjusting heaps
• Parameterized self-adjusting heaps
• The pairing heap: A new form of self-adjusting heap
• Smooth heaps and a dual view of self-adjusting data structures
• Smooth heaps and a dual view of self-adjusting data structures
• Adaptive Heapsort
• Available stabilizing heaps
• A selectable sloppy heap
• Heap Assumptions on Demand
• Algorithms and Data Structures

Cited in

(30)

• The amortized complexity of Henriksen's algorithm
• The pairing heap: A new form of self-adjusting heap
• Three priority queue applications revisited
• Amortized analysis of some disk scheduling algorithms: SSTF, SCAN, and \(N\)-step SCAN
• A fast algorithm for finding interlocking sets
• Manipulating multiple stacks with ordered-heap
• The relaxed min-max heap: A mergeable double-ended priority queue
• Heaps and heapsort on secondary storage
• A survey on priority queues
• A tight lower bound for top-down skew heaps
• Amortized complexity verified
• STRONGER QUICKHEAPS
• Efficient dual simplex algorithms for the assignment problem
• Amortized Computational Complexity
• A Note on Bottom-Up Skew Heaps
• Optimal purely functional priority queues
• Toward optimal self-adjusting heaps
• Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths
• Parameterized self-adjusting heaps
• An overview of Edison
• The K-D heap: An efficient multi-dimensional priority queue
• An abstract concurrent machine for rewriting
• Smooth heaps and a dual view of self-adjusting data structures
• Smooth heaps and a dual view of self-adjusting data structures
• Priority queues with decreasing keys
• Amortized complexity verified
• Strict Fibonacci heaps
• The derivation of a tighter bound for top-down skew heaps
• A complexity O(1) priority queue for event driven molecular dynamics simulations
• On sorting, heaps, and minimum spanning trees

This page was built for publication: Self-Adjusting Heaps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4728230)