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 |
Αρχεία | Μέγεθος | Μορφότυπο | Προβολή |
---|---|---|---|
Δεν υπάρχουν αρχεία που σχετίζονται με αυτό το τεκμήριο. |