Two-tier relaxed heaps
| Autor: | Claus V. Jensen, Amr Elmasry, Jyrki Katajainen |
|---|---|
| Rok vydání: | 2008 |
| Předmět: | |
| Zdroj: | Acta Informatica. 45:193-210 |
| ISSN: | 1432-0525 0001-5903 |
| Popis: | 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}). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|