Research Article Open Access

Fully Retroactive Priority Queues using Persistent Binary Search Trees

JoseWagner de Andrade Junior1 and Rodrigo Duarte Seabra1
  • 1 Federal University of Itajuba, Itajuba, Brazil
Journal of Computer Science
Volume 16 No. 7, 2020, 906-915

DOI: https://doi.org/10.3844/jcssp.2020.906.915

Submitted On: 20 April 2020
Published On: 14 July 2020

How to Cite: Junior, J. A. & Seabra, R. D. (2020). Fully Retroactive Priority Queues using Persistent Binary Search Trees. Journal of Computer Science, 16(7), 906-915. https://doi.org/10.3844/jcssp.2020.906.915

Abstract

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.

Download

Keywords

  • Retroactivity
  • Data Structures