Handbook of Data Structures and Applications, 2nd Edition

5

Leftist Trees*

Sartaj Sahni

University of Florida

5.1Introduction

5.2Height-Biased Leftist Trees

Definition•Insertion Into a Max HBLT•Deletion of Max Element from a Max HBLT•Melding Two Max HBLTs•Initialization•Deletion of Arbitrary Element from a Max HBLT

5.3Weight-Biased Leftist Trees

Definition•Max WBLT Operations

Acknowledgments

References

5.1Introduction

A single-ended priority queue (or simply, a priority queue) is a collection of elements in which each element has a priority. There are two varieties of priority queues—max and min. The primary operations supported by a max (min) priority queue are (a) find the element with maximum (minimum) priority, (b) insert an element, and (c) delete the element whose priority is maximum (minimum). ...