Introduction

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)O(\log n). That gives Dijkstra an overall complexity of O((E+V)log⁡V)O((E + V) \log V), where EE is edges and VV 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)O(1). The result: Dijkstra runs in O(E+Vlog⁡V)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.

Try It: Lazy Melding

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">A <b>Fibonacci heap</b> keeps a loose list of heap-ordered trees. Insert and decrease-key just add to the list — <em>no cleanup</em>. Only Extract Min consolidates, linking trees of equal degree. Watch the step counter: decrease-key always costs O(1).</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">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="new key">
    <button id="btn-dec" type="button">Decrease-key</button>
  </div>
  <div class="input-row">
    <button id="btn-extract" type="button">Extract Min</button>
    <button id="btn-reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Fibonacci Heap — lazy melding demo
// All keys are positive integers. The heap stores node objects with:
//   key, id, degree, marked, parent, children (array)
// Root list is kept as a plain array (no circular linked list — visual clarity).

let idSeq = 0;
let roots = [];          // root list
let nodeMap = {};        // id -> node (for decrease-key)
let minRoot = null;
let opSteps = 0;         // steps for last operation
let totalOps = 0;
let totalSteps = 0;

function makeNode(key) {
  return { key, id: ++idSeq, degree: 0, marked: false, parent: null, children: [] };
}

// Insert: add new singleton tree to root list. O(1) actual.
function insert(key) {
  opSteps = 0;
  const n = makeNode(key);
  nodeMap[n.id] = n;
  roots.push(n); opSteps++;
  if (!minRoot || n.key < minRoot.key) minRoot = n;
  opSteps++;
  return n;
}

// Decrease-key: cut node from parent (if any), add to root list. O(1) amortized.
function decreaseKey(node, newKey) {
  opSteps = 0;
  if (newKey >= node.key) return false;
  node.key = newKey; opSteps++;
  const p = node.parent;
  if (p && node.key < p.key) {
    cut(node, p); opSteps++;
    cascadingCut(p);
  }
  if (node.key < (minRoot ? minRoot.key : Infinity)) { minRoot = node; opSteps++; }
  return true;
}

function cut(node, parent) {
  parent.children = parent.children.filter(c => c !== node);
  parent.degree--;
  node.parent = null;
  node.marked = false;
  roots.push(node); opSteps++;
}

function cascadingCut(node) {
  const p = node.parent;
  if (!p) return;
  if (!node.marked) { node.marked = true; opSteps++; }
  else { cut(node, p); opSteps++; cascadingCut(p); }
}

// Extract-min: remove min, add its children to root list, consolidate. O(log n) amortized.
function extractMin() {
  opSteps = 0;
  if (!minRoot) return null;
  const z = minRoot;
  // Add children of min to root list
  for (const child of z.children) {
    child.parent = null;
    roots.push(child); opSteps++;
  }
  roots = roots.filter(r => r !== z); opSteps++;
  delete nodeMap[z.id];
  if (roots.length === 0) { minRoot = null; return z; }
  // Consolidate
  const A = {};
  for (const w of [...roots]) {
    let x = w, d = x.degree;
    while (A[d]) {
      let y = A[d];
      if (x.key > y.key) { const tmp = x; x = y; y = tmp; }
      // link y under x
      y.parent = x;
      x.children.push(y);
      x.degree++;
      delete A[d];
      d++; opSteps++;
    }
    A[d] = x; opSteps++;
  }
  roots = Object.values(A);
  minRoot = roots.reduce((m, r) => r.key < m.key ? r : m, roots[0]); opSteps++;
  return z;
}

// ── Rendering ──────────────────────────────────────────────────────────────────
function renderNode(node) {
  const wrap = document.createElement('div');
  wrap.className = 'tree';
  const el = document.createElement('div');
  el.className = 'node' + (node === minRoot ? ' min-node' : '') + (node.marked ? ' marked' : '');
  el.textContent = node.key;
  el.title = 'id=' + node.id + (node.marked ? ' [marked]' : '');
  wrap.appendChild(el);
  if (node.children.length > 0) {
    const conn = document.createElement('div'); conn.className = 'connector'; wrap.appendChild(conn);
    const ch = document.createElement('div'); ch.className = 'children';
    for (const c of node.children) ch.appendChild(renderNode(c));
    wrap.appendChild(ch);
  }
  return wrap;
}

function render() {
  const vis = document.getElementById('heap-vis');
  vis.innerHTML = '';
  if (roots.length === 0) {
    const em = document.createElement('div'); em.className = 'empty-msg';
    em.textContent = 'Heap is empty. Insert some nodes!'; vis.appendChild(em);
  } else {
    for (const r of roots) vis.appendChild(renderNode(r));
  }
  // Rebuild select
  const sel = document.getElementById('sel-node');
  sel.innerHTML = '';
  const allNodes = getAllNodes();
  for (const n of allNodes) {
    const opt = document.createElement('option');
    opt.value = n.id; opt.textContent = 'id=' + n.id + ' (key=' + n.key + ')';
    sel.appendChild(opt);
  }
  if (allNodes.length === 0) {
    const opt = document.createElement('option'); opt.textContent = '(empty)'; sel.appendChild(opt);
  }
}

function getAllNodes() {
  const out = [];
  function dfs(n) { out.push(n); for (const c of n.children) dfs(c); }
  for (const r of roots) dfs(r);
  out.sort((a,b) => a.key - b.key);
  return out;
}

function setStatus(msg, cls) {
  const s = document.getElementById('status'); s.textContent = msg; s.className = 'status ' + (cls||'');
}
function setSteps(msg) { document.getElementById('steps').textContent = msg; }

function logOp(opName) {
  totalOps++; totalSteps += opSteps;
  setSteps(fmt('Last op (%opName%): %opSteps% steps  |  Session avg: %v% steps/op over %totalOps% ops', { opName: opName, opSteps: opSteps, v: (totalSteps/totalOps).toFixed(1), totalOps: totalOps }));
}

// ── Seed with a few nodes ──────────────────────────────────────────────────────
function reset() {
  idSeq = 0; roots = []; nodeMap = {}; minRoot = null;
  opSteps = 0; totalOps = 0; totalSteps = 0;
  [30, 17, 24, 42, 7, 55, 13].forEach(k => insert(k));
  render();
  setStatus(fmt('Heap seeded with 7 nodes. Min = %v%.', { v: minRoot ? minRoot.key : '—' }), 'ok');
  setSteps('');
}

document.getElementById('btn-insert').addEventListener('click', () => {
  const v = parseInt(document.getElementById('val').value, 10);
  if (isNaN(v) || v < 1 || v > 99) { setStatus('Enter a key between 1 and 99.', 'warn'); return; }
  const n = insert(v);
  render();
  setStatus(fmt('Inserted key=%v%. Min=%key%. Root list size=%length%.', { v: v, key: minRoot.key, length: roots.length }), 'ok');
  logOp('insert');
});

document.getElementById('btn-dec').addEventListener('click', () => {
  const sel = document.getElementById('sel-node');
  const id = parseInt(sel.value, 10);
  const newKey = parseInt(document.getElementById('dec-val').value, 10);
  const node = nodeMap[id];
  if (!node) { setStatus('Select a node first.', 'warn'); return; }
  if (isNaN(newKey) || newKey >= node.key) {
    setStatus(fmt('New key must be less than current key (%key%).', { key: node.key }), 'warn'); return;
  }
  const oldKey = node.key;
  decreaseKey(node, newKey);
  render();
  setStatus(fmt('Decreased id=%id% from %oldKey% → %newKey%. Min=%key%.', { id: id, oldKey: oldKey, newKey: newKey, key: minRoot.key }), 'ok');
  logOp('decrease-key');
});

document.getElementById('btn-extract').addEventListener('click', () => {
  if (!minRoot) { setStatus('Heap is empty.', 'warn'); return; }
  const removed = extractMin();
  render();
  setStatus(fmt('Extracted min=%key%. Roots after consolidation: %length%.', { key: removed.key, length: roots.length }), 'ok');
  logOp('extract-min');
});

document.getElementById('btn-reset').addEventListener('click', reset);

// Verify: decrease-key on a non-root node costs O(1) amortized
// (only a constant number of pointer updates + possible cascading cuts,
//  but cascading cuts are charged against marked nodes created by prior operations)
function verifyDecreaseKey() {
  reset();
  // Build a multi-level tree by extracting and reinserting in a controlled way
  // First extract min to trigger consolidation
  extractMin(); // removes 7, consolidates
  // Now decrease a deep node
  const deepNode = getAllNodes().find(n => n.parent !== null);
  if (!deepNode) return { ok: true, note: 'no deep node after consolidation' };
  const oldKey = deepNode.key;
  const newKey = 1;
  decreaseKey(deepNode, newKey);
  const ok = deepNode.key === newKey && deepNode.parent === null && roots.includes(deepNode);
  return { ok, oldKey, newKey, steps: opSteps };
}
const v = verifyDecreaseKey();
console.assert(v.ok, 'decrease-key correctness check failed', v);
console.log('Demo verification:', v.ok ? 'PASS' : 'FAIL', v);
reset();
Result
Console

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.

The Real Complexity

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

Operation Amortized cost
Insert O(1)O(1)
Find-min O(1)O(1)
Decrease-key O(1)O(1)
Union (meld) O(1)O(1)
Extract-min O(log⁡n)O(\log n)
Delete O(log⁡n)O(\log n)

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 kk has at least Fk+2F_{k+2} descendants (a Fibonacci number). This keeps tree degrees bounded at O(log⁡n)O(\log n), ensuring extract-min never does more than O(log⁡n)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≫VE \gg V, precisely the dense-graph regime where O(E+Vlog⁡V)O(E + V \log V) beats O((E+V)log⁡V)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)O(\log n) extract-min is improvable: it is known to be Ω(log⁡n)\Omega(\log n) for any comparison-based heap, so the structure is asymptotically optimal.

Where It Matters

The O(1)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)O((E+V)\log V). With a Fibonacci heap it drops to O(E+Vlog⁡V)O(E + V \log V). On dense graphs (E≈V2E \approx V^2) this is the difference between O(V2log⁡V)O(V^2 \log V) and O(V2)O(V^2) — a real win.
  • Prim's MST algorithm: the same decrease-key argument applies; Fibonacci heaps give O(E+Vlog⁡V)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)O(1) decrease-key was achievable, and it is still the only one with a clean, fully proven potential-function argument.

Conclusion

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)O(1) amortized decrease-key.

That single bound unlocks the textbook complexity of Dijkstra (O(E+Vlog⁡V)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/fibonacci-heaps/Content licensed under CC BY-NC 4.0.