# 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 16 November 2009.

HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:

Paul E. Black, "leftist tree", in
*Dictionary of Algorithms and Data Structures* [online], Vreda Pieterse and Paul E. Black, eds. 16 November 2009. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/leftisttree.html