Mike, I've been learning how to implement leftist heaps. I've been thinking of it's primary merge function, and have the following implementation:
I've defined 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 ride node, and an npl value.
Most heap nodes you will see have a value, and left and right nodes, npl is a special property - it stands for Node 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.
To illustrate:
Gah! I spotted the error in this generated diagram after publishing. :-(
I implemented a function for get_npl. It's a minor convenience function, but it has the benefit of making it's access more explicit later in the algorithm:
def get_npl(node):
return node.npl if node else -1
The merge function itself is a really simple recursive function:
# Recursive merge/comparison
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 left and right nodes, depending on the npl, and it will update the npl. Anyway 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 as it maintains the leftist property. By keeping the leftist property, the merge can maintain a O(log n) runtime, which is significantly faster than regular heap O(n). It comes down to knowing that it's always leftist, which eliminates traversals and speeds up merge performance.
Here is an example leftist heap merge:
