A Fibonacci-kupac egy haladó adatstruktúra, amely hatékonyan támogatja a prioritási sor műveleteit. Ez különösen hasznos grafalgoritmusokban, például a Dijkstra algoritmusban vagy a Prim algoritmusban, ahol gyakran kell minimális elemeket keresni vagy prioritást csökkenteni.
Insert)
Find-Min)
Extract-Min)
Decrease-Key)
Union)
function Insert(heap, key):
node = create_node(key)
add_to_root_list(heap, node)
if heap.min is None or key < heap.min.key:
heap.min = node
heap.size += 1
function Find-Min(heap):
return heap.min
function Extract-Min(heap):
z = heap.min
if z is not None:
for each child in z.children:
add_to_root_list(heap, child)
child.parent = None
remove_from_root_list(heap, z)
if z == z.next:
heap.min = None
else:
heap.min = z.next
Consolidate(heap)
heap.size -= 1
return z
function Decrease-Key(heap, node, new_key):
if new_key > node.key:
return "Error: New key is greater than current key"
node.key = new_key
y = node.parent
if y is not None and node.key < y.key:
Cut(heap, node, y)
Cascading-Cut(heap, y)
if node.key < heap.min.key:
heap.min = node
Az alábbi kód egy egyszerű Fibonacci-kupac implementáció:
class FibonacciNode:
def __init__(self, key):
self.key = key
self.parent = None
self.child = None
self.degree = 0
self.mark = False
self.next = self
self.prev = self
class FibonacciHeap:
def __init__(self):
self.min = None
self.size = 0
def insert(self, key):
node = FibonacciNode(key)
if self.min is None:
self.min = node
else:
self._add_to_root_list(node)
if key < self.min.key:
self.min = node
self.size += 1
return node
def find_min(self):
return self.min.key if self.min else None
def extract_min(self):
z = self.min
if z is not None:
if z.child is not None:
children =
for child in children:
self._add_to_root_list(child)
child.parent = None
self._remove_from_root_list(z)
if z == z.next:
self.min = None
else:
self.min = z.next
self._consolidate()
self.size -= 1
return z.key if z else None
def _add_to_root_list(self, node):
if self.min is None:
self.min = node
else:
node.prev = self.min
node.next = self.min.next
self.min.next.prev = node
self.min.next = node
def _remove_from_root_list(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _consolidate(self):
degrees = {}
nodes =
for node in nodes:
degree = node.degree
while degree in degrees:
other = degrees.pop(degree)
if node.key > other.key:
node, other = other, node
self._link(other, node)
degree += 1
degrees = node
self.min = None
for node in degrees.values():
if self.min is None or node.key < self.min.key:
self.min = node
def _link(self, y, x):
self._remove_from_root_list(y)
y.parent = x
if x.child is None:
x.child = y
else:
self._add_to_root_list(y, x.child)
x.degree += 1
y.mark = False
def _iterate(self, start):
node = stop = start
while True:
yield node
node = node.next
if node == stop:
break
# Használat
fib_heap = FibonacciHeap()
fib_heap.insert(10)
fib_heap.insert(3)
fib_heap.insert(15)
print(fib_heap.find_min()) # 3
fib_heap.extract_min()
print(fib_heap.find_min()) # 10
Egy C++ implementáció bonyolultabb a pointerek miatt, de hasonló struktúrát követ. Ha szeretnél, készítek egy konkrét példát.
A Fibonacci-kupac hatékony és gyakran használt haladó algoritmusokban, különösen a grafalgoritmusoknál!