Amortized Analysis of Leftist Heaps

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

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 languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
Pages73-84
Number of pages12
DOIs
Publication statusPublished - 2025

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume15260 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.

Fingerprint

Dive into the research topics of 'Amortized Analysis of Leftist Heaps'. Together they form a unique fingerprint.

Cite this