Daniel Dominic Sleator, Robert Endre Tarjan

Research output: Contribution to journalArticlepeer-review

82 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)52-69
Number of pages18
JournalSIAM Journal on Computing
Issue number1
StatePublished - 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'SELF-ADJUSTING HEAPS.'. Together they form a unique fingerprint.

Cite this