# 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 than `k`.

key: Callable[[T], Key]

The function to extract comparison keys from items.

property min_node: HeapNode[T, Key]

Returns the heap node associated with the smallest item in the heap, without removing it.

nodes() Iterator[HeapNode[T, Key]]

Iterates over all of the heap nodes in this heap.

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` is `False`. 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.

Adds a child to this heap node, incrementing its degree.

child: HeapNode[T, Key] | None

The node’s child.

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
```
degree: int

The degree of this node (i.e., the number of its children).

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` to `True` 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.

left: HeapNode[T, Key]

The left sibling of this node, or `self` if it has no left sibling.

mark: bool

The node’s marked state.

parent: HeapNode[T, Key] | None

The node’s parent.

remove_child(node)

Removes a child from this heap node, decrementing its degree.

right: HeapNode[T, Key]

The right sibling of this node, or `self` if it has no left sibling.

property siblings: Iterator[HeapNode[T, 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: 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 than `k`.

key: Callable[[T], Key]

The function to extract comparison keys from items.

property min_node: HeapNode[T, Key]

Returns the heap node associated with the smallest item in the heap, without removing it.

nodes() Iterator[HeapNode[T, Key]]

Iterates over all of the heap nodes in this heap.

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` is `False`. If either of these assumptions is incorrect, it will lead to undefined behavior and corruption of the heap.

### ReversedComparator

class graphtage.fibonacci.ReversedComparator(key: Key)

Bases: `Generic`[`Key`]

A wrapper that reverses the semantics of its comparison operators.

__init__(key: Key)