Amortized Analysis of Leftist Heaps

Berry Schoenmakers

doi:10.1007/978-3-031-75783-9_3

Amortized Analysis of Leftist Heaps

Berry Schoenmakers (Corresponding author)

Coding Theory and Cryptology

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

1 Citation (Scopus)

5 Downloads (Pure)

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	Principles of Verification: Cycling the Probabilistic Landscape
Subtitle of host publication	Essays Dedicated to Joost-Pieter Katoen on the Occasion of His 60th Birthday
Editors	Nils Jansen, Sebastian Junges, Benjamin Lucien Kaminski, Christoph Matheja, Thomas Noll, Tim Quatmann, Mariëlle Stoelinga, Matthias Volk
Publisher	Springer
Chapter	3
Pages	73-84
Number of pages	12
Volume	1
ISBN (Electronic)	978-3-031-75783-9
ISBN (Print)	978-3-031-75782-2
DOIs	https://doi.org/10.1007/978-3-031-75783-9_3
Publication status	Published - 2025

Publication series

Name	Lecture Notes in Computer Science
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.

Access to Document

10.1007/978-3-031-75783-9_3

Cite this

Schoenmakers, B. (2025). Amortized Analysis of Leftist Heaps. In N. Jansen, S. Junges, B. L. Kaminski, C. Matheja, T. Noll, T. Quatmann, M. Stoelinga, & M. Volk (Eds.), Principles of Verification: Cycling the Probabilistic Landscape: Essays Dedicated to Joost-Pieter Katoen on the Occasion of His 60th Birthday (Vol. 1, pp. 73-84). (Lecture Notes in Computer Science; Vol. 15260 LNCS). Springer. https://doi.org/10.1007/978-3-031-75783-9_3

Schoenmakers, Berry. / Amortized Analysis of Leftist Heaps. Principles of Verification: Cycling the Probabilistic Landscape: Essays Dedicated to Joost-Pieter Katoen on the Occasion of His 60th Birthday. editor / Nils Jansen ; Sebastian Junges ; Benjamin Lucien Kaminski ; Christoph Matheja ; Thomas Noll ; Tim Quatmann ; Mariëlle Stoelinga ; Matthias Volk. Vol. 1 Springer, 2025. pp. 73-84 (Lecture Notes in Computer Science).

@inbook{3795a3799c1247dd893a1b144c29b2ea,

title = "Amortized Analysis of Leftist Heaps",

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.",

author = "Berry Schoenmakers",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.",

year = "2025",

doi = "10.1007/978-3-031-75783-9\_3",

language = "English",

isbn = "978-3-031-75782-2",

volume = "1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "73--84",

editor = "Nils Jansen and Sebastian Junges and Kaminski, \{Benjamin Lucien\} and Christoph Matheja and Thomas Noll and Tim Quatmann and Mari{\"e}lle Stoelinga and Matthias Volk",

booktitle = "Principles of Verification: Cycling the Probabilistic Landscape",

address = "Germany",

}

Schoenmakers, B 2025, Amortized Analysis of Leftist Heaps. in N Jansen, S Junges, BL Kaminski, C Matheja, T Noll, T Quatmann, M Stoelinga & M Volk (eds), Principles of Verification: Cycling the Probabilistic Landscape: Essays Dedicated to Joost-Pieter Katoen on the Occasion of His 60th Birthday. vol. 1, Lecture Notes in Computer Science, vol. 15260 LNCS, Springer, pp. 73-84. https://doi.org/10.1007/978-3-031-75783-9_3

Amortized Analysis of Leftist Heaps. / Schoenmakers, Berry (Corresponding author).
Principles of Verification: Cycling the Probabilistic Landscape: Essays Dedicated to Joost-Pieter Katoen on the Occasion of His 60th Birthday. ed. / Nils Jansen; Sebastian Junges; Benjamin Lucien Kaminski; Christoph Matheja; Thomas Noll; Tim Quatmann; Mariëlle Stoelinga; Matthias Volk. Vol. 1 Springer, 2025. p. 73-84 (Lecture Notes in Computer Science; Vol. 15260 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

TY - CHAP

T1 - Amortized Analysis of Leftist Heaps

AU - Schoenmakers, Berry

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

PY - 2025

Y1 - 2025

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/85212097128

U2 - 10.1007/978-3-031-75783-9_3

DO - 10.1007/978-3-031-75783-9_3

M3 - Chapter

AN - SCOPUS:85212097128

SN - 978-3-031-75782-2

VL - 1

T3 - Lecture Notes in Computer Science

SP - 73

EP - 84

BT - Principles of Verification: Cycling the Probabilistic Landscape

A2 - Jansen, Nils

A2 - Junges, Sebastian

A2 - Kaminski, Benjamin Lucien

A2 - Matheja, Christoph

A2 - Noll, Thomas

A2 - Quatmann, Tim

A2 - Stoelinga, Mariëlle

A2 - Volk, Matthias

PB - Springer

ER -

Schoenmakers B. Amortized Analysis of Leftist Heaps. In Jansen N, Junges S, Kaminski BL, Matheja C, Noll T, Quatmann T, Stoelinga M, Volk M, editors, Principles of Verification: Cycling the Probabilistic Landscape: Essays Dedicated to Joost-Pieter Katoen on the Occasion of His 60th Birthday. Vol. 1. Springer. 2025. p. 73-84. (Lecture Notes in Computer Science). doi: 10.1007/978-3-031-75783-9_3