SELF-ADJUSTING HEAPS.

In this paper we explore two themes in data structure design: amortized computational complexity and self-adjustment. We develop the skew heap, a self-adjusting form of heap related to the leftist heaps of C. A. Crane and D. E. 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.