Mike, I’ve been learning how to implement leftist heaps. I’ve been thinking about the primary merge function, and have the following implementation.

I define a node in my heap like this:

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        self.npl = 0

There is a value, a left and a right node, and an npl value.

Most heap nodes you’ll see have a value and left and right children. npl is a special property — it stands for Null Path Length. It’s the shortest path from X (the current node) to a null node — that is, a node with either one or no children.

I implemented a small function get_npl. It’s a minor convenience, but it makes access more explicit later in the algorithm:

def get_npl(node):
    return node.npl if node else -1

The merge function itself is a simple recursive function:

def merge(h1, h2):
    if not h1: return h2
    if not h2: return h1

    # Ensure h1 is the root with the smaller value; if not, swap.
    if h1.val > h2.val:
        h1, h2 = h2, h1

    # Recursive merge: h1's right child with h2.
    h1.right = merge(h1.right, h2)

    return finalize_node(h1)

I’ve been grappling with a good name for the “finalizing” function finalize_node. It could be maybe_swap, or swap_and_update_npl. It might swap the left and right nodes depending on the NPL, and then update the NPL. Here it is:

def finalize_node(node):
    # Compare NPLs: if right is longer, swap to keep it "left-heavy".
    if get_npl(node.left) < get_npl(node.right):
        node.left, node.right = node.right, node.left

    # Update current node's NPL based on the right child.
    node.npl = get_npl(node.right) + 1
    return node

This swapping is critical: it maintains the leftist property. By keeping the tree leftist, the merge can maintain O(log n) runtime, significantly faster than a naive O(n). It comes down to knowing the tree is always leftist, which eliminates traversals and speeds up merge performance.