Abstract
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.
Original language | English |
---|---|
Title of host publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
Publisher | Springer |
Pages | 73-84 |
Number of pages | 12 |
DOIs | |
Publication status | Published - 2025 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 15260 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Bibliographical note
Publisher Copyright:© The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.