SELF-ADJUSTING HEAPS.

Daniel Dominic Sleator, Robert Endre Tarjan

Research output: Contribution to journalArticle

73 Scopus citations

Abstract

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
Volume15
Issue number1
DOIs
StatePublished - Jan 1 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

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

  • Cite this