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 computationaland

complexityself-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 averagingamortization.

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 structureself-adjusting.

In this paper we develop theskew 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.

Daniel Sleator: Email, Home Page, Papers

Last modified: Sat Jan 21 07:15:44 EST 2006