Strict Fibonacci heaps

dc.contributor.author	Brodal, GS	en
dc.contributor.author	Lagogiannis, G	en
dc.contributor.author	Tarjan, RE	en
dc.date.accessioned	2014-06-06T06:52:06Z
dc.date.available	2014-06-06T06:52:06Z
dc.date.issued	2012	en
dc.identifier.issn	07378017	en
dc.identifier.uri	http://dx.doi.org/10.1145/2213977.2214082	en
dc.identifier.uri	http://62.217.125.90/xmlui/handle/123456789/5843
dc.subject	data structures	en
dc.subject	decrease-key	en
dc.subject	heaps	en
dc.subject	meld	en
dc.subject	worst-case complexity	en
dc.subject.other	decrease-key	en
dc.subject.other	Fibonacci heap	en
dc.subject.other	heaps	en
dc.subject.other	Linear spaces	en
dc.subject.other	meld	en
dc.subject.other	Pigeonhole principle	en
dc.subject.other	RAM model	en
dc.subject.other	Time bound	en
dc.subject.other	Worst-case complexity	en
dc.subject.other	Data structures	en
dc.subject.other	Computation theory	en
dc.title	Strict Fibonacci heaps	en
heal.type	conferenceItem	en
heal.identifier.primary	10.1145/2213977.2214082	en
heal.publicationDate	2012	en
heal.abstract	We present the first pointer-based heap implementation with time bounds matching those of Fibonacci heaps in the worst case. We support make-heap, insert, find-min, meld and decrease-key in worst-case O(1) time, and delete and delete-min in worst-case O(lg n) time, where n is the size of the heap. The data structure uses linear space. A previous, very complicated, solution achieving the same time bounds in the RAM model made essential use of arrays and extensive use of redundant counter schemes to maintain balance. Our solution uses neither. Our key simplification is to discard the structure of the smaller heap when doing a meld. We use the pigeonhole principle in place of the redundant counter mechanism. © 2012 ACM.	en
heal.journalName	Proceedings of the Annual ACM Symposium on Theory of Computing	en
dc.identifier.doi	10.1145/2213977.2214082	en
dc.identifier.spage	1177	en
dc.identifier.epage	1184	en