Partition-based Simple Heaps
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917303286759424 |
|---|---|
| author | Brodal, Gerth Stølting Iacono, John Rysgaard, Casper Moldrup Wild, Sebastian |
| author_facet | Brodal, Gerth Stølting Iacono, John Rysgaard, Casper Moldrup Wild, Sebastian |
| contents | We introduce a new family of priority-queue data structures: partition-based simple heaps. The structures consist of $O(\log n)$ doubly-linked lists; order is enforced among data in different lists, but the individual lists are unordered. Our structures have amortized $O(\log n)$ time extract-min and amortized $O(\log \log n)$ time insert and decrease-key.
The structures require nothing beyond binary search over $O(\log n)$ elements, as well as binary partitions and concatenations of linked lists in natural ways as the linked lists get too big or small. We present three different ways that these lists can be maintained in order to obtain the stated amortized running times. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_01206 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Partition-based Simple Heaps Brodal, Gerth Stølting Iacono, John Rysgaard, Casper Moldrup Wild, Sebastian Data Structures and Algorithms We introduce a new family of priority-queue data structures: partition-based simple heaps. The structures consist of $O(\log n)$ doubly-linked lists; order is enforced among data in different lists, but the individual lists are unordered. Our structures have amortized $O(\log n)$ time extract-min and amortized $O(\log \log n)$ time insert and decrease-key. The structures require nothing beyond binary search over $O(\log n)$ elements, as well as binary partitions and concatenations of linked lists in natural ways as the linked lists get too big or small. We present three different ways that these lists can be maintained in order to obtain the stated amortized running times. |
| title | Partition-based Simple Heaps |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2603.01206 |