# leftist tree

(data structure)

**Definition:**
A *priority queue* implemented with a variant of a *binary tree*. Every *node* has a count which is the distance to the nearest *leaf*. In addition to the *heap property*, leftist trees are kept so the right *descendant* of each node has the shorter distance to a leaf.

**Generalization** (I am a kind of ...)

*priority queue*.

**Aggregate child** (... is a part of or used in me.)

*binary tree*, *heap property*.

*Note:
These are called "leftist" because the left subtrees are usually taller than the right subtrees.*

Author: PEB

## Implementation

merge and delete (C and Pascal) which use distance (C and Pascal), insert (C and Pascal)

Go to the
Dictionary of Algorithms and Data
Structures home page.

If you have suggestions, corrections, or comments, please get in touch
with Paul Black.

Entry modified 12 February 2019.

HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:

Paul E. Black, "leftist tree", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 12 February 2019. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/leftisttree.html