Amortized Analysis of Leftist Heaps
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917840239460352 |
|---|---|
| author | Schoenmakers, Berry |
| author_facet | Schoenmakers, Berry |
| contents | Leftist heaps and skew heaps are two well-known data structures for mergeable priority queues. Leftist heaps are constructed for efficiency in the worst-case sense whereas skew heaps are self-adjusting, designed for efficiency in the amortized sense. In this paper, we analyze the amortized complexity of leftist heaps to initiate a full performance comparison with skew heaps. We consider both the leftist heaps originally developed by Crane and Knuth, which are also referred to as rank-biased (or, height-biased) leftist heaps, and the weight-biased leftist heaps introduced by Cho and Sahni. We show how weight-biased leftist heaps satisfy the same exact amortized bounds as skew heaps. With these matching bounds we establish a nice trade-off in which storage of weights is used to limit the worst-case complexity of leftist heaps, without affecting the amortized complexity compared to skew heaps. For rank-biased leftist heaps, we obtain the same amortized lower bounds as for skew heaps, but whether these bounds are tight is left as an open problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_11051 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Amortized Analysis of Leftist Heaps Schoenmakers, Berry Data Structures and Algorithms Leftist heaps and skew heaps are two well-known data structures for mergeable priority queues. Leftist heaps are constructed for efficiency in the worst-case sense whereas skew heaps are self-adjusting, designed for efficiency in the amortized sense. In this paper, we analyze the amortized complexity of leftist heaps to initiate a full performance comparison with skew heaps. We consider both the leftist heaps originally developed by Crane and Knuth, which are also referred to as rank-biased (or, height-biased) leftist heaps, and the weight-biased leftist heaps introduced by Cho and Sahni. We show how weight-biased leftist heaps satisfy the same exact amortized bounds as skew heaps. With these matching bounds we establish a nice trade-off in which storage of weights is used to limit the worst-case complexity of leftist heaps, without affecting the amortized complexity compared to skew heaps. For rank-biased leftist heaps, we obtain the same amortized lower bounds as for skew heaps, but whether these bounds are tight is left as an open problem. |
| title | Amortized Analysis of Leftist Heaps |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.11051 |