Fibonacci Heaps

Every time a navigation app finds the fastest route, it runs a shortest-path algorithm — most likely Dijkstra's. And at the heart of Dijkstra's algorithm sits a single operation repeated thousands of times: decrease-key, the act of updating a node's tentative distance when a shorter path is found.

With a binary heap — the default priority queue in most textbooks — decrease-key costs $O(\log n)$. That gives Dijkstra an overall complexity of $O((E + V) \log V)$, where $E$ is edges and $V$ is vertices. Fine for small graphs, but not optimal.

In 1987, Michael Fredman and Robert Tarjan invented the Fibonacci heap, a priority queue that reduces decrease-key to amortized $O(1)$. The result: Dijkstra runs in $O(E + V \log V)$ — a genuine improvement on dense graphs, and the theoretical optimum for comparison-based shortest paths.

The trick is pure laziness: when you decrease a key, just cut that node out of its tree and throw it on a loose pile. Don't reorganize anything until you absolutely must. It sounds reckless. It works.

Insert nodes and decrease their keys. Notice that insert and decrease-key just drop nodes onto a loose root list — no cleanup. Only Extract Min triggers a consolidation pass that links trees by degree.

<p class="hint">{{hint}}</p>
<div class="controls">
  <div class="input-row">
    <input id="val" type="number" min="1" max="99" value="10" placeholder="key">
    <button id="btn-insert" type="button">{{btn_insert}}</button>
  </div>
  <div class="input-row">
    <select id="sel-node"></select>
    <input id="dec-val" type="number" min="1" max="99" value="1" placeholder="{{placeholder_new_key}}">
    <button id="btn-dec" type="button">{{btn_dec}}</button>
  </div>
  <div class="input-row">
    <button id="btn-extract" type="button">{{btn_extract}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>
<div id="heap-vis" class="heap-vis"></div>
<div id="status" class="status"></div>
<div id="steps" class="steps"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 4px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .65rem; line-height: 1.45; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .6rem; }
.input-row { display: flex; gap: .4rem; flex-wrap: wrap; align-items: center; }
input[type=number] { width: 68px; padding: .35rem .5rem; border: 1px solid #bbb; border-radius: 7px; font-size: .9rem; }
select { padding: .35rem .5rem; border: 1px solid #bbb; border-radius: 7px; font-size: .9rem; max-width: 120px; }
button { font: 600 13px system-ui; padding: .38rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; white-space: nowrap; }
button.ghost { background: #fff; color: #1d3557; }
.heap-vis { min-height: 90px; border: 1px solid #dde3ea; border-radius: 10px;
            background: #f6f8fb; padding: .5rem .6rem; overflow-x: auto;
            display: flex; flex-wrap: wrap; gap: 16px; align-items: flex-start; }
.tree { display: inline-flex; flex-direction: column; align-items: center; }
.node-row { display: flex; gap: 8px; justify-content: center; }
.node { width: 38px; height: 38px; border-radius: 50%; display: flex; align-items: center;
        justify-content: center; font: 700 14px ui-monospace, monospace;
        border: 2px solid #1d3557; background: #d8e4ef; color: #1d3557;
        transition: background .2s; position: relative; }
.node.min-node { background: #a8d5a2; border-color: #2d8a55; color: #185830; }
.node.marked { border-style: dashed; border-color: #e07b00; }
.children { display: flex; gap: 6px; margin-top: 6px; }
.connector { width: 100%; height: 8px; display: flex; justify-content: center; }
.connector::before { content: ''; width: 2px; background: #aab8c8; height: 100%; }
.empty-msg { color: #888; font-size: .9rem; align-self: center; padding: .5rem; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.3em; margin: .3rem 0 .1rem; color: #1d3557; }
.status.ok { color: #0a7d33; }
.status.warn { color: #b05000; }
.steps { font-size: .82rem; color: #555; }

// Code not found

Count the steps: decrease-key does constant work regardless of heap size. Extract-min does more work, but it cleans up multiple trees at once, so the cost is spread (amortized) over future operations. This is the same principle behind amortized analysis in dynamic shortest paths.

Fibonacci heaps are proven to achieve these amortized bounds (Fredman & Tarjan, 1987):

Why it works — the potential method. The proof assigns a potential $\Phi$ = (number of roots) + 2 × (number of marked nodes). Every cheap operation increases $\Phi$ slightly; extract-min decreases $\Phi$ a lot while doing real work. When you add actual cost + change in potential, every operation averages out.

The Fibonacci numbers appear because of the degree-bounding lemma: after consolidation, a root of degree $k$ has at least $F_{k+2}$ descendants (a Fibonacci number). This keeps tree degrees bounded at $O(\log n)$, ensuring extract-min never does more than $O(\log n)$ work.

Why not use them everywhere? The constant factors are large and the structure is complex to implement correctly. For graphs with few decrease-key calls, a binary heap or even a pairing heap wins in practice. Fibonacci heaps shine when $E \gg V$, precisely the dense-graph regime where $O(E + V \log V)$ beats $O((E + V) \log V)$.

There is no P vs NP mystery here — Fibonacci heaps are a solved, proven structure. The open question is whether the $O(\log n)$ extract-min is improvable: it is known to be $\Omega(\log n)$ for any comparison-based heap, so the structure is asymptotically optimal.

The $O(1)$ amortized decrease-key changes the complexity of every algorithm that issues many such calls:

• Dijkstra's algorithm: with a binary heap, complexity is $O((E+V)\log V)$. With a Fibonacci heap it drops to $O(E + V \log V)$. On dense graphs ($E \approx V^2$) this is the difference between $O(V^2 \log V)$ and $O(V^2)$ — a real win.
• Prim's MST algorithm: the same decrease-key argument applies; Fibonacci heaps give $O(E + V \log V)$ for minimum spanning trees.
• Min-cost flow: network simplex and successive shortest path algorithms issue large numbers of priority updates; Fibonacci heaps are the theoretical tool of choice.
• Graph algorithms research: any algorithm paper that wants to claim tight complexity for graph problems involving a priority queue will reach for the Fibonacci heap as the standard yardstick.

In practice, pairing heaps and rank-pairing heaps often match Fibonacci heap performance with simpler code. But the Fibonacci heap remains the theoretical benchmark: it is the structure that first proved $O(1)$ decrease-key was achievable, and it is still the only one with a clean, fully proven potential-function argument.

Fibonacci heaps are a lesson in strategic laziness. By refusing to reorganize until the last possible moment — just tossing decreased nodes onto a root list and only consolidating during extract-min — Fredman and Tarjan achieved what every algorithm designer wanted: $O(1)$ amortized decrease-key.

That single bound unlocks the textbook complexity of Dijkstra ($O(E + V \log V)$), Prim, and a family of network-flow algorithms. The Fibonacci numbers in the name are not decoration: they bound the degree of trees after consolidation and are the key to the entire proof.

The structure is complex to implement, but the idea is simple: charge expensive work against the cheap work that created the mess. That is amortized analysis in its purest form — and it is the same reasoning that underlies dynamic shortest paths and every data structure that trades occasional big costs for a long string of near-free operations.