Two-tier relaxed heaps
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Two-tier relaxed heaps. / Elmasry, Amr; Jensen, Claus; Katajainen, Jyrki.
In: Acta Informatica, Vol. 45, No. 3, 14.02.2008, p. 193-210.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Two-tier relaxed heaps
AU - Elmasry, Amr
AU - Jensen, Claus
AU - Katajainen, Jyrki
PY - 2008/2/14
Y1 - 2008/2/14
N2 - 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).
AB - 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).
U2 - 10.1007/s00236-008-0070-7
DO - 10.1007/s00236-008-0070-7
M3 - Journal article
VL - 45
SP - 193
EP - 210
JO - Acta Informatica
JF - Acta Informatica
SN - 0001-5903
IS - 3
ER -
ID: 10118689