A leftist heap is a node-based data structure where push, pop and merging of two heaps may all be performed in O(ln(n)) time. This depends on a property called the minimum null-path length. A null path is any path from the root of a binary tree to a node that does not have two children. The minimum null-path length is the minimum length of all null paths within a tree. If the minimum null-path length of an empty node is defined as -1, we may recursive define the minimum null-path length of a tree with a non-null root as being the mininum of one plus the minimum null-path length of the left subtree and one plus the minimum null-path length of the right subtree.

A leftist heap may be defined recursively:

• A leaf node is a leftist heap,
• A non-leaf node is a leftist heap if both subtrees are leftist heaps and the minimum null-path length of the left subtree is greater or equal to the minimum null-path length of the right subtree.

The primary operation of leftist heaps is a merge operation of two leftist heaps. Once this is defined, we may define push and pop in terms of merge operations:

• Pushing a single object onto a leftist heap is the same as merging the exisiting leftist heap with a leftist heap comprised of a single node, and
• Popping the minimum element from a leftist heap is equivalent to removing the root node and then merging the right subtree with the left subtree.

The Merge Operation