fibonacci_heap.py

from typing import Any, Optional
import math

class FibonacciHeapNode:
    """
    Represents a node in the Fibonacci heap.

    Attributes:
        key: The priority of the node.
        value: Optional data associated with the key.
        parent: Pointer to the parent node.
        child: Pointer to any one of its child nodes.
        left: Pointer to the left sibling in the circular doubly linked list.
        right: Pointer to the right sibling in the circular doubly linked list.
        degree: The number of children the node has.
        mark: A boolean flag used for the cascading cut operation.
    """
    def __init__(self, key, value: Optional[Any] = None):
        self.key = key
        self.value = value
        self.parent: Optional['FibonacciHeapNode'] = None
        self.child: Optional['FibonacciHeapNode'] = None
        self.left: 'FibonacciHeapNode' = self
        self.right: 'FibonacciHeapNode' = self
        self.degree: int = 0
        self.mark: bool = False

class FibonacciHeap:
    """
    Abstract Data Type for a Fibonacci Heap.

    Attributes:
        min_node: Pointer to the node with the minimum key in the root list.
        n: The total number of nodes in the heap.
    """
    def __init__(self):
        """
        Initializes an empty Fibonacci heap.
        """
        self.min_node: Optional[FibonacciHeapNode] = None
        self.n: int = 0

    def insert(self, key, value: Optional[Any] = None) -> FibonacciHeapNode:
        """
        Inserts a new node with the given key (and optional value) into the heap.

        Args:
            key: The priority of the new node.
            value: Optional data to associate with the key.

        Returns:
            The newly created FibonacciHeapNode.
        """
        node_val = FibonacciHeapNode(key, value)

        if self.n == 0 or self.min_node is None:
            self.min_node = node_val
            self.n = 1
            return node_val
        # insert the new node next to min_node
        # insert the new node into the circular root list
        node_val.left = self.min_node
        node_val.right = self.min_node.right
        self.min_node.right.left = node_val
        self.min_node.right = node_val

        self.n += 1
        if self.min_node.key > key:
            self.min_node = node_val
        return node_val

    def find_min(self) -> Optional[FibonacciHeapNode]:
        """
        Returns the node with the minimum key in the heap.

        Returns:
            The FibonacciHeapNode with the minimum key, or None if the heap is empty.
        """
        return self.min_node # value is none anyway if this does not yet exist.

    def extract_min(self) -> Optional[FibonacciHeapNode]:
        """
        Removes and returns the node with the minimum key from the heap.
        This operation also performs the consolidate operation.

        Returns:
            The FibonacciHeapNode with the minimum key that was removed,
            or None if the heap is empty.
        """
        # Handle empty heap
        if self.min_node is None:
            return None

        # Save min node to return later
        ret_node = self.min_node

        # Handle single node case
        if self.n == 1:
            self.min_node = None
            self.n = 0
            return ret_node

        # swap all children to the root
        if ret_node.child is not None:
            # Iterate through all children
            child = ret_node.child
            while True:
                next_child = child.right
                child.left.right = child.right
                child.right.left = child.left
                # Add child to root list
                child.left = self.min_node
                child.right = self.min_node.right
                self.min_node.right.left = child
                self.min_node.right = child
                child.parent = None
                child.mark = False
                child = next_child
                # Exit if we've processed all children
                if child == ret_node.child:
                    break

            # Clear child pointer
            ret_node.child = None

        # Remove min node from root list
        ret_node.left.right = ret_node.right
        ret_node.right.left = ret_node.left

        # If ret_node was the only root, we're done
        if ret_node == ret_node.right:
            self.min_node = None
            self.n -= 1
            return ret_node

        # Update min_node to a valid node in the root list, so we have a reference to something other than None
        self.min_node = ret_node.right

        # perform fibonacci heap consolidation
        self._consolidate()

        # Decrement node count
        self.n -= 1

        return ret_node

    def _consolidate(self):
        """Helper method to consolidate the root list, used only in extract_min."""
        max_degree = int(math.log2(self.n)) * 2 + 1

        # create degree array with size of log(n)
        degree_array: Optional['FibonacciHeapNode'] = [None] * (max_degree + 1)

        # Collect all roots into an array
        roots = []
        current = self.min_node
        start_node = current
        while True:
            roots.append(current)
            current = current.right
            if current == start_node:
                break

        # Process each root and consolidate
        for root in roots:
            node = root
            degree = node.degree

            # do not allow roots with the same degrees, they must be merged.
            while degree_array[degree] is not None:
                other_node = degree_array[degree]

                # Skip if node and other_node are the same node
                if node == other_node:
                    break

                # ensure that the node that is the root, will be the one with the smaller value.
                if node.key > other_node.key:
                    node, other_node = other_node, node

                # Link other_node as a child of node
                self._link(other_node, node)

                # Clear the slot and move to next degree
                degree_array[degree] = None
                degree += 1

            degree_array[degree] = node

        # reset min_node to None and rebuild root list
        self.min_node = None

        for i in range(len(degree_array)):
            if degree_array[i] is not None:
                # If this is the first valid root, make a singleton circular list
                if self.min_node is None:
                    degree_array[i].left = degree_array[i]
                    degree_array[i].right = degree_array[i]
                    self.min_node = degree_array[i]
                else:
                    # Otherwise, add to the root list
                    degree_array[i].left = self.min_node
                    degree_array[i].right = self.min_node.right
                    self.min_node.right.left = degree_array[i]
                    self.min_node.right = degree_array[i]

                    # Update min_node if needed
                    if degree_array[i].key < self.min_node.key:
                        self.min_node = degree_array[i]

    def _link(self, child_node, parent_node):
        """
        Make child_node a child of parent_node.
        Args:
            child_node: The node to become a child
            parent_node: The node to become the parent
        """
        child_node.left.right = child_node.right
        child_node.right.left = child_node.left

        if parent_node.child is None:
            parent_node.child = child_node
            child_node.left = child_node
            child_node.right = child_node
        else:
            child_node.left = parent_node.child
            child_node.right = parent_node.child.right
            parent_node.child.right.left = child_node
            parent_node.child.right = child_node

        # Set parent pointer and clear mark
        child_node.parent = parent_node
        child_node.mark = False

        # Increment parent_node's degree
        parent_node.degree += 1


    def decrease_key(self, node: FibonacciHeapNode, new_key) -> None:
        """
        Decreases the key of a given node to a new value.
        This operation may involve cutting the node from its parent and cascading cuts.

        Args:
            node: The FibonacciHeapNode whose key needs to be decreased.
            new_key: The new key value (must be less than or equal to the current key).

        Raises:
            ValueError: If the new key is greater than the current key.
        """
        if new_key > node.key:
            raise ValueError("New key is greater than current key")

        node.key = new_key
        parent = node.parent

        if parent and node.key < parent.key:
            # CUT node from its parent's child list
            if node.right == node:
                parent.child = None
            else:
                node.right.left = node.left
                node.left.right = node.right
                if parent.child == node:
                    parent.child = node.right
            parent.degree -= 1

            # ADD node to root list
            node.left = self.min_node
            node.right = self.min_node.right
            self.min_node.right.left = node
            self.min_node.right = node

            node.parent = None
            node.mark = False

            # CASCADING CUT
            ancestor = parent
            while ancestor.parent:
                if not ancestor.mark:
                    ancestor.mark = True
                    break
                parent = ancestor.parent
                # CUT ancestor
                if ancestor.right == ancestor:
                    parent.child = None
                else:
                    ancestor.right.left = ancestor.left
                    ancestor.left.right = ancestor.right
                    if parent.child == ancestor:
                        parent.child = ancestor.right
                parent.degree -= 1

                # ADD ancestor to root list
                ancestor.left = self.min_node
                ancestor.right = self.min_node.right
                self.min_node.right.left = ancestor
                self.min_node.right = ancestor

                ancestor.parent = None
                ancestor.mark = False
                ancestor = parent

        # Handle case when node is already root (e.g., in delete())
        if node.parent is None:

        # Detach from any previous position (only if node isn't alone)
            if node.left != node or node.right != node:
                node.left.right = node.right
                node.right.left = node.left

            # Add node to root list (if it's not already there)
            node.left = self.min_node
            node.right = self.min_node.right
            self.min_node.right.left = node
            self.min_node.right = node

            # Ensure min_node is updated
            if self.min_node and node.key < self.min_node.key:
                self.min_node = node

    def delete(self, node: FibonacciHeapNode) -> None:
        """
        Deletes a node from the heap.
        This operation can be implemented by decreasing the key to negative infinity
        and then extracting the minimum.

        Args:
            node: The FibonacciHeapNode to be deleted.
        """
        self.decrease_key(node, float("-inf"))
        self.extract_min()

    def is_empty(self) -> bool:
        """
        Checks if the heap is empty.

        Returns:
            True if the heap is empty, False otherwise.
        """
        return self.min_node is None

    # Optional: Method to get the current size of the heap
    def size(self) -> int:
        """
        Returns the number of nodes in the heap.

        Returns:
            The total number of nodes.
        """
        return self.n

    # Optional: Helper method to display the heap structure (for debugging/understanding)
    def display_heap(self) -> None:
        """
        (Optional) Displays the structure of the Fibonacci heap.
        This is useful for visualization and understanding during implementation.
        """
        print("Root list:")
        if self.min_node is None:
            print("Heap is empty.")
            return

        current = self.min_node
        while True:
            print(f"Key: {current.key}, Degree: {current.degree}, Marked: {current.mark}")
            current = current.right
            if current == self.min_node:
                break

# --- Human Created but AI refined test case for fibonacci heap --- #
# While we can create a simple test case, it was important to make sure this works well.
# And is as bulletproof as possible, so we used AI to refine it into a more comprehensive
# test case for fibonacci heap to make sure all edge cases (that we didn't think of) are tested.
if __name__ == '__main__':
    # Test the Fibonacci Heap implementation
    heap = FibonacciHeap()

    print("Testing basic operations...")
    # Test empty heap
    assert heap.is_empty() == True
    assert heap.extract_min() is None

    # Insert elements and verify min
    nodes = []
    print("Inserting elements: ", end="")
    for val in [10, 5, 8, 3, 6, 1, 7]:
        print(f"{val} ", end="")
        nodes.append(heap.insert(val))
    print("\nMin after insertions:", heap.find_min().key)
    assert heap.find_min().key == 1

    # Extract min elements and verify order
    print("\nExtracting elements: ", end="")
    expected = [1, 3, 5, 6, 7, 8, 10]
    for expected_val in expected:
        min_node = heap.extract_min()
        print(f"{min_node.key} ", end="")
        assert min_node.key == expected_val
    print("\nAll elements extracted in correct order")
    assert heap.is_empty()

    # Test decrease key
    print("\nTesting decrease key...")
    heap = FibonacciHeap()
    nodes = []
    for val in [10, 20, 30, 40, 50]:
        nodes.append(heap.insert(val))

    print(f"Min before decrease: {heap.find_min().key}")
    heap.decrease_key(nodes[3], 5)  # 40 -> 5
    print(f"Decreased 40 to 5, min is now: {heap.find_min().key}")
    assert heap.find_min().key == 5

    # Test delete
    print("\nTesting delete...")
    heap.delete(nodes[1])  # Delete 20
    print("Deleted node with key 20")

    # Extract all and verify
    print("Remaining elements: ", end="")
    expected = [5, 10, 30, 50]
    extracted = []
    while not heap.is_empty():
        node = heap.extract_min()
        if node.key != float('-inf'):
            extracted.append(node.key)
            print(f"{node.key} ", end="")

    # Verify everything worked correctly
    print("\n\nAll tests completed!")
    if len(expected) == len(extracted) and all(a == b for a, b in zip(sorted(expected), sorted(extracted))):
        print("✅ Fibonacci heap implementation is correct!")
    else:
        print("❌ Test failed! Expected:", expected, "Got:", extracted)