Mergeable Heaps: Leftist to Fibonacci

1. Introduction & Motivation

A plain binary heap gives you $O(\log n)$ insert, $O(\log n)$ extract-min, and $O(1)$ peek. But ask it to do one more thing — combine two entire heaps into one — and it has no good answer. The array-backed binary heap has exactly one way to merge: take every element of the smaller heap and insert it, one at a time, into the larger one. Merging a heap of size $m$ into a heap of size $n$ this way costs $O(m \log(n+m))$; when the two heaps are comparable in size, that is $O(n \log n)$ for a single merge — effectively as expensive as sorting all the elements from scratch.

That single missing operation motivates an entire family of data structures called mergeable heaps (also called meldable heaps): priority queues engineered so that combining two heaps is fast — from $O(\log n)$ down to $O(1)$ — often at the cost of giving up the tight, complete-binary-tree shape that makes an array-backed heap so simple. This lesson covers five such structures, roughly in order of increasing structural cleverness:

Leftist Heap: tracks a "null-path length" per node to guarantee a short right spine, so merge only ever recurses down that spine.
Skew Heap: the same merge idea as Leftist, but drops the bookkeeping entirely and just always swaps children — trading a worst-case guarantee for an amortized one.
Pairing Heap: a multi-way tree where merge is a single comparison and a pointer attach — the simplest of the five to implement, and fast in practice.
Binomial Heap: a forest of trees shaped like the binary representation of the heap's size, where merging two heaps is literally binary addition with carries.
Fibonacci Heap: relaxes the Binomial Heap's strict shape to get $O(1)$ amortized insert, merge, and (critically) decrease-key — the structure that gives Dijkstra's algorithm its best known asymptotic running time.

All five support the same core contract as a binary heap — insert, find-min, extract-min — plus an efficient merge (sometimes called meld or union). Several of them also support decrease-key, which matters far beyond textbook exercises: it is the operation Dijkstra's algorithm leans on every time it finds a shorter path to a vertex already in the queue.

2. Prerequisites

This lesson assumes you are already comfortable with the standard array-backed binary heap: the heap-order property, heapify-up and heapify-down, $O(n)$ build-heap, and $O(\log n)$ insert/extract-min. Those fundamentals are covered in depth in Part 11: Heaps, Sorting & Hashing (see its "Heap Fundamentals" and "Heap Operations" sections) — this lesson does not re-derive them. What's new here is entirely about structure: none of the five heaps below use a flat array: they are all explicit node-and-pointer trees (or forests of trees), which is exactly what unlocks fast merging.

3. Leftist Heap

                Core insight: every node tracks an s-value (its null-path length: the distance to the nearest descendant missing a child, with $s(\text{null}) = 0$). The leftist invariant requires $s(\text{left child}) \ge s(\text{right child})$ at every node. Enforcing this forces the tree to lean left (hence "leftist") and keeps the right spine short — provably $O(\log n)$ long for $n$ nodes. Since merge only ever recurses down the right spine of each tree, merge is $O(\log n)$ worst case.
            

Merging two leftist heaps a and b: compare the two roots, keep the smaller as the new root, and recursively merge its right child with the other whole tree. After that recursive merge returns, compare the s-values of the new root's two children and swap them if the left child's s-value is smaller — restoring the invariant. insert is just merge(heap, singleton), and extract-min removes the root and merges its two children.

class LeftistNode:
    __slots__ = ("value", "left", "right", "s")

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.s = 1  # null-path length of a fresh leaf is 1


def _s(node):
    return node.s if node is not None else 0


def merge(a, b):
    """Merge two leftist min-heaps rooted at a and b - O(log n) worst case,
    because recursion only ever follows the (short) right spine."""
    if a is None:
        return b
    if b is None:
        return a
    if a.value > b.value:
        a, b = b, a
    a.right = merge(a.right, b)
    if _s(a.left) < _s(a.right):
        a.left, a.right = a.right, a.left
    a.s = _s(a.right) + 1
    return a


def insert(root, value):
    """Insert is merge with a fresh singleton heap - O(log n)."""
    return merge(root, LeftistNode(value))


def extract_min(root):
    """Remove and return the minimum; the new heap is the merge of the
    old root's two children - O(log n)."""
    if root is None:
        raise IndexError("extract_min from an empty heap")
    new_root = merge(root.left, root.right)
    return root.value, new_root


def to_sorted_list(root):
    values = []
    while root is not None:
        value, root = extract_min(root)
        values.append(value)
    return values


# Build two separate heaps, then merge them.
root_a = None
for v in [5, 3, 8, 1]:
    root_a = insert(root_a, v)

root_b = None
for v in [7, 2]:
    root_b = insert(root_b, v)

combined = merge(root_a, root_b)
print(to_sorted_list(combined))  # [1, 2, 3, 5, 7, 8]

#include <iostream>

struct LeftistNode {
    int value;
    LeftistNode* left;
    LeftistNode* right;
    int s; // null-path length

    explicit LeftistNode(int v) : value(v), left(nullptr), right(nullptr), s(1) {}
};

int nullPathLength(LeftistNode* node) {
    return node == nullptr ? 0 : node->s;
}

LeftistNode* merge(LeftistNode* a, LeftistNode* b) {
    if (a == nullptr) return b;
    if (b == nullptr) return a;
    if (a->value > b->value) std::swap(a, b);
    a->right = merge(a->right, b);
    if (nullPathLength(a->left) < nullPathLength(a->right)) {
        std::swap(a->left, a->right);
    }
    a->s = nullPathLength(a->right) + 1;
    return a;
}

LeftistNode* insertValue(LeftistNode* root, int value) {
    return merge(root, new LeftistNode(value));
}

// Removes the minimum, rewires `root` to the new tree via the reference,
// and returns the extracted value.
int extractMin(LeftistNode*& root) {
    LeftistNode* old = root;
    int value = old->value;
    root = merge(old->left, old->right);
    delete old;
    return value;
}

int main() {
    LeftistNode* rootA = nullptr;
    for (int v : {5, 3, 8, 1}) rootA = insertValue(rootA, v);

    LeftistNode* rootB = nullptr;
    for (int v : {7, 2}) rootB = insertValue(rootB, v);

    LeftistNode* combined = merge(rootA, rootB);

    std::cout << "Sorted: ";
    while (combined != nullptr) {
        std::cout << extractMin(combined) << " ";
    }
    std::cout << "\n"; // Sorted: 1 2 3 5 7 8
}

import java.util.NoSuchElementException;

public class LeftistHeap {
    static class Node {
        int value;
        Node left, right;
        int s = 1; // null-path length

        Node(int value) { this.value = value; }
    }

    static int s(Node node) {
        return node == null ? 0 : node.s;
    }

    static Node merge(Node a, Node b) {
        if (a == null) return b;
        if (b == null) return a;
        if (a.value > b.value) { Node t = a; a = b; b = t; }
        a.right = merge(a.right, b);
        if (s(a.left) < s(a.right)) {
            Node t = a.left; a.left = a.right; a.right = t;
        }
        a.s = s(a.right) + 1;
        return a;
    }

    static Node insert(Node root, int value) {
        return merge(root, new Node(value));
    }

    // Java has no out-parameters, so extract-min returns both the value
    // and the new root via a small holder.
    static class ExtractResult {
        final int value;
        final Node newRoot;
        ExtractResult(int value, Node newRoot) { this.value = value; this.newRoot = newRoot; }
    }

    static ExtractResult extractMin(Node root) {
        if (root == null) throw new NoSuchElementException("extract_min from an empty heap");
        return new ExtractResult(root.value, merge(root.left, root.right));
    }

    public static void main(String[] args) {
        Node rootA = null;
        for (int v : new int[]{5, 3, 8, 1}) rootA = insert(rootA, v);

        Node rootB = null;
        for (int v : new int[]{7, 2}) rootB = insert(rootB, v);

        Node combined = merge(rootA, rootB);

        StringBuilder sb = new StringBuilder("Sorted: ");
        while (combined != null) {
            ExtractResult result = extractMin(combined);
            sb.append(result.value).append(" ");
            combined = result.newRoot;
        }
        System.out.println(sb.toString().trim()); // Sorted: 1 2 3 5 7 8
    }
}

4. Skew Heap

                Core insight: a Skew Heap is a Leftist Heap with the bookkeeping removed. There is no s-value and no invariant to maintain — merge does the exact same recursive descent (smaller root wins, recurse into its right child), but then unconditionally swaps the resulting root's two children, every time, no comparison needed. The tree can become arbitrarily unbalanced for any single operation, yet a sequence of $n$ operations still costs $O(n \log n)$ total, i.e. $O(\log n)$ amortized per operation — not worst case.
            

Why does unconditional swapping still bound the amortized cost? Intuitively, every merge step walks one node further down the right spine of each input tree, then immediately turns that step into a left-spine step by swapping. A node can only be visited by a merge along a right spine a bounded number of times before the swapping forces it onto a much shorter path for future operations; a potential-function argument (assigning "credit" to nodes on the right spine of any subtree) shows the total work across any sequence of $n$ merges is $O(n \log n)$, even though a single pathological merge can briefly touch $O(n)$ nodes.

class SkewNode:
    __slots__ = ("value", "left", "right")

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def merge(a, b):
    """Merge two skew heaps. No invariant is tracked - children are
    swapped unconditionally after every recursive merge.
    O(log n) AMORTIZED, not worst case."""
    if a is None:
        return b
    if b is None:
        return a
    if a.value > b.value:
        a, b = b, a
    a.right = merge(a.right, b)
    a.left, a.right = a.right, a.left  # unconditional swap
    return a


def insert(root, value):
    return merge(root, SkewNode(value))


def extract_min(root):
    if root is None:
        raise IndexError("extract_min from an empty heap")
    new_root = merge(root.left, root.right)
    return root.value, new_root


def to_sorted_list(root):
    values = []
    while root is not None:
        value, root = extract_min(root)
        values.append(value)
    return values


root = None
for v in [9, 4, 6, 1, 7, 3]:
    root = insert(root, v)

print(to_sorted_list(root))  # [1, 3, 4, 6, 7, 9]

#include <iostream>

struct SkewNode {
    int value;
    SkewNode* left;
    SkewNode* right;
    explicit SkewNode(int v) : value(v), left(nullptr), right(nullptr) {}
};

SkewNode* merge(SkewNode* a, SkewNode* b) {
    if (a == nullptr) return b;
    if (b == nullptr) return a;
    if (a->value > b->value) std::swap(a, b);
    a->right = merge(a->right, b);
    std::swap(a->left, a->right); // unconditional swap - no invariant to maintain
    return a;
}

SkewNode* insertValue(SkewNode* root, int value) {
    return merge(root, new SkewNode(value));
}

int extractMin(SkewNode*& root) {
    SkewNode* old = root;
    int value = old->value;
    root = merge(old->left, old->right);
    delete old;
    return value;
}

int main() {
    SkewNode* root = nullptr;
    for (int v : {9, 4, 6, 1, 7, 3}) root = insertValue(root, v);

    std::cout << "Sorted: ";
    while (root != nullptr) std::cout << extractMin(root) << " ";
    std::cout << "\n"; // Sorted: 1 3 4 6 7 9
}

import java.util.NoSuchElementException;

public class SkewHeap {
    static class Node {
        int value;
        Node left, right;
        Node(int value) { this.value = value; }
    }

    static Node merge(Node a, Node b) {
        if (a == null) return b;
        if (b == null) return a;
        if (a.value > b.value) { Node t = a; a = b; b = t; }
        a.right = merge(a.right, b);
        Node t = a.left; a.left = a.right; a.right = t; // unconditional swap
        return a;
    }

    static Node insert(Node root, int value) {
        return merge(root, new Node(value));
    }

    static class ExtractResult {
        final int value;
        final Node newRoot;
        ExtractResult(int value, Node newRoot) { this.value = value; this.newRoot = newRoot; }
    }

    static ExtractResult extractMin(Node root) {
        if (root == null) throw new NoSuchElementException("extract_min from an empty heap");
        return new ExtractResult(root.value, merge(root.left, root.right));
    }

    public static void main(String[] args) {
        Node root = null;
        for (int v : new int[]{9, 4, 6, 1, 7, 3}) root = insert(root, v);

        StringBuilder sb = new StringBuilder("Sorted: ");
        while (root != null) {
            ExtractResult r = extractMin(root);
            sb.append(r.value).append(" ");
            root = r.newRoot;
        }
        System.out.println(sb.toString().trim()); // Sorted: 1 3 4 6 7 9
    }
}

5. Pairing Heap

                Core insight: a Pairing Heap is a multi-way tree, not a binary one. Merging two pairing heaps is the simplest operation in this entire lesson: compare the two roots, and attach the heap with the larger root as a new child of the heap with the smaller root. That's it — $O(1)$ worst case, no recursion. The subtlety is entirely in extract-min: removing the root leaves behind a list of orphaned child subtrees that must be recombined, using the "two-pass pairing" procedure below.
            

To extract the minimum: detach the root's list of children, then (1) pair them up left-to-right and merge each pair, and (2) combine the resulting merged trees right-to-left into one final tree. This specific two-pass order (rather than, say, merging strictly left-to-right) is what gives Pairing Heaps their good amortized behavior in practice.

class PairingNode:
    __slots__ = ("value", "children")

    def __init__(self, value):
        self.value = value
        self.children = []


def merge(a, b):
    """Attach the heap with the larger root as a child of the one with
    the smaller root. O(1) worst case."""
    if a is None:
        return b
    if b is None:
        return a
    if a.value <= b.value:
        a.children.append(b)
        return a
    else:
        b.children.append(a)
        return b


def insert(root, value):
    return merge(root, PairingNode(value))


def _merge_pairs(children):
    """Two-pass pairing: merge left-to-right in pairs, then combine those
    results right-to-left. This order is what gives the amortized bounds."""
    if not children:
        return None
    if len(children) == 1:
        return children[0]

    merged_pairs = []
    i = 0
    while i + 1 < len(children):
        merged_pairs.append(merge(children[i], children[i + 1]))
        i += 2
    if i < len(children):
        merged_pairs.append(children[i])

    result = merged_pairs[-1]
    for j in range(len(merged_pairs) - 2, -1, -1):
        result = merge(merged_pairs[j], result)
    return result


def extract_min(root):
    if root is None:
        raise IndexError("extract_min from an empty heap")
    new_root = _merge_pairs(root.children)
    return root.value, new_root


def to_sorted_list(root):
    values = []
    while root is not None:
        value, root = extract_min(root)
        values.append(value)
    return values


root = None
for v in [5, 3, 8, 1, 2]:
    root = insert(root, v)

print(to_sorted_list(root))  # [1, 2, 3, 5, 8]

#include <iostream>
#include <vector>

struct PairingNode {
    int value;
    std::vector<PairingNode*> children;
    explicit PairingNode(int v) : value(v) {}
};

PairingNode* merge(PairingNode* a, PairingNode* b) {
    if (a == nullptr) return b;
    if (b == nullptr) return a;
    if (a->value <= b->value) {
        a->children.push_back(b);
        return a;
    } else {
        b->children.push_back(a);
        return b;
    }
}

PairingNode* insertValue(PairingNode* root, int value) {
    return merge(root, new PairingNode(value));
}

PairingNode* mergePairs(std::vector<PairingNode*>& children) {
    if (children.empty()) return nullptr;
    if (children.size() == 1) return children[0];

    std::vector<PairingNode*> mergedPairs;
    std::size_t i = 0;
    while (i + 1 < children.size()) {
        mergedPairs.push_back(merge(children[i], children[i + 1]));
        i += 2;
    }
    if (i < children.size()) mergedPairs.push_back(children[i]);

    PairingNode* result = mergedPairs.back();
    for (int j = static_cast<int>(mergedPairs.size()) - 2; j >= 0; --j) {
        result = merge(mergedPairs[j], result);
    }
    return result;
}

int extractMin(PairingNode*& root) {
    PairingNode* old = root;
    int value = old->value;
    root = mergePairs(old->children);
    delete old;
    return value;
}

int main() {
    PairingNode* root = nullptr;
    for (int v : {5, 3, 8, 1, 2}) root = insertValue(root, v);

    std::cout << "Sorted: ";
    while (root != nullptr) std::cout << extractMin(root) << " ";
    std::cout << "\n"; // Sorted: 1 2 3 5 8
}

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

public class PairingHeap {
    static class Node {
        int value;
        List<Node> children = new ArrayList<>();
        Node(int value) { this.value = value; }
    }

    static Node merge(Node a, Node b) {
        if (a == null) return b;
        if (b == null) return a;
        if (a.value <= b.value) {
            a.children.add(b);
            return a;
        } else {
            b.children.add(a);
            return b;
        }
    }

    static Node insert(Node root, int value) {
        return merge(root, new Node(value));
    }

    static Node mergePairs(List<Node> children) {
        if (children.isEmpty()) return null;
        if (children.size() == 1) return children.get(0);

        List<Node> mergedPairs = new ArrayList<>();
        int i = 0;
        while (i + 1 < children.size()) {
            mergedPairs.add(merge(children.get(i), children.get(i + 1)));
            i += 2;
        }
        if (i < children.size()) mergedPairs.add(children.get(i));

        Node result = mergedPairs.get(mergedPairs.size() - 1);
        for (int j = mergedPairs.size() - 2; j >= 0; j--) {
            result = merge(mergedPairs.get(j), result);
        }
        return result;
    }

    static class ExtractResult {
        final int value;
        final Node newRoot;
        ExtractResult(int value, Node newRoot) { this.value = value; this.newRoot = newRoot; }
    }

    static ExtractResult extractMin(Node root) {
        if (root == null) throw new NoSuchElementException("extract_min from an empty heap");
        return new ExtractResult(root.value, mergePairs(root.children));
    }

    public static void main(String[] args) {
        Node root = null;
        for (int v : new int[]{5, 3, 8, 1, 2}) root = insert(root, v);

        StringBuilder sb = new StringBuilder("Sorted: ");
        while (root != null) {
            ExtractResult r = extractMin(root);
            sb.append(r.value).append(" ");
            root = r.newRoot;
        }
        System.out.println(sb.toString().trim()); // Sorted: 1 2 3 5 8
    }
}

6. Binomial Heap

                Core insight: a Binomial Heap is not one tree but a forest — at most one binomial tree of each order $k$ (an order-$k$ tree has exactly $2^k$ nodes). Whether an order-$k$ tree is present mirrors whether bit $k$ is set in the binary representation of $n$, the heap's size. Merging two binomial heaps is then exactly like binary addition with carries: two order-$k$ trees combine (link) into one order-$(k{+}1)$ tree, exactly as two 1-bits at the same position carry into the next position.
            

Link: given two order-$k$ trees, compare their roots; the one with the larger value becomes the new leftmost child of the one with the smaller value, producing a single order-$(k{+}1)$ tree in $O(1)$. Merge (union): splice the two root lists together sorted by ascending order (like the merge step of merge sort), then walk the combined list left to right, "carrying" whenever two adjacent trees share the same order — identical in spirit to adding two binary numbers digit by digit. Extract-min: scan the root list for the minimum-valued root, remove it, reverse its list of children into a fresh small binomial heap, and merge that back into what remains.

class BinomialNode:
    __slots__ = ("value", "degree", "child", "sibling")

    def __init__(self, value):
        self.value = value
        self.degree = 0
        self.child = None    # leftmost child
        self.sibling = None  # next root, or next sibling within a child list


class BinomialHeap:
    """A forest of binomial trees, at most one tree per order - structured
    like the binary representation of the heap's size."""

    def __init__(self):
        self.head = None  # root list, sorted by increasing degree

    def is_empty(self):
        return self.head is None

    @staticmethod
    def _link(y, z):
        """Make z the parent of y. Requires y.value >= z.value and
        y.degree == z.degree."""
        y.sibling = z.child
        z.child = y
        z.degree += 1

    @staticmethod
    def _merge_root_lists(h1, h2):
        """Merge two root lists into one sorted by non-decreasing degree -
        exactly like the merge step of merge sort."""
        dummy = BinomialNode(0)  # sentinel; its own fields are never read
        tail = dummy
        while h1 is not None and h2 is not None:
            if h1.degree <= h2.degree:
                tail.sibling, h1 = h1, h1.sibling
            else:
                tail.sibling, h2 = h2, h2.sibling
            tail = tail.sibling
        tail.sibling = h1 if h1 is not None else h2
        return dummy.sibling

    def merge_with(self, other):
        """Absorb `other` into this heap - like binary addition with
        carries. O(log n)."""
        merged = self._merge_root_lists(self.head, other.head)
        other.head = None
        if merged is None:
            self.head = None
            return

        prev, curr, nxt = None, merged, merged.sibling
        while nxt is not None:
            if (curr.degree != nxt.degree) or (
                nxt.sibling is not None and nxt.sibling.degree == curr.degree
            ):
                prev, curr = curr, nxt
            elif curr.value <= nxt.value:
                curr.sibling = nxt.sibling
                self._link(nxt, curr)
            else:
                if prev is None:
                    merged = nxt
                else:
                    prev.sibling = nxt
                self._link(curr, nxt)
                curr = nxt
            nxt = curr.sibling
        self.head = merged

    def insert(self, value):
        """Insert is merge with a singleton one-node heap - O(log n) worst
        case, O(1) amortized (like a binary counter increment)."""
        singleton = BinomialHeap()
        singleton.head = BinomialNode(value)
        self.merge_with(singleton)

    def find_min(self):
        if self.head is None:
            raise IndexError("find_min on an empty heap")
        best = self.head
        node = self.head.sibling
        while node is not None:
            if node.value < best.value:
                best = node
            node = node.sibling
        return best.value

    def extract_min(self):
        """Remove and return the minimum root, then merge its children
        back in as a new heap. O(log n)."""
        if self.head is None:
            raise IndexError("extract_min from an empty heap")

        prev_min, min_node = None, self.head
        prev, node = self.head, self.head.sibling
        while node is not None:
            if node.value < min_node.value:
                prev_min, min_node = prev, node
            prev, node = node, node.sibling

        if prev_min is None:
            self.head = min_node.sibling
        else:
            prev_min.sibling = min_node.sibling

        # Reverse min_node's children (stored highest-degree-first) into an
        # ascending-degree root list for the sub-heap being merged back in.
        child_heap = BinomialHeap()
        child = min_node.child
        while child is not None:
            nxt = child.sibling
            child.sibling = child_heap.head
            child_heap.head = child
            child = nxt

        self.merge_with(child_heap)
        return min_node.value


heap_a = BinomialHeap()
for v in [5, 3, 8, 1]:
    heap_a.insert(v)

heap_b = BinomialHeap()
for v in [7, 2, 6]:
    heap_b.insert(v)

heap_a.merge_with(heap_b)

result = []
while not heap_a.is_empty():
    result.append(heap_a.extract_min())
print(result)  # [1, 2, 3, 5, 6, 7, 8]

#include <iostream>
#include <stdexcept>

struct BinomialNode {
    int value;
    int degree;
    BinomialNode* child;
    BinomialNode* sibling;
    explicit BinomialNode(int v) : value(v), degree(0), child(nullptr), sibling(nullptr) {}
};

class BinomialHeap {
public:
    BinomialNode* head = nullptr;

    bool isEmpty() const { return head == nullptr; }

    // Insert is merge with a singleton one-node heap.
    void insert(int value) {
        BinomialHeap singleton;
        singleton.head = new BinomialNode(value);
        mergeWith(singleton);
    }

    int findMin() const {
        if (head == nullptr) throw std::underflow_error("find_min on an empty heap");
        BinomialNode* best = head;
        for (BinomialNode* node = head->sibling; node != nullptr; node = node->sibling) {
            if (node->value < best->value) best = node;
        }
        return best->value;
    }

    // Absorb `other` into this heap - like binary addition with carries. O(log n).
    void mergeWith(BinomialHeap& other) {
        BinomialNode* merged = mergeRootLists(head, other.head);
        other.head = nullptr;
        if (merged == nullptr) { head = nullptr; return; }

        BinomialNode* prev = nullptr;
        BinomialNode* curr = merged;
        BinomialNode* next = curr->sibling;
        while (next != nullptr) {
            if (curr->degree != next->degree ||
                (next->sibling != nullptr && next->sibling->degree == curr->degree)) {
                prev = curr;
                curr = next;
            } else if (curr->value <= next->value) {
                curr->sibling = next->sibling;
                link(next, curr);
            } else {
                if (prev == nullptr) merged = next;
                else prev->sibling = next;
                link(curr, next);
                curr = next;
            }
            next = curr->sibling;
        }
        head = merged;
    }

    // Remove and return the minimum root, then merge its children back in. O(log n).
    int extractMin() {
        if (head == nullptr) throw std::underflow_error("extract_min from an empty heap");

        BinomialNode* prevMin = nullptr;
        BinomialNode* minNode = head;
        BinomialNode* prev = head;
        BinomialNode* node = head->sibling;
        while (node != nullptr) {
            if (node->value < minNode->value) { prevMin = prev; minNode = node; }
            prev = node;
            node = node->sibling;
        }

        if (prevMin == nullptr) head = minNode->sibling;
        else prevMin->sibling = minNode->sibling;

        BinomialHeap childHeap;
        BinomialNode* child = minNode->child;
        while (child != nullptr) {
            BinomialNode* next = child->sibling;
            child->sibling = childHeap.head;
            childHeap.head = child;
            child = next;
        }

        mergeWith(childHeap);
        int value = minNode->value;
        delete minNode;
        return value;
    }

private:
    static void link(BinomialNode* y, BinomialNode* z) {
        // Make z the parent of y. Requires y->value >= z->value, y->degree == z->degree.
        y->sibling = z->child;
        z->child = y;
        z->degree++;
    }

    static BinomialNode* mergeRootLists(BinomialNode* h1, BinomialNode* h2) {
        BinomialNode dummy(0); // stack sentinel; never deleted, never read
        BinomialNode* tail = &dummy;
        while (h1 != nullptr && h2 != nullptr) {
            if (h1->degree <= h2->degree) { tail->sibling = h1; h1 = h1->sibling; }
            else { tail->sibling = h2; h2 = h2->sibling; }
            tail = tail->sibling;
        }
        tail->sibling = (h1 != nullptr) ? h1 : h2;
        return dummy.sibling;
    }
};

int main() {
    BinomialHeap heapA;
    for (int v : {5, 3, 8, 1}) heapA.insert(v);

    BinomialHeap heapB;
    for (int v : {7, 2, 6}) heapB.insert(v);

    heapA.mergeWith(heapB);

    std::cout << "Sorted: ";
    while (!heapA.isEmpty()) std::cout << heapA.extractMin() << " ";
    std::cout << "\n"; // Sorted: 1 2 3 5 6 7 8
}

import java.util.NoSuchElementException;

public class BinomialHeap {
    static class Node {
        int value;
        int degree;
        Node child;
        Node sibling;
        Node(int value) { this.value = value; }
    }

    Node head;

    boolean isEmpty() { return head == null; }

    void insert(int value) {
        BinomialHeap singleton = new BinomialHeap();
        singleton.head = new Node(value);
        mergeWith(singleton);
    }

    int findMin() {
        if (head == null) throw new NoSuchElementException("find_min on an empty heap");
        Node best = head;
        for (Node node = head.sibling; node != null; node = node.sibling) {
            if (node.value < best.value) best = node;
        }
        return best.value;
    }

    // Absorb `other` into this heap - like binary addition with carries. O(log n).
    void mergeWith(BinomialHeap other) {
        Node merged = mergeRootLists(head, other.head);
        other.head = null;
        if (merged == null) { head = null; return; }

        Node prev = null;
        Node curr = merged;
        Node next = curr.sibling;
        while (next != null) {
            if (curr.degree != next.degree
                    || (next.sibling != null && next.sibling.degree == curr.degree)) {
                prev = curr;
                curr = next;
            } else if (curr.value <= next.value) {
                curr.sibling = next.sibling;
                link(next, curr);
            } else {
                if (prev == null) merged = next;
                else prev.sibling = next;
                link(curr, next);
                curr = next;
            }
            next = curr.sibling;
        }
        head = merged;
    }

    // Remove and return the minimum root, then merge its children back in. O(log n).
    int extractMin() {
        if (head == null) throw new NoSuchElementException("extract_min from an empty heap");

        Node prevMin = null;
        Node minNode = head;
        Node prev = head;
        Node node = head.sibling;
        while (node != null) {
            if (node.value < minNode.value) { prevMin = prev; minNode = node; }
            prev = node;
            node = node.sibling;
        }

        if (prevMin == null) head = minNode.sibling;
        else prevMin.sibling = minNode.sibling;

        BinomialHeap childHeap = new BinomialHeap();
        Node child = minNode.child;
        while (child != null) {
            Node next = child.sibling;
            child.sibling = childHeap.head;
            childHeap.head = child;
            child = next;
        }

        mergeWith(childHeap);
        return minNode.value;
    }

    private static void link(Node y, Node z) {
        y.sibling = z.child;
        z.child = y;
        z.degree++;
    }

    private static Node mergeRootLists(Node h1, Node h2) {
        Node dummy = new Node(0); // sentinel; value/degree never read
        Node tail = dummy;
        while (h1 != null && h2 != null) {
            if (h1.degree <= h2.degree) { tail.sibling = h1; h1 = h1.sibling; }
            else { tail.sibling = h2; h2 = h2.sibling; }
            tail = tail.sibling;
        }
        tail.sibling = (h1 != null) ? h1 : h2;
        return dummy.sibling;
    }

    public static void main(String[] args) {
        BinomialHeap heapA = new BinomialHeap();
        for (int v : new int[]{5, 3, 8, 1}) heapA.insert(v);

        BinomialHeap heapB = new BinomialHeap();
        for (int v : new int[]{7, 2, 6}) heapB.insert(v);

        heapA.mergeWith(heapB);

        StringBuilder sb = new StringBuilder("Sorted: ");
        while (!heapA.isEmpty()) sb.append(heapA.extractMin()).append(" ");
        System.out.println(sb.toString().trim()); // Sorted: 1 2 3 5 6 7 8
    }
}

7. Fibonacci Heap

                Core insight: a Fibonacci Heap relaxes the Binomial Heap's strict "at most one tree per order" shape even further. Insert and merge become just root-list concatenation — no linking, no carrying, done lazily and left for later. All of that deferred cleanup work is paid for during extract-min, which "consolidates" the root list back down to one tree per degree. This laziness is what gives $O(1)$ amortized insert, merge, and (critically) decrease-key — the operation that makes Dijkstra's algorithm asymptotically faster.
            

Decrease-key needs one more mechanism to stay cheap: marking. When a node loses a child (because that child was cut away by a decrease-key elsewhere), it is marked. If an already-marked node loses a second child, it is itself cut from its parent and moved to the root list — and the cut cascades upward to its own parent (a "cascading cut"). This bounds how lopsided any tree can become: no node can lose more than one child "for free" before it, too, gets promoted to the root list.

Fibonacci Heaps matter almost entirely because of Dijkstra's algorithm (covered in Part 13: Shortest Paths & Topological Order). With a binary heap, Dijkstra runs in $O((V+E)\log V)$ because every distance update is a $O(\log V)$ decrease-key. Swap in a Fibonacci Heap, where decrease-key is $O(1)$ amortized, and the bound improves to $O(E + V\log V)$ — the $E$ decrease-keys become (amortized) free, and only the $V$ extract-min calls pay the logarithmic cost.

The consolidate step below is written as a clearly-commented, straightforward pass rather than a micro-optimized one: it uses a hash map keyed by degree instead of a pre-sized array, and recomputes degree as "current number of children" instead of caching a separate field. Both choices trade a constant factor for clarity without changing the algorithm's correctness or its $O(\log n)$ amortized extract-min bound.

class FibNode:
    __slots__ = ("value", "children", "parent", "mark")

    def __init__(self, value):
        self.value = value
        self.children = []
        self.parent = None
        self.mark = False


class FibonacciHeap:
    """A relaxed Binomial Heap: merging is just root-list concatenation
    (lazy), and cleanup is deferred until extract-min."""

    def __init__(self):
        self.roots = []
        self.min_node = None

    def is_empty(self):
        return self.min_node is None

    def insert(self, value):
        """O(1) amortized (and worst case): drop a new tree onto the root list."""
        node = FibNode(value)
        self.roots.append(node)
        if self.min_node is None or node.value < self.min_node.value:
            self.min_node = node
        return node

    def merge_with(self, other):
        """Lazy merge: concatenate the two root lists. O(1) amortized.
        (A production implementation splices two circular doubly linked
        root lists in true O(1); this teaching version uses a plain list,
        so the concatenation itself costs O(len(other.roots)) here - but
        no consolidation work happens at merge time either way.)"""
        self.roots.extend(other.roots)
        if other.min_node is not None and (
            self.min_node is None or other.min_node.value < self.min_node.value
        ):
            self.min_node = other.min_node
        other.roots = []
        other.min_node = None

    def _consolidate(self):
        """Combine roots until at most one tree of each degree remains.
        Degree is simply the current number of children - no cached field
        to keep in sync."""
        degree_table = {}
        for root in list(self.roots):
            x = root
            d = len(x.children)
            while d in degree_table:
                y = degree_table.pop(d)
                if y.value < x.value:
                    x, y = y, x
                x.children.append(y)
                y.parent = x
                y.mark = False
                d = len(x.children)
            degree_table[d] = x
        self.roots = list(degree_table.values())
        self.min_node = min(self.roots, key=lambda n: n.value) if self.roots else None

    def extract_min(self):
        """O(log n) amortized: unhook the min root, promote its children
        to the root list, then consolidate."""
        z = self.min_node
        if z is None:
            raise IndexError("extract_min from an empty heap")

        for child in z.children:
            child.parent = None
            self.roots.append(child)
        self.roots.remove(z)

        if self.roots:
            self._consolidate()
        else:
            self.min_node = None
        return z.value

    def _cut(self, node, parent):
        parent.children.remove(node)
        node.parent = None
        node.mark = False
        self.roots.append(node)

    def _cascading_cut(self, node):
        parent = node.parent
        if parent is not None:
            if not node.mark:
                node.mark = True
            else:
                self._cut(node, parent)
                self._cascading_cut(parent)

    def decrease_key(self, node, new_value):
        """O(1) amortized. If the new value violates heap order against
        the parent, cut the node free and cascade the cut upward: a node
        marked once (it already lost a child) that loses a SECOND child is
        itself cut, which bounds how unbalanced any tree can become."""
        if new_value > node.value:
            raise ValueError("new_value must not exceed the current value")
        node.value = new_value
        parent = node.parent
        if parent is not None and node.value < parent.value:
            self._cut(node, parent)
            self._cascading_cut(parent)
        if self.min_node is None or node.value < self.min_node.value:
            self.min_node = node


heap = FibonacciHeap()
handles = {}
for v in [5, 3, 8, 1, 2]:
    handles[v] = heap.insert(v)

print(heap.extract_min())  # 1

heap.decrease_key(handles[8], 0)
print(heap.extract_min())  # 0

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>
#include <unordered_map>

struct FibNode {
    int value;
    std::vector<FibNode*> children;
    FibNode* parent = nullptr;
    bool mark = false;
    explicit FibNode(int v) : value(v) {}
};

class FibonacciHeap {
public:
    std::vector<FibNode*> roots;
    FibNode* minNode = nullptr;

    bool isEmpty() const { return minNode == nullptr; }

    // O(1) amortized (and worst case): drop a new tree onto the root list.
    FibNode* insert(int value) {
        FibNode* node = new FibNode(value);
        roots.push_back(node);
        if (minNode == nullptr || node->value < minNode->value) minNode = node;
        return node;
    }

    // Lazy merge: concatenate root lists. O(1) amortized. (A production
    // implementation splices two circular doubly linked lists in true
    // O(1); this teaching version uses std::vector, so the concatenation
    // costs O(other.roots.size()) here, but no consolidation happens at
    // merge time either way.)
    void mergeWith(FibonacciHeap& other) {
        roots.insert(roots.end(), other.roots.begin(), other.roots.end());
        if (other.minNode != nullptr && (minNode == nullptr || other.minNode->value < minNode->value)) {
            minNode = other.minNode;
        }
        other.roots.clear();
        other.minNode = nullptr;
    }

    // O(log n) amortized: unhook the min root, promote its children, consolidate.
    int extractMin() {
        if (minNode == nullptr) throw std::underflow_error("extract_min from an empty heap");
        FibNode* z = minNode;

        for (FibNode* child : z->children) {
            child->parent = nullptr;
            roots.push_back(child);
        }
        roots.erase(std::remove(roots.begin(), roots.end(), z), roots.end());

        if (!roots.empty()) consolidate();
        else minNode = nullptr;

        int value = z->value;
        delete z;
        return value;
    }

    // O(1) amortized. If decreasing value breaks heap order with the
    // parent, cut the node free and cascade upward: a node marked once
    // (it already lost a child) that loses a second child is cut too,
    // which bounds how unbalanced any tree can become.
    void decreaseKey(FibNode* node, int newValue) {
        if (newValue > node->value) throw std::invalid_argument("newValue must not exceed the current value");
        node->value = newValue;
        FibNode* parent = node->parent;
        if (parent != nullptr && node->value < parent->value) {
            cut(node, parent);
            cascadingCut(parent);
        }
        if (minNode == nullptr || node->value < minNode->value) minNode = node;
    }

private:
    // Combine roots until at most one tree of each degree remains. Degree
    // is simply the current child count - nothing to keep in sync.
    void consolidate() {
        std::unordered_map<int, FibNode*> degreeTable;
        std::vector<FibNode*> snapshot = roots;
        for (FibNode* root : snapshot) {
            FibNode* x = root;
            int d = static_cast<int>(x->children.size());
            while (degreeTable.count(d)) {
                FibNode* y = degreeTable[d];
                degreeTable.erase(d);
                if (y->value < x->value) std::swap(x, y);
                x->children.push_back(y);
                y->parent = x;
                y->mark = false;
                d = static_cast<int>(x->children.size());
            }
            degreeTable[d] = x;
        }
        roots.clear();
        minNode = nullptr;
        for (auto& entry : degreeTable) {
            roots.push_back(entry.second);
            if (minNode == nullptr || entry.second->value < minNode->value) minNode = entry.second;
        }
    }

    void cut(FibNode* node, FibNode* parent) {
        parent->children.erase(std::remove(parent->children.begin(), parent->children.end(), node), parent->children.end());
        node->parent = nullptr;
        node->mark = false;
        roots.push_back(node);
    }

    void cascadingCut(FibNode* node) {
        FibNode* parent = node->parent;
        if (parent != nullptr) {
            if (!node->mark) {
                node->mark = true;
            } else {
                cut(node, parent);
                cascadingCut(parent);
            }
        }
    }
};

int main() {
    FibonacciHeap heap;
    std::unordered_map<int, FibNode*> handles;
    for (int v : {5, 3, 8, 1, 2}) handles[v] = heap.insert(v);

    std::cout << heap.extractMin() << "\n"; // 1

    heap.decreaseKey(handles[8], 0);
    std::cout << heap.extractMin() << "\n"; // 0
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;

public class FibonacciHeap {
    static class Node {
        int value;
        List<Node> children = new ArrayList<>();
        Node parent;
        boolean mark;
        Node(int value) { this.value = value; }
    }

    List<Node> roots = new ArrayList<>();
    Node minNode;

    boolean isEmpty() { return minNode == null; }

    // O(1) amortized (and worst case): drop a new tree onto the root list.
    Node insert(int value) {
        Node node = new Node(value);
        roots.add(node);
        if (minNode == null || node.value < minNode.value) minNode = node;
        return node;
    }

    // Lazy merge: concatenate root lists. O(1) amortized. (A production
    // implementation splices two circular doubly linked lists in true
    // O(1); this teaching version uses ArrayList, so the concatenation
    // costs O(other.roots.size()) here, but no consolidation happens at
    // merge time either way.)
    void mergeWith(FibonacciHeap other) {
        roots.addAll(other.roots);
        if (other.minNode != null && (minNode == null || other.minNode.value < minNode.value)) {
            minNode = other.minNode;
        }
        other.roots = new ArrayList<>();
        other.minNode = null;
    }

    // O(log n) amortized: unhook the min root, promote its children, consolidate.
    int extractMin() {
        if (minNode == null) throw new NoSuchElementException("extract_min from an empty heap");
        Node z = minNode;

        for (Node child : z.children) {
            child.parent = null;
            roots.add(child);
        }
        roots.remove(z);

        if (!roots.isEmpty()) consolidate();
        else minNode = null;

        return z.value;
    }

    // O(1) amortized. If decreasing value breaks heap order with the
    // parent, cut the node free and cascade upward: a node marked once
    // (it already lost a child) that loses a second child is cut too,
    // which bounds how unbalanced any tree can become.
    void decreaseKey(Node node, int newValue) {
        if (newValue > node.value) throw new IllegalArgumentException("newValue must not exceed the current value");
        node.value = newValue;
        Node parent = node.parent;
        if (parent != null && node.value < parent.value) {
            cut(node, parent);
            cascadingCut(parent);
        }
        if (minNode == null || node.value < minNode.value) minNode = node;
    }

    // Combine roots until at most one tree of each degree remains. Degree
    // is simply the current child count - nothing to keep in sync.
    private void consolidate() {
        Map<Integer, Node> degreeTable = new HashMap<>();
        List<Node> snapshot = new ArrayList<>(roots);
        for (Node root : snapshot) {
            Node x = root;
            int d = x.children.size();
            while (degreeTable.containsKey(d)) {
                Node y = degreeTable.remove(d);
                if (y.value < x.value) { Node t = x; x = y; y = t; }
                x.children.add(y);
                y.parent = x;
                y.mark = false;
                d = x.children.size();
            }
            degreeTable.put(d, x);
        }
        roots = new ArrayList<>(degreeTable.values());
        minNode = null;
        for (Node r : roots) {
            if (minNode == null || r.value < minNode.value) minNode = r;
        }
    }

    private void cut(Node node, Node parent) {
        parent.children.remove(node);
        node.parent = null;
        node.mark = false;
        roots.add(node);
    }

    private void cascadingCut(Node node) {
        Node parent = node.parent;
        if (parent != null) {
            if (!node.mark) {
                node.mark = true;
            } else {
                cut(node, parent);
                cascadingCut(parent);
            }
        }
    }

    public static void main(String[] args) {
        FibonacciHeap heap = new FibonacciHeap();
        Map<Integer, Node> handles = new HashMap<>();
        for (int v : new int[]{5, 3, 8, 1, 2}) handles.put(v, heap.insert(v));

        System.out.println(heap.extractMin()); // 1

        heap.decreaseKey(handles.get(8), 0);
        System.out.println(heap.extractMin()); // 0
    }
}

8. Complexity Comparison Table

"Amortized" bounds below hold over any sequence of operations from an empty heap; where a structure gives the same bound worst case and amortized, only one value is shown.

Heap	Insert	Merge	Extract-Min	Decrease-Key
Leftist	$O(\log n)$ worst case	$O(\log n)$ worst case	$O(\log n)$ worst case	Not supported (no parent pointers)
Skew	$O(\log n)$ amortized	$O(\log n)$ amortized	$O(\log n)$ amortized	Not supported (no parent pointers)
Pairing	$O(1)$ worst case	$O(1)$ worst case	$O(\log n)$ amortized	$O(\log n)$ amortized (conjectured optimal)
Binomial	$O(\log n)$ worst case, $O(1)$ amortized	$O(\log n)$ worst case	$O(\log n)$ worst case	$O(\log n)$ worst case (needs parent pointers; not implemented above)
Fibonacci	$O(1)$ amortized	$O(1)$ amortized	$O(\log n)$ amortized	$O(1)$ amortized

9. Applications & Alternatives

Where each variant earns its keep

Choosing among mergeable heaps

Leftist / Skew Heap: the simplest mergeable heaps to reach for in competitive programming when you need to merge priority queues (e.g. small-to-large merging on a tree) and don't need decrease-key.
Pairing Heap: the practical favorite — simplest to implement well, excellent constant factors, and used as the priority queue backing several graph-algorithm libraries in practice, despite its amortized bounds being harder to pin down tightly in theory than Fibonacci's.
Binomial Heap: a clean, fully worst-case-bounded mergeable heap; a natural fit when a system needs predictable per-operation latency rather than just a good amortized average, and its forest-of-trees shape maps directly onto binary counters and other "carry" structures.
Fibonacci Heap: the textbook answer whenever decrease-key dominates the workload — Dijkstra's algorithm and Prim's minimum spanning tree algorithm are the canonical examples. In practice its large constant factors mean a $d$-ary heap or a Pairing Heap often wins on real hardware despite the worse asymptotic bound.

None of these are the only way to get a mergeable priority queue. A balanced BST (Part 10) already supports merge, insert, and extract-min in $O(\log n)$, at the cost of more memory overhead per node than a specialized heap. Concatenable structures like 2-3 finger trees generalize the idea further, supporting split and concatenate alongside priority operations. The right choice, as always, depends on which operation dominates the workload — merge-heavy, decrease-key-heavy, or extract-min-heavy — not on which structure is most famous.

10. Exercises & Mastery

Easy

Given a working merge(a, b) for a Skew Heap, implement insert(root, value) as a single call to merge with a freshly created singleton node.

Medium

Given two Pairing Heaps, merge them and then extract the minimum from the combined heap. State which of the two original roots survives the merge and what happens to its sibling's subtree during the following extract-min.

Hard

You are given a working array/binary-heap-backed implementation of Dijkstra's algorithm. Explain, step by step, how swapping its priority queue for a Fibonacci-Heap-backed one changes the algorithm's asymptotic running time, which specific priority-queue calls benefit, and why. Code is optional here — the goal is the design reasoning, not a rewritten implementation.

Mastery challenge: A job scheduler must support merging two independent priority queues whenever two subsystems are combined at runtime, and must support lowering a job's priority (decrease-key) whenever it's escalated. Choose one heap from this lesson, justify the choice against the alternatives, and explain what changes if merges are rare but decrease-key calls are extremely frequent.

Review rhythm: tomorrow, redraw the Leftist Heap's leftist invariant and the Fibonacci Heap's marking rule from memory; next week, re-derive why Skew Heap's amortized bound holds despite no per-operation guarantee; several weeks later, trace a Binomial Heap merge as binary addition with carries on paper. Finally, explain to someone else why a plain binary heap cannot merge efficiently, and which of these five structures you'd reach for and why.

11. Summary Cheat Sheet

A plain binary heap merges in $O(n \log n)$ by repeated insertion; "mergeable" (meldable) heaps exist specifically to make merge faster.
Leftist Heap: tracks null-path length (s-value) to keep the right spine short; merge is $O(\log n)$ worst case.
Skew Heap: same merge shape as Leftist, but unconditionally swaps children instead of tracking an invariant; $O(\log n)$ amortized, not worst case.
Pairing Heap: a multi-way tree; merge is a single comparison and attach, $O(1)$; extract-min uses two-pass pairing to recombine children.
Binomial Heap: a forest with at most one tree per order; merging is binary addition with carries.
Fibonacci Heap: lazy root-list concatenation for insert/merge, with cleanup deferred to extract-min; marking and cascading cuts bound tree imbalance and give $O(1)$ amortized decrease-key.
Fibonacci Heaps are the classic reason Dijkstra's algorithm reaches $O(E + V\log V)$ instead of $O((V+E)\log V)$.
In practice, Pairing Heaps are frequently preferred over Fibonacci Heaps for their much smaller constant factors.

Cookie Consent

Advanced Heaps: Leftist, Skew, Pairing, Binomial & Fibonacci

Table of Contents

1. Introduction & Motivation

2. Prerequisites

3. Leftist Heap

4. Skew Heap

5. Pairing Heap

6. Binomial Heap

7. Fibonacci Heap

8. Complexity Comparison Table

9. Applications & Alternatives

Choosing among mergeable heaps

10. Exercises & Mastery

Easy

Medium

Hard

11. Summary Cheat Sheet

Cookie Consent

Advanced Heaps: Leftist, Skew, Pairing, Binomial & Fibonacci

Table of Contents

1. Introduction & Motivation

2. Prerequisites

3. Leftist Heap

4. Skew Heap

5. Pairing Heap

6. Binomial Heap

7. Fibonacci Heap

8. Complexity Comparison Table

9. Applications & Alternatives

Choosing among mergeable heaps

10. Exercises & Mastery

Easy

Medium

Hard

11. Summary Cheat Sheet

Continue the DSA Curriculum

Data Structures & Algorithms Hub

Part 11: Heaps, Sorting & Hashing

Part 13: Shortest Paths & Topological Order