Fully Retroactive Priority Queues using Persistent Binary Search Trees
- 1 Federal University of Itajuba, Itajuba, Brazil
Published On: 14 July 2020
Copyright: © 2020 JoseWagner de Andrade Junior and Rodrigo Duarte Seabra. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Classic dynamic data structures maintains itself subject to sequence S of operations and answer queries using the latest version of the data structure. Retroactive data structures are those which allow making a modification or a query in any version of this data structure through its timeline. These data structures are used in some geometric problems and in problems related with graphs, such as the minimum path problem in dynamic graphs. This work presents how to implement a data structure to a fully retroactive version of a priority queue through persistent self-balanced binary search trees in polylogarithmic time. We use these data structures to improve the performance merging two versions of partially retroactive priority queues. The empirical analysis showed that the average performance of the proposed algorithm is better in terms of processing times than the other algorithms, despite the high constants in its complexity.
- Data Structures