91 lines
2.7 KiB
Python
91 lines
2.7 KiB
Python
"""An implementation of a fibonacci heap."""
|
|
from __future__ import annotations
|
|
from math import log2, ceil
|
|
|
|
import exceptions
|
|
|
|
class FibonacciNode():
|
|
"""A node for the fibonacci heap."""
|
|
def __init__(self, element, value):
|
|
self.element = element
|
|
self.value = value
|
|
self.children = []
|
|
self.size = 1
|
|
|
|
def __len__(self):
|
|
return self.size
|
|
|
|
def __lt__(self, other: FibonacciNode):
|
|
return self.value < other.value
|
|
|
|
@property
|
|
def degree(self):
|
|
"""Return the degree (number of children) of the node."""
|
|
return len(self.children)
|
|
|
|
def add_child(self, child: FibonacciNode):
|
|
"""Adds a child to the node."""
|
|
self.children.append(child)
|
|
self.size += child.size
|
|
|
|
class FibonacciHeap():
|
|
"""The fibonacci heap."""
|
|
def __init__(self, element, value: int):
|
|
new_node = FibonacciNode(element, value)
|
|
self.roots = [new_node]
|
|
self.min = new_node
|
|
self.size = 1
|
|
|
|
def __len__(self):
|
|
return self.size
|
|
|
|
def merge(self, other: FibonacciHeap):
|
|
"""Merge two fibonacci heaps."""
|
|
self.roots += other.roots
|
|
self.size += other.size
|
|
if self.min is None or other.min < self.min:
|
|
self.min = other.min
|
|
|
|
def insert(self, element, value: int):
|
|
"""Insert an element into the heap."""
|
|
self.merge(FibonacciHeap(element, value))
|
|
|
|
def extract_min(self):
|
|
"""Extract the element with the smallest value."""
|
|
if self.min is None:
|
|
raise exceptions.HeapEmpty()
|
|
element = self.min.element
|
|
value = self.min.value
|
|
self.roots += self.min.children
|
|
self.roots.remove(self.min)
|
|
self.size -= 1
|
|
if self.roots == []:
|
|
self.min = None
|
|
else:
|
|
self._rearrange()
|
|
self.min = min(self.roots)
|
|
|
|
return element, value
|
|
|
|
def _rearrange(self):
|
|
heap_size = len(self)
|
|
required_roots = (0 if heap_size == 0 else
|
|
1 if heap_size == 1 else
|
|
ceil(log2(heap_size)))
|
|
|
|
while len(self.roots) > required_roots:
|
|
degree_array = [None for _ in range(required_roots)]
|
|
for root in self.roots:
|
|
root_degree = root.degree
|
|
if degree_array[root_degree] is None:
|
|
degree_array[root_degree] = root
|
|
else:
|
|
if degree_array[root_degree] < root:
|
|
degree_array[root_degree].add_child(root)
|
|
self.roots.remove(root)
|
|
else:
|
|
root.add_child(degree_array[root_degree])
|
|
self.roots.remove(degree_array[root_degree])
|
|
|
|
break
|