| Two constant-factor-optimal realizations of adaptive heapsort | |
| Authors: | Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen |
| Published in: | Proceedings of the 22nd International Workshop on Combinatorial Algorithms, Lecture Notes in Computer Science 7056, Springer-Verlag (2011), 195-208 |
| Full text: |  PDF (355 kB) |
| DOI: | 10.1007/978-3-642-25011-8_16 |
| Copyright: | © Springer-Verlag |
| Abstract: | In this paper we introduce two efficient priority queues. For both, insert requires O(1) amortized time and extract-min O(lg n) worst-case time including at most lg n + O(1) element comparisons, where n is the number of elements stored. One priority queue is based on a weak heap (array-based) and the other on a weak queue (pointer-based). In both, the main idea is to temporarily store the inserted elements in a buffer, and once it is full to move its elements to the main queue using an efficient bulk-insertion procedure. By employing the new priority queues in adaptive heapsort, we guarantee, for several measures of disorder, that the formula expressing the number of element comparisons performed by the algorithm is optimal up to the constant factor of the high-order term. We denote such performance as constant-factor optimality. Unlike some previous constant-factor-optimal adaptive sorting algorithms, adaptive heapsort relying on the developed priority queues is practically workable. |
| Related: |  HTML (Slides) HTML (Source code) HTML (Journal article) HTML (Errata) |
| BibLATEX: | @inproceedings{EEK2011aC,
author = {Stefan Edelkamp and Amr Elmasry and Jyrki Katajainen},
title = {Two constant-factor-optimal realizations of adaptive heapsort},
booktitle = {Proceedings of the 22nd International Workshop on Combinatorial
Algorithms},
series = {Lecture Notes in Computer Science},
volume = {7056},
publisher = {Springer-Verlag},
year = {2011},
pages = {195--208},
}
|