Two-tier relaxed heaps
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
We introduce a data structure which provides efficient heap operations with respect to the number of element comparisons performed. Let n denote the size of the heap being manipulated. Our data structure guarantees the worst-case cost of O(1) for finding the minimum, inserting an element, extracting an (unspecified) element, and replacing an element with a smaller element; and the worst-case cost of O(lg n) with at most lg n + 3 lg lg n + O(1) element comparisons for deleting an element. We thereby improve the comparison complexity of heap operations known for run-relaxed heaps and other worst-case efficient heaps. Furthermore, our data structure supports melding of two heaps of size m and n at the worst-case cost of O(min {lg m, lg n}).
A preliminary version of this paper [8] was presented at the 17th International Symposium on Algorithms and Computation held in Kolkata in December 2006.
Partially supported by the Danish Natural Science Research Council under contracts 21-02-0501 (project Practical data structures and algorithms) and 272-05-0272 (project Generic programming—algorithms and tools).
Originalsprog | Engelsk |
---|---|
Tidsskrift | Acta Informatica |
Vol/bind | 45 |
Udgave nummer | 3 |
Sider (fra-til) | 193-210 |
Antal sider | 17 |
ISSN | 0001-5903 |
DOI | |
Status | Udgivet - 14 feb. 2008 |
ID: 10118689