| Experiences with the design and implementation of space-efficient deques | |
| Authors: | Jyrki Katajainen and Bjarke Buur Mortensen |
| Published in: | Proceedings of the 5th Workshop on Algorithm Engineering, Lecture Notes in Computer Science 2141, Springer-Verlag (2001), 39–50 |
| Full text: |  PDF (159 kB) |
| DOI: | 10.1007/3-540-44688-5_4 |
| Copyright: | © Springer-Verlag |
| Abstract: | A new realization of a space-efficient deque is presented. The data structure is constructed from three singly resizable arrays, each of which is a blockwise-allocated pile (a heap without the order property). The data structure is easily explainable provided that one knows the classical heap concept. All core deque operations are performed in O(1) worst-case time. Also, general modifying operations are provided which run in O(√n) time if the structure contains n elements. Experiences with an implementation of the data structure show that, compared to an existing library implementation, the constants for some of the operations are unfavourably high, whereas others show improved running times. |
| Related: |  HTML (Slides) HTML (Source code) |
| BibLATEX: | @inproceedings{KM2001aC,
author = {Jyrki Katajainen and Bjarke Buur Mortensen},
title = {Experiences with the design and implementation of space-efficient
deques},
booktitle = {Proceedings of the 5th Workshop on Algorithm Engineering},
series = {Lecture Notes in Computer Science},
volume = {2141},
publisher = {Springer-Verlag},
year = {2001},
pages = {39--50},
}
|