The implementation is in fibheap.py. It defines a FibHeap class, which stores hashable objects, and requires a key function (object → priority key).
from fibheap import FibHeap
# In this example, the objects being stored are just plain strings,
# and my key function is a static function that looks up in a dict.
priority = {'a':0, 'b':1, 'c':2, 'd':3, 'e':4, 'f':5, 'g':6, 'h':7, 'i':8}
heap = FibHeap(sortkey=lambda x: priority[x])
for x in priority.keys():
heap.push(x)
print(heap)
print("pop", heap.popmin())
print(heap)
print("decreasekey(f)")
priority['f'] = 0
heap.decreasekey('f')
print(heap)
priority['h'] = 5
heap.decreasekey('h')
print(heap)
priority['e'] = 1
heap.decreasekey('e')
priority['g'] = 0
heap.decreasekey('g')
priority['j'] = 2
heap.push('j')
print(heap)
print("pop", heap.popmin())
print(heap)
priority['i'] = -1
heap.decreasekey('i')
priority['h'] = -1
heap.decreasekey('h')
print("pop", heap.popmin())
print("pop", heap.popmin())
print(heap)
.
|a(0)
|i(8)
|h(7)
|g(6)
|f(5)
|e(4)
|d(3)
|c(2)
|b(1)
'
pop a
.
|b(1)+i(8)
| +c(2)+d(3)
| | \e(4)-f(5)
| \g(6)-h(7)
'
decreasekey(f)
.
|f(0)
|b(1)+i(8)
| +c(2)+d(3)
| | \{e(4)}
| \g(6)-h(7)
'
.
|f(0)
|h(5)
|b(1)+i(8)
| +c(2)+d(3)
| | \{e(4)}
| \{g(6)}
'
.
|f(0)
|j(2)
|g(0)
|e(1)
|h(5)
|b(1)+i(8)
| \{c(2)}-d(3)
'
pop f
.
|g(0)+j(2)
| +b(1)+i(8)
| | \{c(2)}-d(3)
| \e(1)-h(5)
'
pop i
pop h
.
|g(0)+j(2)
| +{b(1)}-{c(2)}-d(3)
| \{e(1)}
'
# The same Dijkstra example from graphs.ipynb
# Here the Fibonacci heap stores Vertex objects, and we tell it how
# to get at the key from a Vertex.
from ucamcl_alg_utils import DirectedGraph
def dijkstra(g, s):
for v in g.vertices:
v.distance = float('inf')
s.distance = 0
toexplore = FibHeap([s], sortkey = lambda v: v.distance)
while not toexplore.is_empty():
v = toexplore.popmin()
# assert: v.distance is the true shortest distance from s to v
# assert: v is never put back into toexplore
for w,edgecost in v.neighbours:
dist_w = v.distance + edgecost
if dist_w < w.distance:
w.distance = dist_w
if w in toexplore:
toexplore.decreasekey(w)
else:
toexplore.push(w)
g = DirectedGraph([('s','t',2), ('s','v',3), ('t','u',2), ('u','v',1), ('v','t',4)])
dijkstra(g, g.vertex['s'])
for v in g.vertices:
print(f"distance from s to {v} is {v.distance}")
distance from s to u is 4 distance from s to s is 0 distance from s to t is 2 distance from s to v is 3
This is the LazyForest implementation of DisjointSet. Most of the code is for pretty-printing!
class DisjointSet:
class DSNode:
def __init__(self, k):
self.k = k
self.parent = self
self.rank = 1
def __init__(self, ks=[]):
self._nodes = {k:DisjointSet.DSNode(k) for k in ks}
def add_singleton(self, k):
self._nodes[k] = DisjointSet.DSNode(k)
def get_set_with(self, k):
n = self._nodes[k]
root = n
while root != root.parent:
root = root.parent
# path compression heuristic
while n != root:
n.parent, n = root, n.parent
return root
def merge(self, n1, n2):
if n1 == n2:
return
# weighted union heuristic
m1,m2 = (n1,n2) if n1.rank >= n2.rank else (n2,n1)
m1.rank = m1.rank + m2.rank
m2.parent = m1
# Rather intricate pretty-printing routine, to show the shape of the data structure
def __str__(self):
roots = [n for n in self._nodes.values() if n.parent == n]
all_children = {n:[] for n in self._nodes.values()}
for n in self._nodes.values():
if n.parent != n:
all_children[n.parent].append(n)
if not roots:
return "Empty set"
res = '\n'.join(self._nodestr(n, all_children) for n in roots)
res = ['.'] + ['|'+r for r in res.splitlines()] + ["'"]
return '\n'.join(res)
def _nodestr(self, n, children):
self_str = str(n.k)
if not children[n]:
return self_str
res = []
cs = [self._nodestr(c, children) for c in children[n]]
imax = len(cs) - 1
for i,c in enumerate(cs):
ls = c.splitlines()
jmax = len(ls) - 1
for j,l in enumerate(ls):
if j>0 and i==imax:
pipe = ' '
elif j>0:
pipe = '|'
elif imax==0:
pipe = '-'
elif i<imax:
pipe = '+'
else:
pipe = '\\'
r = self_str if i==0 and j==0 else ' '*len(self_str)
res.append(r + pipe + l)
return '\n'.join(res)
from ucamcl_alg_utils import UndirectedGraph
g = UndirectedGraph([('a','b',2), ('a','c',9), ('b','c',6), ('b','d',5), ('b','e',8), ('c','e',3),
('c','f',4), ('d','e',7), ('e','f',1)])
partition = DisjointSet(g.vertices)
edges = sorted(g.edges, key = lambda e: e[2])
print(partition)
for (u,v,edgeweight) in edges:
p = partition.get_set_with(u)
q = partition.get_set_with(v)
print(f"after searching for {u} and {v}")
print(partition)
if p != q:
partition.merge(p, q)
print(f"after merging {u}--{v}")
print(partition)
. |b |a |f |d |e |c ' after searching for e and f . |b |a |f |d |e |c ' after merging e--f . |b |a |d |e-f |c ' after searching for a and b . |b |a |d |e-f |c ' after merging a--b . |a-b |d |e-f |c ' after searching for c and e . |a-b |d |e-f |c ' after merging c--e . |a-b |d |e+f | \c ' after searching for c and f . |a-b |d |e+f | \c ' after searching for b and d . |a-b |d |e+f | \c ' after merging b--d . |a+b | \d |e+f | \c ' after searching for b and c . |a+b | \d |e+f | \c ' after merging b--c . |a+b | +d | \e+f | \c ' after searching for d and e . |a+b | +d | \e+f | \c ' after searching for b and e . |a+b | +d | \e+f | \c ' after searching for a and c . |a+b | +d | +e-f | \c '