Self-Adjusting Heaps
In this paper we explore two themes in data structure design: amortized computational complexity and self-adjustment. We are motivated by the following observations. In most applications of data structure, we wish to perform not just a single operation but a sequence of operations, possibly having correlated behavior. By averaging the running time per operation over a worst-case sequence of operations, we can sometimes obtain an overall time bound much smaller than the worst-case time per operation multiplied by the number of operations. We call this kind of averaging amortization. Standard kinds of data structures, such as the many varieties of balanced trees, are specifically designed so that the worst-case time per operations is small. Such efficiency is achieved by imposing an explicit structural constraint that must be maintained during updates, at a cost of both running time and storage space. However, if amortized running time is the complexity measure of interest, we can guarantee efficiency without maintaining a structural constraint. Instead, during each access or update operation we adjust the data structure in a simple, uniform way. We call such a data structure self-adjusting. In this paper we develop the skew heap, a self-adjusting form of heap related to the leftist heaps of Crane and Knuth. (What we mean by a heap has also been called a priority queue or a mergeable heap.) Skew heaps use less space than leftist heaps and similar worst-case-efficient data structures and are competitive in running time, both in theory and in practice, with worst-case structures. They are also easier to implement. We derive an information-theoretic lower bound showing that skew heaps have minimum possible amortized running time, to within a constant factor, on any sequence of certain heap operations.
- 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
- 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
- Skew Heap
- Amortized Complexity
- 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)