| Strictly-regular number system and data structures | |
| Authors: | Amr Elmasry, Claus Jensen, and Jyrki Katajainen |
| Published in: | Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory, Lecture Notes in Computer Science 6139, Springer-Verlag (2010), 26-37 |
| Full text: |  PDF (296 kB) |
| DOI: | 10.1007/978-3-642-13731-0_4 |
| Copyright: | © Springer-Verlag |
| Abstract: | We introduce a new number system that we call the strictly-regular system, which efficiently supports the operations: digit-increment, digit-decrement, cut, concatenate, and add. Compared to other number systems, the strictly-regular system has distinguishable properties. It is superior to the regular system for its efficient support to decrements, and superior to the extended-regular system for being more compact by using three symbols instead of four. To demonstrate the applicability of the new number system, we modify Brodal’s meldable priority queues making deletion require at most 2 lg n + O(1) element comparisons (improving the bound from 7 lg n + O(1)) while maintaining the efficiency and the asymptotic time bounds for all operations. |
| Related: |  HTML (Slides) HTML (Slides) |
| BibLATEX: | @inproceedings{EJK2010bC,
author = {Amr Elmasry and Claus Jensen and Jyrki Katajainen},
title = {Strictly-regular number system and data structures},
booktitle = {Proceedings of the 12th Scandinavian Symposium and Workshops on
Algorithm Theory},
series = {Lecture Notes in Computer Science},
volume = {6139},
publisher = {Springer-Verlag},
year = {2010},
pages = {26--37},
}
|