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: Optional[Callable[[graphtage.fibonacci.T], graphtage.fibonacci.Key]] = None)¶
Bases:
Generic
[graphtage.fibonacci.T
,graphtage.fibonacci.Key
]A Fibonacci Heap.
- __init__(key: Optional[Callable[[graphtage.fibonacci.T], graphtage.fibonacci.Key]] = 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: graphtage.fibonacci.HeapNode[graphtage.fibonacci.T, graphtage.fibonacci.Key], k: graphtage.fibonacci.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
.
- key: Callable[[graphtage.fibonacci.T], graphtage.fibonacci.Key]¶
The function to extract comparison keys from items.
- property min_node: graphtage.fibonacci.HeapNode[graphtage.fibonacci.T, graphtage.fibonacci.Key]¶
Returns the heap node associated with the smallest item in the heap, without removing it.
- nodes() Iterator[graphtage.fibonacci.HeapNode[graphtage.fibonacci.T, graphtage.fibonacci.Key]] ¶
Iterates over all of the heap nodes in this heap.
- peek() graphtage.fibonacci.T ¶
Returns the smallest element of the heap without removing it.
- Returns
The smallest element of the heap.
- Return type
T
- pop() graphtage.fibonacci.T ¶
Returns and removes the smallest item from this heap.
- push(item: graphtage.fibonacci.T) graphtage.fibonacci.HeapNode[graphtage.fibonacci.T, graphtage.fibonacci.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: graphtage.fibonacci.HeapNode[graphtage.fibonacci.T, graphtage.fibonacci.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
[graphtage.fibonacci.T
,graphtage.fibonacci.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[graphtage.fibonacci.HeapNode[graphtage.fibonacci.T, graphtage.fibonacci.Key]] ¶
Iterates over all of this node’s descendants, including itself.
- add_child(node)¶
Adds a child to this heap node, incrementing its degree.
- child: Optional[graphtage.fibonacci.HeapNode[graphtage.fibonacci.T, graphtage.fibonacci.Key]]¶
The node’s child.
- property children: Iterator[graphtage.fibonacci.HeapNode[graphtage.fibonacci.T, graphtage.fibonacci.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: graphtage.fibonacci.T¶
The item associated with this heap node.
- key: graphtage.fibonacci.Key¶
The key to be used when sorting this heap node.
- left: graphtage.fibonacci.HeapNode[graphtage.fibonacci.T, graphtage.fibonacci.Key]¶
The left sibling of this node, or
self
if it has no left sibling.
- parent: Optional[graphtage.fibonacci.HeapNode[graphtage.fibonacci.T, graphtage.fibonacci.Key]]¶
The node’s parent.
- remove_child(node)¶
Removes a child from this heap node, decrementing its degree.
- right: graphtage.fibonacci.HeapNode[graphtage.fibonacci.T, graphtage.fibonacci.Key]¶
The right sibling of this node, or
self
if it has no left sibling.
- property siblings: Iterator[graphtage.fibonacci.HeapNode[graphtage.fibonacci.T, graphtage.fibonacci.Key]]¶
Iterates over this node’s siblings.
Equivalent to:
node = self.right while node != self: yield node node = node.right
MaxFibonacciHeap¶
- class graphtage.fibonacci.MaxFibonacciHeap(key: Optional[Callable[[graphtage.fibonacci.T], graphtage.fibonacci.Key]] = None)¶
Bases:
Generic
[graphtage.fibonacci.T
,graphtage.fibonacci.Key
],graphtage.fibonacci.FibonacciHeap
[graphtage.fibonacci.T
,graphtage.fibonacci.ReversedComparator
[graphtage.fibonacci.Key
]]A Fibonacci Heap that yields items in decreasing order, using a
ReversedComparator
.- __init__(key: Optional[Callable[[graphtage.fibonacci.T], graphtage.fibonacci.Key]] = 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: graphtage.fibonacci.HeapNode[graphtage.fibonacci.T, graphtage.fibonacci.Key], k: graphtage.fibonacci.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
.
- key: Callable[[graphtage.fibonacci.T], graphtage.fibonacci.Key]¶
The function to extract comparison keys from items.
- property min_node: graphtage.fibonacci.HeapNode[graphtage.fibonacci.T, graphtage.fibonacci.Key]¶
Returns the heap node associated with the smallest item in the heap, without removing it.
- nodes() Iterator[graphtage.fibonacci.HeapNode[graphtage.fibonacci.T, graphtage.fibonacci.Key]] ¶
Iterates over all of the heap nodes in this heap.
- peek() graphtage.fibonacci.T ¶
Returns the smallest element of the heap without removing it.
- Returns
The smallest element of the heap.
- Return type
T
- pop() graphtage.fibonacci.T ¶
Returns and removes the smallest item from this heap.
- push(item: graphtage.fibonacci.T) graphtage.fibonacci.HeapNode[graphtage.fibonacci.T, graphtage.fibonacci.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: graphtage.fibonacci.HeapNode[graphtage.fibonacci.T, graphtage.fibonacci.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.