graphtage.fibonacci
A pure Python implementation of a Fibonacci Heap.
Many of the algorithms in Graphtage only require partially sorting collections, so we can get a speedup from using a Fibonacci Heap that has amortized constant time insertion.
fibonacci classes
FibonacciHeap
- class graphtage.fibonacci.FibonacciHeap(key: Callable[[T], Key] | None = None)
Bases:
Generic
[T
,Key
]A Fibonacci Heap.
- __init__(key: Callable[[T], Key] | None = None)
Initializes a Fibonacci heap.
- Parameters:
key –
An optional function that accepts an item and returns the key to be used for comparing that item. If omitted, it is equivalent to:
lambda item: item
- clear()
Removes all items from this heap.
- decrease_key(x: HeapNode[T, Key], k: Key)
Decreases the key value associated with the given node.
- Parameters:
x – The node to modify.
k – The new key value.
- Raises:
ValueError – If
x.key
is less thank
.
- property min_node: HeapNode[T, Key]
Returns the heap node associated with the smallest item in the heap, without removing it.
- peek() T
Returns the smallest element of the heap without removing it.
- Returns:
The smallest element of the heap.
- Return type:
T
- pop() T
Returns and removes the smallest item from this heap.
- push(item: T) HeapNode[T, Key]
Adds a new item to this heap.
- Returns:
The heap node created to store the new item.
- Return type:
HeapNode[T, Key]
- remove(node: HeapNode[T, Key])
Removes the given node from this heap.
- Parameters:
node – The node to be removed.
Warning
This function assumes that the provided node is actually a member of this heap. It also assumes (but does not check) that
node.deleted
isFalse
. If either of these assumptions is incorrect, it will lead to undefined behavior and corruption of the heap.
HeapNode
- class graphtage.fibonacci.HeapNode(item: ~graphtage.fibonacci.T, key: ~graphtage.fibonacci.Key = <object object>)
Bases:
Generic
[T
,Key
]A node in a
FibonacciHeap
.- __init__(item: ~graphtage.fibonacci.T, key: ~graphtage.fibonacci.Key = <object object>)
Initializes a Fibonacci heap node.
- Parameters:
item – The heap item associated with the node.
key – An optional key to use for the item in sorting. If omitted, the item itself will be used.
- __iter__() Iterator[HeapNode[T, Key]]
Iterates over all of this node’s descendants, including itself.
- add_child(node)
Adds a child to this heap node, incrementing its degree.
- property children: Iterator[HeapNode[T, Key]]
Iterates over this node’s children.
Equivalent to:
if self.child is not None: yield self.child yield from self.child.siblings
- deleted: bool
Whether the node has been deleted.
This is to prevent nodes from being manipulated after they have been removed from a heap.
Warning
Do not set
HeapNode.deleted
toTrue
unless the node has already been removed from the heap.
- item: T
The item associated with this heap node.
- key: Key
The key to be used when sorting this heap node.
- remove_child(node)
Removes a child from this heap node, decrementing its degree.
MaxFibonacciHeap
- class graphtage.fibonacci.MaxFibonacciHeap(key: Callable[[T], Key] | None = None)
Bases:
Generic
[T
,Key
],FibonacciHeap
[T
,ReversedComparator
[Key
]]A Fibonacci Heap that yields items in decreasing order, using a
ReversedComparator
.- __init__(key: Callable[[T], Key] | None = None)
Initializes a Fibonacci heap.
- Parameters:
key –
An optional function that accepts an item and returns the key to be used for comparing that item. If omitted, it is equivalent to:
lambda item: item
- clear()
Removes all items from this heap.
- decrease_key(x: HeapNode[T, Key], k: Key)
Decreases the key value associated with the given node.
- Parameters:
x – The node to modify.
k – The new key value.
- Raises:
ValueError – If
x.key
is less thank
.
- property min_node: HeapNode[T, Key]
Returns the heap node associated with the smallest item in the heap, without removing it.
- peek() T
Returns the smallest element of the heap without removing it.
- Returns:
The smallest element of the heap.
- Return type:
T
- pop() T
Returns and removes the smallest item from this heap.
- push(item: T) HeapNode[T, Key]
Adds a new item to this heap.
- Returns:
The heap node created to store the new item.
- Return type:
HeapNode[T, Key]
- remove(node: HeapNode[T, Key])
Removes the given node from this heap.
- Parameters:
node – The node to be removed.
Warning
This function assumes that the provided node is actually a member of this heap. It also assumes (but does not check) that
node.deleted
isFalse
. If either of these assumptions is incorrect, it will lead to undefined behavior and corruption of the heap.