OVERVIEW AND IMPLEMENTATION OF SELECTED RETROACTIVE DATA STRUCTURES
DOI:
https://doi.org/10.24867/25BE21KovacevicKeywords:
advanced data structures, retroactive data structures, queue, stack, priority queueAbstract
Retroactive data structures support modification of a series of operations performed on a given structure. In this paper, the concepts of partial and complete retroactivity are introduced, and partial retroactivity is illustrated using following structures: queue, stack and priority queue. The main focus of the paper is the description of methods of implementation of selected structures using doubly linked list and treap structure. It is concluded that execution time similar to the corresponding standard structures can be achieved.
References
[1] MIT Open Courseware, „Advanced Data Structures“, Prof. Erik Demaine, ocw.mit.edu, Stranica kursa „Napredne strukture podataka“, pristupano: maj 2023.
[2] E. D. Demaine, J. Ianoco, S. Langerma, „Retroactive Data Structures“, Proceedings of the Fifteenth Snnual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Lousiana, USA, January 11-14, 2004.
[3] E. D. Demaine, T. Kaler, Q. Liu A. Sidford, A. Yedidia, „Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing“, MIT CSAIL Cambridge, MA, USA, 2015.
[4] J. W. Andrade Junior, R. Duarte Seabra, „Fully Retroactive Priority Queues using Persistent Binary Search Trees“, Journal of Computer Science, 16(7), pp. 906-915, July 2020.
[5] GeeksForGeeks, „Complete Guide On Complexity Analysis – Data Structure and Algorithms Tutorial“, geeksforgeeks.org, članak na sajtu GeeksForGeeks, pristupano: maj 2023.
[6] S. Agarwal, P. Panwaria, „Implementation, Analysis and Application of Retroactive Data Structures“, Proc. of the Intl. Conf. on Advances in Computer Science and Electronics Engineering, 2012.
[7] Sunita, D. Garg, „Dynamizing Dijkstra: A solution to dynamic shortest path problem through retroactive priority queue“, Journal of King Saud University - Computer and Information Sciences Volume 33, Issue 3, pp. 364-373, March 2021
[2] E. D. Demaine, J. Ianoco, S. Langerma, „Retroactive Data Structures“, Proceedings of the Fifteenth Snnual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Lousiana, USA, January 11-14, 2004.
[3] E. D. Demaine, T. Kaler, Q. Liu A. Sidford, A. Yedidia, „Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing“, MIT CSAIL Cambridge, MA, USA, 2015.
[4] J. W. Andrade Junior, R. Duarte Seabra, „Fully Retroactive Priority Queues using Persistent Binary Search Trees“, Journal of Computer Science, 16(7), pp. 906-915, July 2020.
[5] GeeksForGeeks, „Complete Guide On Complexity Analysis – Data Structure and Algorithms Tutorial“, geeksforgeeks.org, članak na sajtu GeeksForGeeks, pristupano: maj 2023.
[6] S. Agarwal, P. Panwaria, „Implementation, Analysis and Application of Retroactive Data Structures“, Proc. of the Intl. Conf. on Advances in Computer Science and Electronics Engineering, 2012.
[7] Sunita, D. Garg, „Dynamizing Dijkstra: A solution to dynamic shortest path problem through retroactive priority queue“, Journal of King Saud University - Computer and Information Sciences Volume 33, Issue 3, pp. 364-373, March 2021
Downloads
Published
2023-12-05
Issue
Section
Electrotechnical and Computer Engineering
