Fibonacci Heap & Hollow Heap
Python 3 implementations of a Fibonacci heap and a Hollow heap. The both heaps have exceptional low amortised running times.
The Hollow heap implementation is based on the paper Hollow Heaps (2015) by Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan & Uri Zwick.
The Fibonacci heap implementation a is well-known algorithm from the the paper Fibonacci Heaps And Their Uses In Improved Network Optimization Algorithms (1984) by Michael L. Fredman and Robert E. Tarjan.
Amortized Time Complexity
The special thing about Fibonacci Heap and Hollow Heap is their low amortized time complexity. Their amortized running times are lower than binary heap or binomial heap has.
| Method | Fibonacci | Hollow | Binary | Binomial |
|---|---|---|---|---|
| find_min | O(1) | O(1) | O(1) | O(1) |
| insert | O(1) | O(1) | O(log n) | O(1) |
| delete | O(log n) | O(log n) | O(log n) | O(log n) |
| decrease_key | O(1) | O(1) | O(log n) | O(log n) |
| merge | O(1) | O(1) | O(n) | O(log n) |
Fibonacci Heap
The Fibonacci heap uses multiple trees. Every node has degree at most log(n) and the size of subtrees are related to Fibonacci sequence. You can read more about from Wikipedia.
Here is a visualiation of the Fibonacci heap when nodes are deleted.
Hollow Heap
The Hollow heap achives the same running times as the Fibonacci heap by using lazy deletion and a directed acyclic graph instead of a tree. You can read more about from the white paper Hollow Heaps.
Here is a visualiation of the Hollow heap when nodes are deleted.
Example
from hollow_heap import HollowHeap
from fibonacci_heap import FibonacciHeap
# Create an empty heap
heap = FibonacciHeap() # = HollowHeap()
# Insert a node with properties
# key = 10
# val = 10
nodeA = heap.insert(10)
# Insert a node with properties
# key = 12
# val = "B"
nodeB = heap.insert(12, "B")
# Return the smallest node -> nodeA
n = heap.find_min()
# Decrease the key of nodeB from 12 to 3
nodeB = heap.decrease_key(nodeB, 3)
# Delete the nodeB
heap.delete(nodeB)
# Delete the min node -> nodeA
heap.delete_min()
# Merge heap2 into heap
heap2 = FibonacciHeap() # = HollowHeap()
heap2.insert(8)
heap.merge(heap2)Visualization
You can visualize the heaps by using visualize/visualize.py
from visualize.visualize import visualize
from hollow_heap import HollowHeap
heap = HollowHeap()
nodeA = heap.insert(1)
nodeB = heap.insert(2)
visualize(heap, title="Title", highlight=nodeB)Tests
To run unittests, run command $ python tests.py
Licence
MIT License Copyright (c) 2020 Frans L