Skip to content
Tutorials Center
My learning

Topics

Lesson 111 of 225 ยท Heaps

Fibonacci, Binomial and d-ary Heaps

Learn d-ary, binomial and Fibonacci heaps in Python: how they differ from a binary heap, mergeable heaps, decrease-key, amortized costs and when they matter.

The binary heap is the workhorse: simple, compact, and fast in practice. It gives O(log n) push and pop. But it has two weak spots. Merging two binary heaps takes O(n), because you must rebuild. And decrease-key (making an item's priority better) needs you to first find the item, which a plain heap cannot do quickly.

Other heap designs trade simplicity for better bounds on those operations. This lesson tours three of them: the d-ary heap (a small tweak that is often faster in practice), the binomial heap (a heap that merges in O(log n)), and the Fibonacci heap (decrease-key in O(1) amortized, which gives the best known bound for Dijkstra's algorithm). You will build all three, and learn why most programmers still reach for heapq.

The operations we compare

Operation Binary heap d-ary heap Binomial heap Fibonacci heap
insert O(log n) O(log_d n) O(1) amortized O(1)
find-min O(1) O(1) O(log n) (O(1) with a pointer) O(1)
extract-min O(log n) O(d log_d n) O(log n) O(log n) amortized
decrease-key O(log n)* O(log_d n)* O(log n) O(1) amortized
merge two heaps O(n) O(n) O(log n) O(1)

* Assumes you already know the item's position in the array.

Do not memorize the table yet. Each section below explains where its column comes from.

d-ary heaps

A binary heap's tree gives each node 2 children. A d-ary heap gives each node up to d children, stored in the same flat array:

TEXT
d = 3, array indexes
              0
        /     |     \
       1      2      3
     / | \  / | \  / | \
    4  5 6 7  8 9 10 11 12

parent(i)   = (i - 1) // d
children(i) = d*i + 1 ... d*i + d

With d = 2 this is the binary heap you know. Larger d makes the tree shallower: the height is about log_d n instead of log_2 n.

  • Push / decrease-key move an item up, one comparison per level. Shallower tree, so fewer steps.
  • Pop moves an item down, and at each level must find the smallest of d children. That is up to d comparisons per level, so more work per level: O(d log_d n) in total.

If a program does many pushes or decrease-keys but fewer pops, a larger d wins. Dijkstra's algorithm on a dense graph is the classic case: up to E decrease-key operations but only V pops, so choosing d near E/V balances the costs. Large d also helps the CPU cache, since the d children sit next to each other in memory (see Memory and Data Layout).

Python A d-ary heap with comparison counts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the pattern: as d grows, the pushes need steadily fewer comparisons, while the pops cost about the same up to d = 3 and clearly more from d = 4 on. A d of 3 or 4 is a common compromise. In Python the interpreter overhead dominates, so heapq (written in C, binary) beats any pure-Python d-ary heap; the idea matters in systems languages and for reasoning about trade-offs.

Mergeable heaps and the binomial heap

Sometimes you need to merge two priority queues into one: combining the pending-task lists of two workers, for instance. With arrays, merging means copying and re-heapifying: O(n). A mergeable heap merges in O(log n) or better.

The binomial heap gets there with a lovely analogy to binary numbers.

A binomial tree B_k has order k and exactly 2^k nodes. B_0 is a single node. B_k is made by taking two B_(k-1) trees and making one root a child of the other (the smaller key stays on top, to keep heap order):

TEXT
B0: o            B1: o          B2:   o              B3: (two B2's linked)
                     |              / |
                     o             o  o
                                      |
                                      o

A binomial heap is a list of binomial trees with at most one tree of each order, each obeying the min-heap rule. Because every tree has a power-of-two size, a heap with n nodes has exactly the trees that match the 1-bits of n in binary. A heap with 13 nodes (1101 in binary) has trees B_3, B_2 and B_0.

TEXT
n = 13 = 8 + 4 + 1   ->   trees B3, B2, B0

Merging two heaps is just binary addition with carries: when two trees have the same order, link them into one tree of the next order (the carry). There are at most log2(n) + 1 orders, so merging costs O(log n). Insert is a merge with a one-node heap; extract-min finds the smallest root (at most log n roots), removes it, and merges its children (which are trees of every smaller order) back in.

Python A binomial heap (merge like binary addition)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The tree orders always match the 1-bits of the size: the proof is that a binomial heap is just a binary counter whose "digits" are trees.

Fibonacci heaps

The Fibonacci heap is a binomial heap made lazy. The idea: do not tidy up until you have to. It keeps a circular list of heap-ordered trees (the root list) with a pointer to the minimum root.

  • insert: add a one-node tree to the root list. O(1).
  • merge: join two root lists. O(1).
  • extract-min: remove the minimum root, promote its children to the root list, then consolidate: link roots of equal degree (number of children) until all roots have different degrees. This cleanup pays for all the lazy work. O(log n) amortized (see Amortized Analysis).
  • decrease-key: lower the key. If it is now smaller than its parent, cut the node from its parent and make it a new root: O(1). To keep trees bushy, each node may lose at most one child before it is itself cut too (a mark bit, with a cascading cut). That guarantees a node of degree k has at least F(k+2) descendants, a Fibonacci number, which is where the name comes from and why the maximum degree is only O(log n).

The result: insert, merge and decrease-key are O(1) amortized; extract-min is O(log n) amortized.

Amortized means averaged over a sequence of operations. A single extract-min can take O(n) when the root list is long, and a single decrease-key may trigger a long cascading cut. Only the total over many operations is bounded.

Python A Fibonacci heap with decrease-key

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A few details worth studying in the code: extract_min first collects the other roots plus the dead root's children into a plain list, then _consolidate rebuilds the root list from scratch, linking equal degrees like binary carries. decrease_key is the star: it never searches, because the caller keeps the node handle returned by insert.

Why Dijkstra cares

Dijkstra's algorithm repeatedly pops the closest unvisited vertex and relaxes its edges, which may lower ("decrease") the distance of other vertices. With V vertices and E edges:

  • binary heap with decrease-key: O((V + E) log V)
  • Fibonacci heap: O(E + V log V), because the E decrease-keys are O(1) each.

On paper, that is the best bound. In practice, Fibonacci heaps have large constants and many pointers, so cache misses dominate. Benchmarks rarely favor them unless graphs are very large and dense.

The practical alternative: lazy deletion with heapq

Python's heapq has no decrease-key. The standard workaround is lazy deletion: push a new entry with the better priority, and when you later pop an outdated entry, just skip it. The heap grows to at most E entries, so the cost is O(E log E) = O(E log V), almost as good.

Python Decrease-key by lazy deletion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Choosing a heap

Situation Best choice
General-purpose priority queue in Python heapq (binary, C speed)
Lots of pushes, few pops, or cache-bound code in a systems language d-ary heap, d = 4 is common
Need to merge priority queues repeatedly Binomial or Fibonacci (or a leftist or pairing heap)
Theory: Dijkstra/Prim with the best asymptotic bound Fibonacci heap
Need to change priorities of existing items Indexed heap, or lazy deletion

The pairing heap deserves a mention: far simpler than a Fibonacci heap, with similar practical behavior, and often the best choice when you really need mergeable heaps with decrease-key.

Common mistakes

  • Assuming amortized equals worst case. A Fibonacci heap's single operations can be slow.
  • Forgetting the node handle. Decrease-key only works in O(1) if you keep a reference to the node (or a position map) from insertion.
  • Increasing a key with decrease-key. The operation only lowers priorities; raising one needs a delete and re-insert.
  • Choosing exotic heaps without measuring. Constant factors decide in practice.
  • Mixing keys of different types in heap entries, which makes comparisons fail.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a larger d do in a d-ary heap?

    A larger d gives a shallower tree, so items move up in fewer steps, but each step down must scan up to d children.
  2. 2. A binomial heap contains 13 items. Which tree orders does it hold?

    13 is 1101 in binary, which is 8 + 4 + 1, so the heap has one tree each of order 3, 2 and 0.
  3. 3. How long does it take to merge two binomial heaps with n items in total?

    Merging works like binary addition over at most log n + 1 tree orders, linking trees of equal order as carries.
  4. 4. Which operation is O(1) amortized in a Fibonacci heap but O(log n) in a binary heap?

    Decrease-key just cuts the node out and adds it to the root list; the cleanup is deferred to extract-min.
  5. 5. Python's heapq has no decrease-key. What is the usual workaround?

    Lazy deletion leaves the old entry in the heap and ignores it later, which costs only a little extra space and time.

Summary

  • A d-ary heap is a binary heap with d children per node: faster pushes and decrease-keys, slower pops, and cache-friendly.
  • A binomial heap is a set of binomial trees that mirrors the binary representation of n; merging is binary addition in O(log n).
  • A Fibonacci heap is lazy: O(1) insert, merge and decrease-key (amortized), O(log n) amortized extract-min, giving Dijkstra O(E + V log V).
  • Constant factors make heapq with lazy deletion the practical choice in Python.
  • Amortized bounds average over sequences of operations; keep node handles to use decrease-key.

Next: Tries