Thin heaps, thick heaps

Haim Kaplan, Robert Endre Tarjan

Research output: Contribution to journalArticle

16 Scopus citations

Abstract

The Fibonacci heap was devised to provide an especially efficient implementation of Dijkstra's shortest path algorithm. Although asyptotically efficient, it is not as fast in practice as other heap implementations. Expanding on ideas of Høyer [1995], we describe three heap implementations (two versions of thin heaps and one of thick heaps) that have the same amortized efficiency as Fibonacci heaps, but need less space and promise better practical performance. As part of our development, we fill in a gap in Høyer's analysis.

Original languageEnglish (US)
Article number3
JournalACM Transactions on Algorithms
Volume4
Issue number1
DOIs
StatePublished - Mar 1 2008

All Science Journal Classification (ASJC) codes

  • Mathematics (miscellaneous)

Keywords

  • Binomial queue
  • Data structure
  • Decrease key operation
  • Fibonacci heap
  • Heap
  • Melding
  • Priority queue
  • Thick heap
  • Thin heap

Fingerprint Dive into the research topics of 'Thin heaps, thick heaps'. Together they form a unique fingerprint.

  • Cite this