Retroactive Monotonic Priority Queues via Range Searching
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913031357726720 |
|---|---|
| author | Castro, Lucas de Freitas, Rosiane |
| author_facet | Castro, Lucas de Freitas, Rosiane |
| contents | The best-known fully retroactive priority queue costs $O(\log^2 m \log \log m)$ time per operation and uses $O(m \log m)$ space, where $m$ is the number of operations performed on the data structure. In contrast, standard (non-retroactive) priority queues can cost $O(\log m)$ time per operation and use $O(m)$ space. So far, it remains open whether these bounds can be achieved for fully retroactive priority queues.
In this work, we study a restricted variant of priority queues known as monotonic priority queues. First, we show that finding the minimum in a retroactive monotonic priority queue is a special case of the range-searching problem. Then, we design a fully retroactive monotonic priority queue that costs $O(\log m)$ time per operation and uses $O(m)$ space, achieving the same bounds as a standard priority queue. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_09892 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Retroactive Monotonic Priority Queues via Range Searching Castro, Lucas de Freitas, Rosiane Data Structures and Algorithms Computational Geometry The best-known fully retroactive priority queue costs $O(\log^2 m \log \log m)$ time per operation and uses $O(m \log m)$ space, where $m$ is the number of operations performed on the data structure. In contrast, standard (non-retroactive) priority queues can cost $O(\log m)$ time per operation and use $O(m)$ space. So far, it remains open whether these bounds can be achieved for fully retroactive priority queues. In this work, we study a restricted variant of priority queues known as monotonic priority queues. First, we show that finding the minimum in a retroactive monotonic priority queue is a special case of the range-searching problem. Then, we design a fully retroactive monotonic priority queue that costs $O(\log m)$ time per operation and uses $O(m)$ space, achieving the same bounds as a standard priority queue. |
| title | Retroactive Monotonic Priority Queues via Range Searching |
| topic | Data Structures and Algorithms Computational Geometry |
| url | https://arxiv.org/abs/2508.09892 |