Hollow Heaps

Author(s): Hansen, Thomas D; Kaplan, Haim; Tarjan, Robert E; Zwick, Uri

Download

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1fc1s

Full metadata record

DC Field	Value	Language
dc.contributor.author	Hansen, Thomas D	-
dc.contributor.author	Kaplan, Haim	-
dc.contributor.author	Tarjan, Robert E	-
dc.contributor.author	Zwick, Uri	-
dc.date.accessioned	2021-10-08T19:47:32Z	-
dc.date.available	2021-10-08T19:47:32Z	-
dc.date.issued	2015	en_US
dc.identifier.citation	Hansen, Thomas Dueholm, Haim Kaplan, Robert E. Tarjan, and Uri Zwick. "Hollow Heaps." In International Colloquium on Automata, Languages, and Programming (2015): pp. 689-700. doi:10.1007/978-3-662-47672-7_56	en_US
dc.identifier.uri	http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=FF2304D6916DFC582B7F3CF6BDFD1344?doi=10.1.1.697.3072&rep=rep1&type=pdf	-
dc.identifier.uri	http://arks.princeton.edu/ark:/88435/pr1fc1s	-
dc.description.abstract	amortized time. Hollow heaps are by far the simplest structure to achieve this. Hollow heaps combine two novel ideas: the use of lazy deletion and re-insertion to do decrease-key operations, and the use of a dag (directed acyclic graph) instead of a tree or set of trees to represent a heap. Lazy deletion produces hollow nodes (nodes without items), giving the data structure its name.	en_US
dc.format.extent	689 - 700	en_US
dc.language.iso	en_US	en_US
dc.relation.ispartof	International Colloquium on Automata, Languages, and Programming	en_US
dc.rights	Author's manuscript	en_US
dc.title	Hollow Heaps	en_US
dc.type	Conference Article	en_US
dc.identifier.doi	10.1007/978-3-662-47672-7_56	-
pu.type.symplectic	http://www.symplectic.co.uk/publications/atom-terms/1.0/journal-article	en_US

Files in This Item:

File	Description	Size	Format
HollowHeapsProgramming.pdf		402.86 kB	Adobe PDF	View/Download