AlgoVerse

Binomial heap

A forest of binomial trees of distinct degrees, like the binary digits of n; merging two heaps works like adding two binary numbers and takes O(log n).

The binomial tree of degree k, B_k, is two copies of B_{k−1} with one root made a child of the other. So it has 2^k nodes and its root has k children.

Read the full explanation ↓
Input:
n=8PDF export

Seven inserts: 7 = 111 in binary, so three trees of 1, 2 and 4 nodes remain. Then an extract-min.

  1. class Node:
  2. def __init__(self, key):
  3. self.key = key
  4. self.degree = 0
  5. self.children = [] # in increasing degree
  8. def binomial_heap(ops):
  9. heap = [] # the root list, in increasing degree
  10. removed = []
  11. for x in ops:
  12. if x > 0:
  13. union(heap, [Node(x)])
  14. elif not heap:
  15. continue
  16. else:
  17. m = heap[0]
  18. for r in heap:
  19. if r.key < m.key:
  20. m = r
  21. heap.remove(m)
  22. removed.append(m.key)
  23. union(heap, m.children)
  24. return removed
  27. def union(heap, other):
  28. # Merge the two root lists by degree, then link trees of equal degree, like adding binary numbers.
  29. heap.extend(other)
  30. heap.sort(key=lambda t: t.degree)
  31. i = 0
  32. while i < len(heap) - 1:
  33. x = heap[i]
  34. nx = heap[i + 1]
  35. if x.degree != nx.degree:
  36. i = i + 1
  37. elif i + 2 < len(heap) and heap[i + 2].degree == x.degree:
  38. i = i + 1
  39. elif x.key <= nx.key:
  40. link(nx, x)
  41. heap.pop(i + 1)
  42. else:
  43. link(x, nx)
  44. heap.pop(i)
  47. def link(y, z):
  48. # Two trees of degree k become one of degree k + 1: y goes under z.
  49. z.children.append(y)
  50. z.degree = z.degree + 1

Invariant: Each tree is heap-ordered, a tree of degree k has exactly 2^k nodes, and after each union no two roots share a degree.

Start

∅

removed—

Local variables

Orange = changed in this step

ops list

12725152833410

Call stack

  1. binomial_heap()line 8
Step 1 of 207
Black = inserted, extracted · Orange = key stepmerged: 0/8 · inserted: 0/7 · link: 0/6 · min_root: 0/1 · three_alike: 0/1 · extracted: 0/1
    Explanation

    Binomial trees

    The binomial tree of degree k, B_k, is two copies of B_{k−1} with one root made a child of the other. So it has 2^k nodes and its root has k children.

    Binomial heaps

    A collection of heap-ordered binomial trees, at most one of each degree. The trees present are exactly the 1 digits of n in binary, so there are at most ⌊log n⌋ + 1 of them.

    Union is binary addition

    Put the two root lists side by side in order of degree. Wherever two trees share a degree, link them: the larger root goes under the smaller, giving one tree of the next degree, like a carry in addition. If three trees of one degree sit together, step over the first and link the next two.

    • Insert: union with a one-node heap.
    • Extract-min: the minimum is one of the roots; take it out and union its children (themselves a binomial heap) back in.

    The input

    A positive number is inserted and 0 means extract-min.