D. D. Sleator, R. E. Tarjan, Self-Adjusting Heaps, SIAM J. COMPUT., Vol. 15, No. 1, 1986
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 structures, 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 operation 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.