In this tick you will implement the Fibonacci Heap. This is an intricate data structure – for some of you, perhaps the most intricate programming you have yet programmed. If you haven’t already completed the dis-set tick, that’s a good warmup.
The first step is to implement a FibNode class to
represent a node in the Fibonacci heap, and a FibHeap class
to represent the entire heap. Each FibNode should store its priority key
k, and the FibHeap should store a list of root nodes as
well as the minroot.
Then implement the FibHeap methods: _push(n,k),
_decreasekey(n,k), and _popmin(), where
n is a FibNode, and _popmin returns a FibNode.
To implement these efficiently, it’s helpful to store within each
FibNode not only its children but also its parent and its immediate
siblings; see lecture notes section 7.7 for details.
The tester only tests if your code is correct—it’s up to you to make sure you use an efficient implementation. But the tester runs tests on up to \(n=100\,000\) items, so if your code isn’t as asymptotically efficient as the Fibonacci Heap then it will probably time out!
When we’re using a Fibonacci heap, for example in Dijkstra’s
algorithm, we want to use it to store ‘external’ items such as graph
vertices, and we want methods such as decreasekey(x,k)
where x is an external item.
Modify your FibHeap class to store a dictionary mapping
external items to FibNode objects, and modify your
FibNode class to store the external item for that node.
Then, implement decreasekey(x,k) to (1) look up the FibNode
for item x in the dictionary, (2) call
_decreasekey(n,k) on that node. Also implement appropriate
push(x,k) and popmin() methods.
The code snippet below shows how this works in practice, for Dijkstra’s algorithm. The external items are graph vertices. The heap can use its dictionary to find the FibNode for a given graph vertex, and it can return the graph vertex for a FibNode it popped. The code for Dijkstra’s algorithm only ever works with graph vertices, and doesn’t know anything about FibNode internals.
Please submit a source file fibheap.py to Moodle. It should implement the following class:
class FibHeap:
def push(self, x, k):
# push a new item x into the heap, with priority k
def decreasekey(self, x, k):
# decrease the priority for item x to k
def popmin(self):
# returns an item whose priority is minimal in the heap
def __contains__(self, x):
# returns True if the heap contains item x, False otherwise
def __bool__(self):
# returns True if the heap has any items at all, False otherwiseThe __contains__(self,x) method is invoked by Python
when we use the keyword in. Dijkstra’s algorithm uses this
in the line if w in toexplore. It’s easy to implement: just
check if x is in the FibHeap’s dictionary.
The __bool__(self) method is the standard way in Python
for a data structure to report whether or not it has any elements, and
it’s invoked when we use an expression that expects a boolean, for
example the line while toexplore in the Dijkstra code
below.
Here is a dummy implementation of a heap, and an illustration of how we’d use it in practice. The DummyHeap stores a dictionary whose keys are Vertex objects. (Python lets us use arbitrary objects as dictionary keys.) We could alternatively have implemented the algorithm by storing vertex ids in the heap, and maintaing a separate dictionary that maps vertex id to vertex object. Or we could have implemented it all using dictionaries, avoiding objects altogether.
class DummyHeap:
def __init__(self):
self.dict = {}
def push(self, x, k):
if x in self.dict:
raise ValueError(f"push item {x} which is already in the heap")
self.dict[x] = k
def decreasekey(self, x, k):
if x not in self.dict:
raise KeyError(f"decreasekey for item {x} not in the heap")
self.dict[x] = k
def popmin(self):
if not self.dict:
raise IndexError("popmin from empty heap")
mink = min(k for k in self.dict.values())
x = next(x for x,k in self.dict.items() if k==mink)
del self.dict[x]
return x
def __bool__(self):
return bool(self.dict)
def __contains__(self, x):
return (x in self.dict)
class Vertex:
def __init__(self, id):
self.id = id
self.distance = None
def __str__(self):
return f"vertex({self.id})"
def dijkstra(g, s):
for v in g:
v.distance = float('inf')
s.distance = 0
toexplore = DummyHeap()
toexplore.push(s, s.distance)
while toexplore:
v = toexplore.popmin()
for w,edgecost in g[v]:
dist_w = v.distance + edgecost
if dist_w < w.distance:
w.distance = dist_w
if w in toexplore:
toexplore.decreasekey(w, w.distance)
else:
toexplore.push(w, w.distance)
if __name__ == "__main__":
s,t,v,u = [Vertex(id) for id in ['s','t','v','u']]
g = {s: [(t,2), (v,3)], t:[(u,2)], u:[(v,1)], v:[(t,4)]}
dijkstra(g, s)
for v in g:
print(f"distance from s to {v} is {v.distance}")