Soft heaps simplified

Haim Kaplan, Robert Endre Tarjan, Uri Zwick

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

In 1998, Chazelle [J. ACM, 47 (2000), pp. 1012-1027] introduced a new kind of meldable heap (priority queue) called the soft heap. Soft heaps trade accuracy for speed: the heap operations are allowed to increase the keys of certain items, thereby making these items bad, as long as the number of bad items in the data structure is at most εm, where m is the total number of insertions performed so far, and ε is an error parameter. The amortized time per heap operation is O(lg 1/ε), reduced from O(lgn), where n is the number of items in the heap. Chazelle used soft heaps in several applications, including a faster deterministic minimum-spanning-tree algorithm and a new deterministic linear-time selection algorithm. We give a simplified implementation of soft heaps that uses less space and avoids Chazelle's dismantling operations. We also give a simpler, improved analysis that yields an amortized time bound of O(lg 1/ε) for each deletion, O(1) for each other operation.

Original languageEnglish (US)
Pages (from-to)1660-1673
Number of pages14
JournalSIAM Journal on Computing
Volume42
Issue number4
DOIs
StatePublished - Oct 8 2013

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Soft heaps simplified'. Together they form a unique fingerprint.

  • Cite this