Leftist Heap: A Heap Born to Merge

A leftist heap is a heap data structure designed around one especially important operation: merging two heaps. Ordinary binary heaps are excellent at inserting elements and removing the minimum or maximum, but combining two existing binary heaps is not naturally efficient. A leftist heap addresses that problem by organizing its tree so that merging can proceed mainly along a short path called the right spine.

The central idea is straightforward:

1. Preserve the usual heap-order property.
2. Add a structural rule called the leftist property.
3. Merge heaps recursively along their right spines.
4. Restore the leftist property after each recursive merge by swapping children when necessary.

This article explains the heap invariant, complete binary-tree representations, leftist heaps, right-spine merging, insertion, extraction, heapify, sift-up, sift-down, complexity, and the difference between heaps and binary search trees. The emphasis is on understanding why a leftist heap can be described as “a heap born to merge.”

1. What Is a Heap?​

A heap is a tree-based structure that maintains a particular ordering between each node and its children. There are two common forms:

• A min-heap keeps the smallest element at the root.
• A max-heap keeps the largest element at the root.

In a min-heap, every parent is less than or equal to its children. If a node contains p, and its children contain a and b, the required relationships are:

p <= a
p <= b

The children do not need to be ordered relative to each other. For example, this is a valid min-heap:

        2
      /   \
     5     3
    / \   /
   9   7 8

The root is 2, the smallest value. However, the left child 5 is larger than the right child 3; that is completely acceptable. A heap is not required to sort all elements from left to right.

A max-heap reverses the comparison. Every parent is greater than or equal to its children:

        9
      /   \
     7     8
    / \   /
   2   5 3

The root is the largest value.

The heap-order property is local: it compares each parent with its children. That local rule is enough to guarantee that the minimum of a min-heap, or the maximum of a max-heap, is available at the root.

This local ordering is the first important invariant. A valid operation may change the shape of the tree, but it must never leave a parent in the wrong relationship with its children.

2. Complete Binary Trees and Array Representation​

A traditional binary heap is usually stored as a complete binary tree. A complete binary tree fills every level from left to right, except possibly the final level, which is also filled from left to right.

For example, this tree is complete:

          4
       /     \
      7       6
    /  \     / \
   9    8   10  12
  /
 15

The final level begins at the far left, with no gaps before the node containing 15.

Completeness matters because it allows the tree to be represented compactly in an array. With zero-based indexing:

• The left child of the node at index i is at index 2i + 1.
• The right child is at index 2i + 2.
• The parent is at index floor((i - 1) / 2) for i > 0.

The previous tree can be represented as:

[4, 7, 6, 9, 8, 10, 12, 15]

The array does not store explicit child pointers. The index formulas recover the tree relationships.

A complete binary tree with n nodes has height O(log n). This short height is what makes ordinary binary-heap insertion and extraction efficient. However, completeness is not the only possible structural strategy for a heap. A leftist heap uses linked nodes and follows a different shape rule. It does not need to remain complete.

This distinction is important. “Heap” describes the priority-order invariant, but different heap families can use different shape invariants and representations. An array-based binary heap emphasizes completeness. A leftist heap emphasizes a short right spine.

3. The Two Invariants of a Leftist Heap​

A leftist heap maintains two important invariants.

3.1 Heap-Order Property​

The first invariant is the ordinary heap-order property. For a min-leftist heap, the key stored at a node is no greater than the keys stored at either child:

key(node) <= key(node.left)
key(node) <= key(node.right)

The root therefore contains the minimum element. For a max-leftist heap, the inequalities are reversed, and the root contains the maximum.

3.2 Leftist Property​

The second invariant is the leftist property. It is based on the null path length, often abbreviated as npl.

For a node, the null path length can be defined as the length of a shortest path from that node to a missing child. One common convention is:

npl(null) = -1
npl(leaf) = 0
npl(node) = 1 + min(npl(node.left), npl(node.right))

Some implementations use npl(null) = 0 instead. That changes the numeric values by one but not the algorithmic idea. The convention must simply be used consistently.

The leftist property requires:

npl(left child) >= npl(right child)

at every node.

This means that the right subtree is never “more structurally deep” than the left subtree, according to null path length. The right side is deliberately kept short. That is why the path obtained by repeatedly following right-child pointers—the right spine—is the important path in a leftist heap.

A leftist heap can look unbalanced in the usual binary-search-tree sense. Its left branches may be long, and the whole tree need not be complete. What it controls is the right side, because merging repeatedly travels there.

4. Why the Right Spine Matters​

Suppose a leftist heap has the following shape:

          2
        /   \
       5     8
      / \   /
     9   7 12
    /
   14

The right spine follows:

2 -> 8 -> null

It is short even though the left subtree is deeper. In a leftist heap, the leftist property guarantees that the right spine has logarithmic length relative to the number of nodes.

This is the structural reason merging can be efficient. Instead of rebuilding every node or scanning all elements, a merge operation follows only the right spines of the participating heaps. The relevant work is proportional to the height of those spines, which is O(log n) for a heap containing n nodes.

The leftist property is therefore not mainly about making the entire tree balanced. It is about making the particular route used by merge short.

The name can be slightly misleading if it is interpreted as “the tree always leans left by number of nodes.” That is not the rule. The property compares null path lengths, not subtree sizes. A leftist heap is left-biased in the rank measure that matters to merging.

5. The Central Operation: Merge or Meld​

The key operation in a leftist heap is often called merge, meld, or meld. It combines two leftist heaps into one leftist heap while preserving both invariants.

Assume two min-leftist heaps, A and B.

The merge procedure follows these steps:

1. If either heap is empty, return the other heap.
2. Compare the roots.
3. Make the smaller root the root of the merged heap.
4. Recursively merge the chosen root’s right subtree with the other heap.
5. Check the leftist property.
6. If the left child has a smaller null path length than the right child, swap the children.
7. Recompute the chosen root’s null path length.
8. Return the resulting root.

The root comparison preserves heap order. The child swap preserves the leftist property.

5.1 A Small Merge Example​

Consider these two min-heaps:

Heap A:          3
                / \
               8   10

Heap B:          5
                / \
               7   12

The roots are 3 and 5. Since 3 is smaller, it remains the root. The algorithm recursively merges the right subtree of 3, which contains 10, with Heap B.

The recursive comparison is now between 10 and 5. Since 5 is smaller, 5 becomes the root of that merged portion. Its right subtree is then merged recursively with the appropriate subtree from the other heap.

At each step, the algorithm works on a right child rather than independently combining every subtree. After the recursive call returns, the current node checks its null path lengths. If its right child has a larger null path length than its left child, the two children are exchanged.

The final shape depends on the null path lengths, not merely on the numeric values. Different valid implementations or tie-breaking choices can produce different shapes while maintaining the same heap-order and leftist invariants.

5.2 Pseudocode for Min-Leftist Merging​

Using null as the empty heap and npl as the stored null path length:

merge(a, b):
    if a is null:
        return b
    if b is null:
        return a

    if a.key > b.key:
        swap(a, b)

    a.right = merge(a.right, b)

    if npl(a.left) < npl(a.right):
        swap(a.left, a.right)

    a.npl = 1 + min(npl(a.left), npl(a.right))

    return a

For a max-leftist heap, replace the root comparison with the opposite comparison. The structural steps remain the same.

The code is short because the leftist property does much of the work. The algorithm does not need a separate global rebalancing procedure. Each recursive return repairs the local node before returning upward.

6. Why Swapping Children Is Safe​

A natural question is: if we swap a node’s left and right children, do we damage heap order?

No. Heap order only requires that the parent be correctly ordered relative to each child. It does not require the left child to be smaller than the right child. If a parent is smaller than both children before the swap, it is still smaller than both children afterward.

For example:

        4
      /   \
     9     6

This satisfies min-heap order because 4 <= 9 and 4 <= 6. Swapping the children gives:

        4
      /   \
     6     9

The heap-order property still holds. The swap is therefore available as a structural tool for enforcing the leftist property without changing the priority order.

This is an important distinction between a heap and a binary search tree. A binary search tree normally requires every key in the left subtree to be smaller than the node and every key in the right subtree to be larger. Swapping children in a binary search tree could violate that rule. A heap has no such left-versus-right ordering requirement.

7. Insertion in a Leftist Heap​

Insertion can be implemented using merge. To insert a new key:

1. Create a one-node leftist heap containing the new key.
2. Meld it with the existing heap.
3. Return the merged heap.

A one-node heap is already valid:

  6

Its heap-order property is trivially satisfied because it has no children. Its null path length is set according to the chosen convention.

Suppose the existing min-leftist heap is:

        2
      /   \
     5     9

Insert 4 by creating:

4

Then merge the singleton heap with the existing heap. The root 2 remains the root because it is smaller than 4. The recursive merge proceeds down the right side, and child swapping repairs the leftist property as needed.

The insertion operation therefore has the same asymptotic cost as a merge. If the heap has n nodes, insertion takes O(log n) time in the usual leftist-heap analysis.

This approach is conceptually useful: insertion is not a separate structural algorithm. It is simply a special case of melding a large heap with a one-element heap.

8. Extracting the Minimum or Maximum​

For a min-leftist heap, the minimum is always at the root. To extract it:

1. Save the root’s key.
2. Let the root’s left and right subtrees become two separate leftist heaps.
3. Merge those two subheaps.
4. Return the saved key and the merged heap.

For example:

        2
      /   \
     5     7
    / \   /
   9   8 10

The minimum is 2. After removing it, the remaining heaps are:

Left subtree:       5
                   / \
                  9   8

Right subtree:      7
                   /
                  10

The new heap is obtained by melding these two subheaps. The result remains a min-leftist heap.

For a max-leftist heap, the same procedure extracts the root maximum. The operation is often called deleteMin for min-heaps or deleteMax for max-heaps.

The extraction cost is dominated by the merge of the two root subtrees, so it is O(log n) for a heap of n nodes.

9. Finding the Root Versus Finding Arbitrary Values​

A heap provides fast access to one extreme element:

• A min-heap provides the minimum at the root.
• A max-heap provides the maximum at the root.

Reading the root is O(1) because it is stored at the top. Removing it is more expensive because the remaining subtrees must be merged or repaired.

A heap does not generally support fast search for an arbitrary key. If the required task is “find the smallest item,” a heap is an excellent fit. If the task is “find whether the value 42 exists” or “list all values in sorted order,” a heap may not be the most appropriate structure.

This difference is central when comparing heaps with binary search trees. A binary search tree is organized for directional search by key. A heap is organized for immediate access to one priority extreme.

10. Sift-Up and Sift-Down in Ordinary Binary Heaps​

Because the broader heap family is useful for comparison, it is worth reviewing two standard repair operations used in complete-array binary heaps: sift-up and sift-down.

10.1 Sift-Up​

Insertion into an ordinary binary heap usually places the new item in the next available array position. This preserves completeness, but the new item may violate heap order with its parent.

For a min-heap, compare the new item with its parent. If the new item is smaller, swap them and continue upward.

Example: insert 3 into:

        4
      /   \
     7     6

The next complete-tree position is the left child of 7:

        4
      /   \
     7     6
    /
   3

The 3 is smaller than 7, so swap:

        4
      /   \
     3     6
    /
   7

Now 3 is smaller than its parent 4, so swap again:

        3
      /   \
     4     6
    /
   7

The heap-order property is restored. Since the complete-tree height is O(log n), sift-up takes O(log n) time.

A max-heap uses the opposite comparison: a newly inserted item moves upward while it is greater than its parent.

10.2 Sift-Down​

Extraction from an ordinary binary heap usually moves the last array item to the root. This preserves completeness but may violate heap order at the root.

For a min-heap, compare the current node with its smaller child. If the current node is larger, swap it with that smaller child and continue downward.

Suppose the root becomes 9 after extraction:

        9
      /   \
     4     6
    / \
   7   8

The smaller child of 9 is 4, so swap:

        4
      /   \
     9     6
    / \
   7   8

Now compare 9 with its children 7 and 8. The smaller child is 7, so swap again:

        4
      /   \
     7     6
    / \
   9   8

The heap order is restored. Sift-down also takes O(log n) time.

Leftist heaps do not usually use array-style sift-up and sift-down as their primary operations. Their defining repair pattern is recursive merge along the right spine. Still, the comparison is useful: both structures preserve heap order locally, but they use different structural strategies.

11. Heapify and Building a Heap​

Heapify means transforming a collection into a valid heap.

For an array-based binary heap, a common bottom-up method starts at the last internal node and applies sift-down to each internal node, moving toward the root. Although a single sift-down can cost O(log n), the complete bottom-up construction runs in O(n) time because most nodes are close to the leaves and therefore move only a short distance.

A simpler alternative is repeated insertion. Starting with an empty heap, insert all n elements one at a time. Since each insertion costs O(log n), this approach takes O(n log n) time in the worst case.

A leftist heap can also be built by repeatedly melding singleton heaps. That straightforward strategy has O(n log n) worst-case behavior when each new singleton is merged into the accumulated heap. The defining operation remains meld: a collection of leftist heaps can be combined by repeated merges.

When choosing a construction method, the practical question is whether the input is already available as a batch or whether elements arrive over time. Bottom-up array heapify is attractive for a known batch. Repeated insertion is natural for online data. A leftist heap is especially attractive when separate priority queues must frequently be combined.

12. Complexity of Leftist-Heap Operations​

For a leftist heap containing n nodes, the usual complexities are:

The exact logarithmic expression for merging two heaps can be described in terms of their sizes; the important practical point is that the operation follows short right spines rather than traversing all nodes.

Space usage is O(n) for n linked nodes. Unlike an array-based complete binary heap, a leftist heap stores explicit child references and a null path length or equivalent rank value in each node.

The leftist property is what supports the logarithmic bound. Without that property, repeatedly following right children could encounter a long chain and merging could degrade toward linear time.

13. Leftist Heaps Versus Ordinary Binary Heaps​

Both structures provide heap-order access to an extreme element, but they optimize different structural goals.

Ordinary Binary Heap​

An ordinary binary heap:

• Is usually a complete binary tree.
• Is naturally stored in an array.
• Supports insertion and root extraction in O(log n) time.
• Supports bottom-up heapify in O(n) time.
• Does not provide a natural efficient merge of two existing heaps.

If an application mostly maintains one priority queue, an ordinary binary heap is often a simple and efficient choice.

Leftist Heap​

A leftist heap:

• Is usually represented with linked nodes.
• Need not be complete.
• Stores a leftist rank such as null path length.
• Makes merge the central operation.
• Implements insertion and extraction through merge.
• Has a short right spine because of the leftist property.

If an application repeatedly combines queues, leftist heaps offer a structure designed for that workflow.

The trade-off is that linked nodes require pointers and may have less compact memory behavior than a contiguous array. The best structure depends on the operation mix, implementation environment, and memory requirements.

14. Leftist Heaps Versus Binary Search Trees​

A leftist heap and a binary search tree are both binary tree structures, but their invariants serve different purposes.

A binary search tree normally maintains:

all keys in left subtree < node key
all keys in right subtree > node key

This ordering supports search by comparing a target with the current node and choosing a direction. In a well-shaped binary search tree, search, insertion, and deletion can be logarithmic.

A heap maintains only parent-child priority ordering:

parent <= child       for a min-heap
parent >= child       for a max-heap

The left and right subtrees are not globally sorted. There is no general binary-search direction for an arbitrary target.

A leftist heap adds the leftist property, but that property is not a search-tree property. It controls null path lengths and keeps the right spine short. It does not place values into left and right key ranges.

A useful rule of thumb is:

• Choose a heap when you need repeated priority access.
• Choose a binary search tree when you need ordered search, predecessor or successor operations, or traversal in key order.
• Consider a leftist heap when you need priority access plus frequent heap merging.

15. Min-Leftist Heaps and Max-Leftist Heaps​

The leftist structural rule is independent of whether the heap is a min-heap or max-heap.

For a min-leftist heap:

parent key <= child keys

The root is the minimum, and the operation is commonly called deleteMin.

For a max-leftist heap:

parent key >= child keys

The root is the maximum, and the operation is commonly called deleteMax.

In both versions:

npl(left) >= npl(right)

The merge algorithm differs only in which root wins the comparison. For a min-leftist heap, the smaller root becomes the result root. For a max-leftist heap, the larger root becomes the result root.

For example, when merging roots 4 and 9:

• In a min-leftist heap, 4 remains above 9.
• In a max-leftist heap, 9 remains above 4.

After that choice, the recursive right-spine merge and possible child swap follow the same structural pattern.

16. Understanding the Recursive Merge Step by Step​

It helps to view merge as a controlled descent followed by local repair.

Suppose the current roots are a and b in a min-leftist heap. If b is smaller, swap the references so a is the smaller root. This ensures that a can safely become the root of the result.

The unresolved work is not placed arbitrarily. The algorithm recursively assigns:

a.right = merge(a.right, b)

The left subtree of a is left untouched during this step. Once the recursive merge returns, a.right is a valid leftist heap, but its null path length may make the current node violate the leftist property.

The algorithm then checks:

if npl(a.left) < npl(a.right):
    swap(a.left, a.right)

After the swap, the left child has at least as large a null path length as the right child. Finally, a.npl is recomputed from its children.

This pattern appears at every level on the way back from recursion:

1. Solve the smaller subproblem on the right.
2. Attach its result.
3. Swap children if needed.
4. Recompute the local rank.

The entire merged structure becomes valid because every node repairs itself after its child merge completes.

17. Heap Sort and the Role of Merging​

Heap sort uses an ordinary binary heap to sort a collection. For ascending order, a max-heap can repeatedly expose the largest element, place it at the end of the array, and restore the heap with sift-down. Its overall running time is O(n log n).

A leftist heap can also repeatedly extract its root to produce elements in priority order. However, the main reason to choose a leftist heap is usually not its role in classic in-place heap sort. The distinctive advantage is the ability to meld heaps efficiently.

This distinction illustrates a broader design principle: a data structure is often defined by the operation it makes convenient. An array-based heap emphasizes compact storage and efficient root repair. A leftist heap emphasizes combining independently maintained heaps.

18. Practical Uses and Decision-Making​

The most direct use of a heap is a priority queue. A priority queue repeatedly inserts items and removes the item with the smallest or largest priority.

Examples include:

• Processing tasks by urgency.
• Selecting the next event in time order.
• Maintaining a frontier of candidate items in an algorithm.
• Scheduling work according to priority.

A leftist heap becomes particularly useful when several priority queues need to be combined. Imagine separate groups of tasks, each represented by its own priority queue. If two groups are joined, a leftist heap can meld the corresponding heaps rather than inserting every item from one queue into the other individually.

The practical value is strongest when merge is a frequent, meaningful operation. If merging never occurs and memory compactness is more important, an ordinary array-based binary heap may be preferable.

19. Implementation Considerations​

A typical leftist-heap node stores:

key
left child reference
right child reference
null path length or rank

The implementation should clearly define the null path convention. For example, if npl(null) = -1, then a leaf has npl = 0. If npl(null) = 0, then a leaf may have npl = 1. Either convention works if all comparisons and updates use it consistently.

The merge routine should also handle empty heaps explicitly. Merging an empty heap with a nonempty heap should return the nonempty heap unchanged:

merge(null, h) = h
merge(h, null) = h

For duplicate keys, the comparison can choose either root when the keys are equal. Stable ordering of equal-priority items is not automatically guaranteed by the heap structure. If stability matters, the key can be combined with a sequence number and comparisons can use (priority, sequenceNumber).

Recursive implementations are natural and closely match the mathematical definition. An iterative implementation is possible, but it must preserve the same right-spine traversal and bottom-up repair logic. In either case, correctness depends on maintaining both heap order and the leftist property after every public operation.

20. Common Misconceptions​

A leftist heap is not necessarily left-heavy by node count​

The word “leftist” does not mean that every left subtree contains more nodes than the right subtree. The property compares null path lengths, not direct subtree sizes. It guarantees a short right spine, not a perfectly balanced tree.

A heap is not fully sorted​

Only the root is guaranteed to be the global minimum or maximum. Children are not necessarily ordered relative to one another, and a traversal of the heap does not generally produce sorted output.

The root comparison alone is not enough​

Choosing the smaller root while merging two min-heaps preserves heap order at the new root, but it does not automatically preserve the leftist property. The recursive right merge, child swap, and null path update are all necessary.

Child swapping does not sort the tree​

Swapping left and right children is a structural repair for the leftist rule. It does not create binary-search-tree ordering, nor is it intended to sort sibling subtrees.

Completeness is not required for every heap​

Complete shape is characteristic of ordinary array-based binary heaps. Leftist heaps use a different structural invariant and are commonly represented with linked nodes.

21. A Compact Correctness Argument​

A merge operation is correct if it returns a structure satisfying both invariants.

First, consider heap order. The algorithm selects the smaller root for a min-leftist heap. The selected root is no larger than the other root and remains no larger than its original children. The recursively merged right subtree is itself a valid min-leftist heap, so the selected root is no larger than its new right child as well.

Second, consider the leftist property. After the recursive merge, the algorithm compares the null path lengths of the two children. If the left child’s value is smaller than the right child’s, it swaps them. Therefore, after the swap, the left child’s null path length is at least the right child’s. The node’s own null path length is then recomputed from the children.

The base cases are also valid:

• An empty heap is valid.
• Returning a nonempty heap unchanged preserves its invariants.
• A singleton heap satisfies both properties.

By induction over the recursive calls, every merge returns a valid leftist heap. Since insertion and extraction are built from merge, they inherit this correctness when their surrounding steps are implemented correctly.

22. Practical Takeaways​

A leftist heap is best understood as a heap with a deliberate structural bias:

1. Heap order puts the minimum or maximum at the root.
2. Null path lengths measure how close a node is to a missing child along the shortest route.
3. The leftist property keeps the left rank at least as large as the right rank.
4. The right spine is therefore short.
5. Merge follows that short spine and repairs the tree while returning from recursion.
6. Insertion is merge with a singleton.
7. Extraction is merge of the removed root’s two subheaps.

When a priority queue must frequently absorb another priority queue, this design is especially natural. When the workload is a single large heap with no melding, an ordinary complete binary heap may offer simpler array storage and familiar sift-up and sift-down operations.

The key lesson is not that one heap is universally better than another. The lesson is that a data structure’s invariant should reflect its most important operation. Ordinary heaps use completeness to support compact storage and logarithmic repairs. Leftist heaps use a short right spine to make merging efficient. That focused design choice is what makes the leftist heap a heap born to merge.