Thin heaps, thick heaps

Haim Kaplan; Robert Endre Tarjan

doi:10.1145/1328911.1328914

Thin heaps, thick heaps

Haim Kaplan, Robert Endre Tarjan

Research output: Contribution to journal › Article › peer-review

18 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 language	English (US)
Article number	3
Journal	ACM Transactions on Algorithms
Volume	4
Issue number	1
DOIs	https://doi.org/10.1145/1328911.1328914
State	Published - 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

Access to Document

10.1145/1328911.1328914

Cite this

@article{860e9699e8ce444383fc8207252b3456,

title = "Thin heaps, thick heaps",

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{\o}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{\o}yer's analysis.",

keywords = "Binomial queue, Data structure, Decrease key operation, Fibonacci heap, Heap, Melding, Priority queue, Thick heap, Thin heap",

author = "Haim Kaplan and Tarjan, {Robert Endre}",

year = "2008",

month = mar,

day = "1",

doi = "10.1145/1328911.1328914",

language = "English (US)",

volume = "4",

journal = "ACM Transactions on Algorithms",

issn = "1549-6325",

publisher = "Association for Computing Machinery (ACM)",

number = "1",

}

TY - JOUR

T1 - Thin heaps, thick heaps

AU - Kaplan, Haim

AU - Tarjan, Robert Endre

PY - 2008/3/1

Y1 - 2008/3/1

N2 - 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.

AB - 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.

KW - Binomial queue

KW - Data structure

KW - Decrease key operation

KW - Fibonacci heap

KW - Heap

KW - Melding

KW - Priority queue

KW - Thick heap

KW - Thin heap

UR - http://www.scopus.com/inward/record.url?scp=42149150504&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=42149150504&partnerID=8YFLogxK

U2 - 10.1145/1328911.1328914

DO - 10.1145/1328911.1328914

M3 - Article

AN - SCOPUS:42149150504

SN - 1549-6325

VL - 4

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 1

M1 - 3

ER -

Thin heaps, thick heaps

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this