Thin heaps, thick heaps

Haim Kaplan, Robert Endre Tarjan

Research output: Contribution to journalArticlepeer-review

18 Scopus citations


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
Issue number1
StatePublished - Mar 1 2008

All Science Journal Classification (ASJC) codes

  • Mathematics (miscellaneous)


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


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

Cite this