Car-pooling as a data structuring device: The soft heap

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


A simple variant of a priority queue, called a soft heap, is introduced. The data structure supports the usual operations: insert, delete, meld, and findmin. In order to beat the standard information-theoretic bounds, the soft heap allows errors: occasionally, the keys of certain items are artificially raised. Given any 0 < ε < 1/2 and any mixed sequence of n operations, the soft heap ensures that at most εn keys are raised at any time. The amortized complexity of each operation is constant, except for insert, which takes O(log 1/ε) time. The soft heap is optimal. Also, being purely pointer-based, no arrays are used and no numeric assumptions are made on the keys. The novelty of the data structure is that items are moved together in groups, in a data-structuring equivalent of "car pooling." The main application of the data structure is a faster deterministic algorithm for minimum spanning trees.

Original languageEnglish (US)
Title of host publicationAlgorithms, ESA 1998 - 6th Annual European Symposium, Proceedings
PublisherSpringer Verlag
Number of pages8
ISBN (Print)3540648488, 9783540648482
StatePublished - 1998
Event6th Annual European Symposium on Algorithms, ESA 1998 - Venice, Italy
Duration: Aug 24 1998Aug 26 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1461 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other6th Annual European Symposium on Algorithms, ESA 1998

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Car-pooling as a data structuring device: The soft heap'. Together they form a unique fingerprint.

Cite this