We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Two-tier relaxed heaps.
- Authors
Elmasry, Amr; Jensen, Claus; Katajainen, Jyrki
- Abstract
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}).
- Subjects
CHEMICAL elements; DATA structures; SIZE; COST; COLLECTIONS; MULTIPLE comparisons (Statistics)
- Publication
Acta Informatica, 2008, Vol 45, Issue 3, p193
- ISSN
0001-5903
- Publication type
Article
- DOI
10.1007/s00236-008-0070-7