# Leftist-trees

An implementation of Leftist Trees.

Leftist trees are an efficient implementation of binary
heaps. Regular
(completely balanced) binary heaps are tricky, and in most cases near
impossible, to implement in functional languages because of the need for
constant-time access to the last element in the tree (that element being the
node in the bottom-most level of the tree, furthest to the right). Leftist
trees avoid this by replacing this "balanced" requirement with the
requirement that the right-most spine of the tree be small relative to the
overal number of elements in the tree. Since the fundamental heap operations
(insert, delete-min) only recur on the right spine of the tree in question,
this guarantees that these operations are O(log(n)), where n is the size of
the tree.

Leftist trees look like this:

(rank root left right)

where "rank" is defined to be the length of the right spine of the tree,
"root" is the root element of the tree, "left" is the left sub-tree, and
"right" is the right sub-tree.

Leftist trees are heap-ordered, and they are "balanced" in a loose
sense. In particular, the size of the tree is at least as big as an
exponential function of the rank:

size(tree) >= 2^(rank(tree)) - 1,

or, solving for rank(tree) and noting that the rank is always an
integer,

rank(tree) <= floor(log(size(tree) + 1)).

The important tree operations are INSERT-LT, FIND-MIN-LT, and
DELETE-MIN-LT. A useful function called BUILD-LT is also provided, which
constructs a leftist tree from a list. An important constant is *EMPTY-LT*,
which is the empty tree (for this implementation, just NIL).

To learn how to use the trees, see :DOC LEFTIST-TREE-FNS. To see some
useful theorems about leftist trees, including the rank bound above, see :DOC
LEFTIST-TREE-THMS.

Sources: - Okasaki, Chris. Purely Functional Data Structures. Cambridge,
U.K.: Cambridge UP, 1998. 17-20. Print.

### Subtopics

- Leftist-tree-sort
- Functions and theorems about leftist tree-based heapsort.
- Leftist-tree-fns
- All functions and constants related to leftist trees.
- Leftist-tree-thms
- Useful theorems about leftist trees.
- How-many-lt
- Returns the number of times an object occurs in a leftist tree
- Ltree-sort
- Sort an input list using leftist tree-based heapsort