Self-Adjusting Heaps
From MaRDI portal
Publication:4728230
DOI10.1137/0215004zbMath0618.68017OpenAlexW2065503744MaRDI QIDQ4728230
Daniel Dominic Sleator, Robert Endre 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
data structurespriority queueamortizationself-organizing data structureskew heapamortized computational complexitymergeable heapself- adjustment
Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Discrete mathematics in relation to computer science (68R99)
Related Items
Efficient dual simplex algorithms for the assignment problem ⋮ A tight lower bound for top-down skew heaps ⋮ The pairing heap: A new form of self-adjusting heap ⋮ The K-D heap: An efficient multi-dimensional priority queue ⋮ Amortized Computational Complexity ⋮ A complexity O(1) priority queue for event driven molecular dynamics simulations ⋮ Amortized Complexity Verified ⋮ An abstract concurrent machine for rewriting ⋮ Optimal purely functional priority queues ⋮ Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths ⋮ Three priority queue applications revisited ⋮ Amortized complexity verified ⋮ Amortized analysis of some disk scheduling algorithms: SSTF, SCAN, and \(N\)-step SCAN ⋮ STRONGER QUICKHEAPS ⋮ An Overview of Edison ⋮ On sorting, heaps, and minimum spanning trees ⋮ A fast algorithm for finding interlocking sets ⋮ The derivation of a tighter bound for top-down skew heaps ⋮ Heaps and heapsort on secondary storage ⋮ A Survey on Priority Queues ⋮ Manipulating multiple stacks with ordered-heap ⋮ The relaxed min-max heap: A mergeable double-ended priority queue ⋮ The amortized complexity of Henriksen's algorithm
