DS: Leftist Heaps and Skew Heaps

In algorithms where priority queues must be combined frequently, such as in graph algorithms like Prim's or Dijkstra's with dynamic edges, standard binary heaps fall short due to inefficient merge operations. Leftist heaps and skew heaps address this by using clever tree structures that support merges in logarithmic time, enabling scalable implementations for merge-intensive scenarios. Mastering these data structures equips you with tools to design efficient systems where data structures evolve through union operations.

The Need for Mergeable Heaps

A mergeable heap is a priority queue data structure that supports, beyond insert and delete-min, an efficient merge operation to combine two heaps into one. Standard binary heaps, typically implemented as arrays, require O(n) time to merge, as elements must be reinserted or heapified from scratch. This inefficiency motivates biased binary trees—tree-based heaps where the shape is controlled to allow faster merges. In applications like discrete event simulation or functional programming, where heaps are often immutable and merged, having O(log n) merge is crucial. Both leftist and skew heaps achieve this by focusing on the merge operation as a fundamental building block, with insert and delete-min implemented via merge.

Leftist Heaps: Structure and the Leftist Property

Leftist heaps are binary trees that satisfy the heap-order property (each node's key is less than or equal to its children's, for a min-heap) and the leftist property. This property ensures that for every node, the null-path length (npl) of its left child is at least as large as the npl of its right child. The null-path length of a node is defined as the length of the shortest path from that node to a null child, with null nodes having an npl of 0. Mathematically, for any node $x$, $npl(x)=1+\min (npl(left(x)),npl(right(x)))$, and the leftist property requires $npl(left(x))\ge npl(right(x))$.

This bias guarantees that the right spine—the path from the root following right children—is short, specifically logarithmic in the number of nodes. Intuitively, the tree "leans" left, making the right side shallow, which limits the depth of recursive merges. For example, in a leftist heap with 15 nodes, the right spine might have only 3-4 nodes, compared to a balanced tree where it could be longer. This structural invariant is key to efficient operations.

Merging Leftist Heaps Step by Step

The merge operation for leftist heaps is recursive and hinges on the right spine's shortness. To merge two leftist heaps $H1$ and $H2$:

1. If either heap is empty, return the other.
2. Compare the roots; assume $H1$ has the smaller root (for min-heap). Recursively merge $H2$ with the right subtree of $H1$.
3. After merging, you have a new right subtree. Check if the leftist property holds for the root of $H1$: if $npl(left)<npl(right)$, swap the left and right children.
4. Update the npl of the root: $npl(root)=1+\min (npl(left),npl(right))$.

This process ensures the heap-order and leftist properties are maintained. Since each recursive call descends the right spine and the right spine is O(log n) long, the merge runs in O(log n) time. For instance, merging heaps with roots 5 and 10 involves attaching the heap with root 10 to the right subtree of 5, then swapping children if necessary to keep the tree leftist. The swap step is critical—without it, the right spine could grow, degrading performance.

Skew Heaps: Simplicity with Amortized Efficiency

Skew heaps simplify leftist heaps by eliminating the explicit leftist property check. They are self-adjusting binary heaps where, during a merge, the children of every node visited are unconditionally swapped after the recursive merge. The merge algorithm is similar: compare roots, recursively merge the heap with the larger root into the right subtree of the heap with the smaller root, but then always swap the left and right children of the resulting root before returning.

This "always swap" policy avoids storing npl values and simplifies code, but it doesn't guarantee a short right spine in the worst case. Instead, skew heaps rely on amortized analysis to achieve O(log n) time per operation over a sequence of merges. The swaps spread out the work, ensuring that expensive operations are rare. Think of it like a flexible system that adapts over time—individual merges might occasionally be O(n), but overall performance remains efficient. This makes skew heaps attractive for implementations where code simplicity is prioritized and worst-case guarantees aren't mandatory.

Implementation and Applications

Implementing both variants involves defining a tree node with key, left, and right pointers, plus an npl field for leftist heaps. For leftist heaps, you must carefully update npl after merges; for skew heaps, you simply swap children. In practice, insert is done by merging with a single-node heap, and delete-min by merging the left and right subtrees of the root. When comparing complexities, leftist heaps offer worst-case O(log n) merge, while skew heaps provide amortized O(log n) merge, with skew heaps often faster in practice due to lower overhead.

These structures are particularly useful in applications requiring frequent priority queue merging. For example, in some graph algorithms where multiple priority queues manage different vertex sets that need combining, or in functional programming languages where persistent data structures are common. Another scenario is in job scheduling systems where queues from different users must be merged dynamically. Choosing between them depends on your needs: leftist heaps for predictable performance, skew heaps for simpler code and good average-case behavior.

Common Pitfalls

1. Confusing the leftist property with heap order: The leftist property concerns null-path lengths, not key values. You might incorrectly focus on key comparisons when maintaining balance. Correction: Always compute and compare npl values separately from heap-order checks during merge in leftist heaps.

1. Neglecting child swaps in leftist heap merge: After recursive merge, forgetting to swap children if $npl(left)<npl(right)$ can break the leftist property, leading to a degenerate tree with O(n) merge times. Correction: In the merge function, explicitly check and swap children based on npl before returning the node.

1. Assuming skew heaps have worst-case logarithmic complexity: It's easy to misinterpret amortized efficiency as worst-case. A single skew heap merge might take O(n) time in isolation. Correction: Understand that amortized analysis applies to sequences of operations; use skew heaps where overall throughput matters, not real-time guarantees.

1. Incorrect base cases in recursive merge: Failing to handle empty heaps properly can cause infinite recursion. Correction: Always check if either input heap is null at the start of merge and return the other heap immediately.

Summary

• Leftist heaps maintain the leftist property (based on null-path lengths) to ensure a short right spine, enabling worst-case O(log n) merge operations through careful child swapping after recursive merges.
• Skew heaps simplify by unconditionally swapping children during merge, sacrificing explicit balance for code simplicity and achieving amortized O(log n) efficiency over operation sequences.
• Both are implemented as biased binary trees where merge is the core operation, with insert and delete-min built on top, making them ideal for applications like graph algorithms or functional programming that require frequent priority queue merging.
• Key differences: leftist heaps use npl for balance guarantees, while skew heaps rely on amortized analysis and are easier to code but with less predictable single-operation performance.
• When implementing, ensure correct maintenance of the leftist property or consistent swapping to avoid performance degradation, and choose based on whether worst-case or amortized bounds suit your use case.