Decrease-Key and Delete Node Operations in a Fibonacci Heap

---

A Fibonacci Heap is a data structure that supports efficient operations for priority queues, such as inserting a node, finding the minimum, decreasing a key, and deleting a node. These operations provide amortized time complexities that are significantly better than many traditional heap structures, making Fibonacci heaps useful in algorithms like Dijkstra’s shortest path algorithm and Prim’s minimum spanning tree algorithm.

---

Understanding Fibonacci Heap Basics

Before diving into the operations, let's refresh some basic concepts about Fibonacci heaps:

• Nodes: Each node in a Fibonacci heap contains a key, a pointer to its parent, a list of its children, and a mark indicating whether it has lost a child since the last time it was made a child of another node.
• Min-Heap Property: A Fibonacci heap maintains a collection of heap-ordered trees, with the minimum key being at the root of one of the trees.
• Lazy Structure: Fibonacci heaps delay some work (like consolidating trees) to achieve amortized time bounds.

Fibonacci heaps support the following operations:

• Insert: Insert a new node into the heap.
• Find Min: Find the minimum node in the heap.
• Extract Min: Remove the minimum node from the heap.
• Decrease Key: Decrease the key of a node.
• Delete Node: Remove a specific node from the heap.

---

Decrease Key Operation

What is the Decrease Key Operation?

The Decrease Key operation reduces the value of a key of a specific node in the heap. In a Fibonacci heap, this operation is critical because it helps maintain the heap structure while ensuring that the heap property is not violated.

The Decrease Key operation works as follows:

1. Decrease the value of the node's key.
2. If the decreased key violates the heap order (i.e., it becomes smaller than its parent), the node is cut from its current tree and added to the root list.
3. If the parent node of the cut node has already lost a child, it is marked (indicating that it has lost another child).
4. The operation propagates these changes up the tree until no further changes are required.

Algorithm Steps

1. Find the Node: First, locate the node whose key needs to be decreased.
2. Decrease the Key: Update the key of the node.
3. Check Heap Property: If the key becomes smaller than its parent’s key, cut the node and add it to the root list.
4. Cascade Cut: If the parent node is marked, perform a cascading cut recursively.

Code Example of Decrease Key Operation

class FibonacciHeapNode:
    def __init__(self, key):
        self.key = key
        self.degree = 0
        self.parent = None
        self.child = None
        self.mark = False
        self.next = None
        self.prev = None

class FibonacciHeap:
    def __init__(self):
        self.min_node = None
        self.num_nodes = 0

    def decrease_key(self, node, new_key):
        if new_key > node.key:
            raise ValueError("New key is greater than the current key")
        
        node.key = new_key
        parent = node.parent
        
        if parent and node.key < parent.key:
            self.cut(node, parent)
            self.cascading_cut(parent)
        
        if node.key < self.min_node.key:
            self.min_node = node

    def cut(self, node, parent):
        # Remove node from its parent's child list
        if node == node.next:
            parent.child = None
        else:
            node.prev.next = node.next
            node.next.prev = node.prev

        parent.degree -= 1

        # Add node to the root list
        node.next = self.min_node
        node.prev = self.min_node.prev
        self.min_node.prev.next = node
        self.min_node.prev = node
        node.parent = None
        node.mark = False

    def cascading_cut(self, parent):
        grandparent = parent.parent
        if grandparent:
            if not parent.mark:
                parent.mark = True
            else:
                self.cut(parent, grandparent)
                self.cascading_cut(grandparent)

In this code:

• decrease_key() reduces the key of the node and performs cuts and cascading cuts if necessary.
• cut() handles the removal of the node from its parent and adds it to the root list.
• cascading_cut() propagates the cuts up the tree.

---

Delete Node Operation

What is the Delete Node Operation?

The Delete Node operation removes a node from the Fibonacci heap. This operation is often implemented by first decreasing the key of the node to be deleted to negative infinity (or a very small number) and then performing an Extract Min operation. By making the node the minimum, it will be extracted, thus removing it from the heap.

Steps for Delete Node

1. Decrease the Key: Set the key of the node to negative infinity (or a very small value).
2. Extract Min: Perform the Extract Min operation, which will remove the node from the heap.

This approach leverages the already existing Decrease Key and Extract Min operations for efficiency.

Code Example of Delete Node Operation

def delete_node(self, node):
    # Decrease the key of the node to negative infinity
    self.decrease_key(node, float('-inf'))
    # Extract the minimum, which will remove the node
    self.extract_min()

def extract_min(self):
    min_node = self.min_node
    if min_node:
        # Remove the minimum node from the root list
        if min_node.next == min_node:
            self.min_node = None
        else:
            min_node.prev.next = min_node.next
            min_node.next.prev = min_node.prev
            self.min_node = min_node.next
        
        # Move the children of min_node to the root list
        children = []
        child = min_node.child
        while child:
            children.append(child)
            child = child.next
        
        for child in children:
            self.add_to_root_list(child)
        
        self.num_nodes -= 1
    return min_node

In this code:

• delete_node() decreases the key of the node to negative infinity and then extracts the minimum.
• extract_min() removes the node from the heap and moves any children of the extracted node to the root list.

---

Performance and Time Complexity

Both Decrease Key and Delete Node operations in Fibonacci heaps have efficient amortized time complexities:

• Decrease Key: The amortized time complexity is O(1).
• Delete Node: The amortized time complexity is O(log n), since it involves decreasing the key to negative infinity (O(1)) and performing an extract min operation (O(log n)).

These operations make Fibonacci heaps especially efficient for algorithms that require frequent priority updates, such as Dijkstra's shortest path algorithm.

---

---