Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

Implementing a Fibonacci Heap with Reliable Decrease-Key Support

The Fibonacci heap is one of those data structures engineers either love or quietly avoid. Invented by Michael Fredman and Robert Tarjan in 1984, it offers amortised time bounds that look almost magical: insert, find-min, meld, and decrease-key all run in O(1) amortised time, while extract-min and delete take O(log n) amortised. For graph algorithms like Dijkstra's shortest path or Prim's minimum spanning tree, those bounds can shave meaningful time off large inputs, which matters when you're running routing across an Australian telco's backbone or processing transit data for Sydney's transport authority.

This article walks through a practical implementation of the Fibonacci heap with a sharp focus on the decrease-key operation. We'll cover node layout, the circular doubly linked root list, the consolidate step, cascading cuts, and the potential function that justifies the amortised bounds. A reader who knows basic amortised analysis and is comfortable with heaps in general will find enough here to build one in C or Python and reason about its behaviour.

Why bother with Fibonacci heaps?

Most engineers reach for a binary heap or, increasingly, a pairing heap when they need a priority queue. Binary heaps give O(log n) for everything except decrease-key, which is also O(log n). Pairing heaps are simpler to code and often faster in practice. So why bother with a Fibonacci heap? The answer sits in the asymptotics: when a workload performs many more decrease-key calls than extract-min calls, the O(1) amortised bound on decrease-key starts to dominate the running time.

Real workloads where this happens include the Dijkstra implementation used inside some of Australia's freight routing systems, network analysis pipelines built by data teams in Brisbane's mining sector, and graph algorithms shipped by teams at firms like Canva or Atlassian in Sydney. In all of these cases, edges get relaxed frequently but only a handful of nodes actually win extraction. A Fibonacci heap can outperform a binary heap on such graphs because the relaxation cost drops from O(log n) to O(1).

There's also a pedagogical reason: writing a Fibonacci heap is one of the best exercises in amortised analysis available. The data structure pulls together circular linked lists, trees, marks, cascading cuts, and a clever potential function. Once you've implemented it, you understand why amortised proofs work the way they do. For students at the University of Melbourne or UNSW taking an algorithms unit, it's a rite of passage.

Node layout and the circular root list

A Fibonacci heap is a collection of heap-ordered trees. Each node holds a key, a value, a degree (number of children), a mark flag, a pointer to one of its children, and pointers to its left and right siblings. The siblings form a circular doubly linked list, which lets us splice a child out or insert a sibling in O(1) time without worrying about boundary cases.

The root list itself is also a circular doubly linked list, holding all the current tree roots. Finding the minimum is as cheap as keeping a pointer to the smallest root, updated whenever insert or decrease-key produces something smaller. There is no array of fixed size, and the structure grows and shrinks lazily as trees get linked during extract-min.

In practice, you'll want a struct like this in C:

typedef struct FibNode {
    int key;
    void *value;
    int degree;
    int marked;
    struct FibNode *parent;
    struct FibNode *child;
    struct FibNode *left;
    struct FibNode *right;
} FibNode;

The circular links mean that if a node has no left sibling, its left pointer points to itself. This invariant saves a special case during remove, which you'll call from extract-min and from delete. If you prefer Python, dataclasses work nicely for the same layout and let you keep the code readable while you experiment.

Insert, meld, and extract-min in practice

Insert is the simplest operation in the heap. Create a new node with no children, no parent, and not marked. Splice it into the root list in O(1) and update the min pointer if the new key is smaller. That's it. Because every insert adds a single-node tree to the root list, the heap lazily accrues work that extract-min will eventually handle during consolidation.

Meld, or union, is just as cheap. Concatenate the two root lists in O(1) and pick the smaller of the two min pointers. You can do this by walking each list to its tail and splicing them together, or by maintaining a helper that links two circular lists. Either way, meld is where Fibonacci heaps outshine every other heap family and why some parallel shortest-path implementations use them when running across distributed clusters.

Extract-min is where the real work happens. Remove the minimum node, add each of its children to the root list, then consolidate. Consolidation walks the root list, combining trees of equal degree so that at most one tree of each degree remains. You use an auxiliary array indexed by degree, holding the tree you've most recently linked of that degree. When two trees of equal degree come up, link the one with the larger root as a child of the smaller. After consolidation, the min pointer is reset by scanning the updated root list.

def extract_min(heap):
    z = heap.min_node
    if z is not None:
        for child in z.children:
            child.parent = None
            heap._add_to_root_list(child)
        heap._remove_from_root_list(z)
        if z.right == z:
            heap.min_node = None
        else:
            heap.min_node = z.right
            heap._consolidate()
        heap.n -= 1
    return z

Consolidate is the only operation in the structure whose running time looks expensive, but it's amortised O(log n) over a sequence of operations thanks to the potential function we'll discuss later.

Implementing decrease-key correctly

Decrease-key is the operation that gives Fibonacci heaps their reputation. Given a node whose key is currently greater than a new value, you decrease the key, then walk up the tree fixing heap order. If the new key is smaller than the parent's key, you cut the child off its parent, add it to the root list, and unmark the parent. If the parent was already unmarked, you leave it alone. If the parent was marked, you cut it too, recursively walking up the tree. This cascade is what preserves the structure that bounds the degree of each node.

def decrease_key(heap, node, new_key):
    if new_key > node.key:
        raise ValueError("new key is larger than current key")
    node.key = new_key
    y = node.parent
    if y is not None and node.key < y.key:
        heap._cut(node, y)
        heap._cascading_cut(y)
    if node.key < heap.min_node.key:
        heap.min_node = node

The cut operation removes the node from its sibling list, removes it from its parent's child list, decrements the parent's degree, and adds the node to the root list. Crucially, after being cut to the root list, the node is unmarked. This resets its future participation in cascading cuts and is what bounds how many children any node can lose.

Decrease-key is also where implementations frequently pick up subtle bugs. Off-by-one errors in degree tracking, forgetting to update min when a root becomes smaller, or missing the mark reset are common. Test with small heaps where you can trace the structure by hand. If you want a worked example of how operations build and trim a structure step by step, the ensemble learning guide walks through a similar sequence of decisions and is worth reading alongside your heap code.

Cascading cuts and the role of marks

The mark on a node records whether it has lost a child since it became a child of another node. When a marked node loses another child, it gets cut itself and the cascade continues. Unmarked nodes, when they lose a child, simply become marked. This rule prevents a single node from being lifted through many ancestors in one operation, which would otherwise blow up the amortised bound.

The intuitive picture: marks act as credit that pays for the work of cutting. A node can lose at most one child while unmarked, paying for that cut by setting the mark. If it loses another child, the mark has already been used, so the node itself gets cut. Two cuts per mark, and the analysis works out cleanly. This is why Fibonacci heaps use marks at all, rather than just cutting unconditionally on every decrease-key.

Implementing the cascade is short. Here's the canonical form:

def cascading_cut(heap, y):
    z = y.parent
    if z is not None:
        if not y.marked:
            y.marked = 1
        else:
            heap._cut(y, z)
            heap._cascading_cut(z)

If you're new to amortised cost arguments, working through examples of careful step-by-step reasoning can sharpen your intuition. Reading unrelated guides such as keno strategy walkthroughs trains the same methodical mindset you'll need when tracing a Fibonacci heap during debugging, even though the domains look unrelated.

Amortised analysis with the potential function

The amortised bounds of a Fibonacci heap come from a potential function measured on the structure of the heap. The classical choice is Φ(H) = t(H) + 2 m(H), where t(H) is the number of trees in the root list and m(H) is the number of marked nodes. The actual cost of an operation plus the change in potential gives the amortised cost. Insert and meld add a tree but pay no real work, giving amortised O(1). Decrease-key cuts some nodes and possibly cascades, with the potential drop paying for the work, again giving amortised O(1). Extract-min does O(log n) real work during consolidate but reduces the potential because trees get linked and marks can disappear.

The deep result, which gives the heap its name, is that after cutting a node from its parent, the node's children become a sequence of trees whose sizes follow the Fibonacci sequence. This bounds the maximum degree of any node at O(log n). Without that bound, the consolidate step in extract-min could blow up, because the auxiliary array indexed by degree would need to be huge.

To verify the analysis in practice, instrument your implementation to print t(H) and m(H) at the start and end of each operation. You should see Φ drop sharply during extract-min and stay flat or drop during decrease-key cascades. If Φ keeps climbing during many operations, you have a bug, often a missed cut or a stale mark.

Where Fibonacci heaps shine and where they stall

Fibonacci heaps are not always the right tool. The constants are larger than binary or pairing heaps, the cache behaviour is worse, and the implementation is genuinely fiddly. If your workload does roughly equal numbers of extract-min and decrease-key calls, a pairing heap will usually win on raw wall-clock time. If you only need insert and extract-min with no decrease-key, a binary heap is more than enough.

Here are situations where Fibonacci heaps are worth the effort:

And here are situations where you should probably pick something else:

If you're working on a small project in a Perth startup, the complexity probably isn't worth it. If you're optimising a routing kernel for a Canberra-based logistics platform handling millions of edges daily, the asymptotic savings start to matter. The data structure rewards careful implementation in situations where the amortised savings actually translate to real time, and punishes rushed code where the cascading cuts and marks get out of sync.