Algorithm
Fibonacci Heap is a data structure that supports efficient decrease key and delete node operations, making it particularly useful for certain applications such as Dijkstra's algorithm and Prim's algorithm. Here's an overview of how these operations work in a Fibonacci Heap:
-
Decrease Key Operation:
- This operation is used to decrease the key of a node in the Fibonacci Heap.
- The basic idea is to decrease the key of a node and then perform some cascading cuts and potential consolidations to maintain the properties of the Fibonacci Heap.
- The steps are as follows:
- Update the key of the target node to the new, smaller key.
- If the heap property is violated (i.e., the key of the node is now smaller than the key of its parent), cut the node from its parent.
- Move the cut node to the root list.
- Perform cascading cuts: If the cut node was marked before, unmark it. If its parent was unmarked, mark it. Continue this process until reaching an unmarked root or the root list is exhausted.
-
Delete Node Operation:
- This operation is used to delete a node from the Fibonacci Heap.
- To delete a node, the typical approach is to first decrease its key to negative infinity (or some very large negative value) and then perform the extract minimum operation.
- After decreasing the key to negative infinity, the node would become the minimum and can be easily extracted.
- The decrease key operation, as described above, is used for the first step.
- After extracting the minimum (which effectively deletes the node), the rest of the heap operations, such as consolidating the trees, may be required to maintain the Fibonacci Heap properties.
Here is a brief summary of the Fibonacci Heap properties for reference:
- Each node has an associated degree (the number of children it has).
- Nodes are linked in a circular doubly linked list, forming the root list.
- The minimum node is easily accessible.
- Trees are unordered, and nodes may have arbitrary degrees.
Code Examples
#1 Decrease Key and Delete Node Operations on a Fibonacci Heap implement in Python
Code -
Python Programming
class FibonacciHeapNode:
def __init__(self, key):
self.key = key
self.degree = 0
self.marked = False
self.parent = None
self.child = None
self.next = self
self.prev = self
class FibonacciHeap:
def __init__(self):
self.min_node = None
self.nodes = {}
def insert(self, key):
new_node = FibonacciHeapNode(key)
self.nodes[key] = new_node
if self.min_node is None:
self.min_node = new_node
else:
self._link(self.min_node, new_node)
if key < self.min_node.key:
self.min_node = new_node
def _link(self, root, new_child):
new_child.next = root.next
new_child.prev = root
root.next.prev = new_child
root.next = new_child
def _remove_from_list(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _link_child_to_parent(self, parent, child):
child.prev = child.next = child
parent.degree += 1
child.parent = parent
if parent.child is None:
parent.child = child
else:
self._link(parent.child, child)
def _consolidate(self):
max_degree = int(self.min_node.degree**0.5) + 1
root_list = [None] * max_degree
current = self.min_node
nodes_to_visit = [current]
while nodes_to_visit:
current = nodes_to_visit.pop(0)
degree = current.degree
while root_list[degree] is not None:
other = root_list[degree]
if other.key < current.key:
current, other = other, current
self._link(root_list[degree], current)
root_list[degree] = None
degree += 1
root_list[degree] = current
if current.next != current:
nodes_to_visit.append(current.next)
self.min_node = None
for root in root_list:
if root is not None:
if self.min_node is None or root.key < self.min_node.key:
self.min_node = root
def decrease_key(self, old_key, new_key):
if new_key > old_key:
raise ValueError("New key must be less than the old key")
node = self.nodes[old_key]
node.key = new_key
parent = node.parent
if parent is not None 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, child, parent):
self._remove_from_list(child)
parent.degree -= 1
if parent.child == child:
parent.child = child.next
child.parent = None
child.marked = False
self._link(self.min_node, child)
def _cascading_cut(self, node):
parent = node.parent
if parent is not None:
if not node.marked:
node.marked = True
else:
self._cut(node, parent)
self._cascading_cut(parent)
def delete(self, key):
if key not in self.nodes:
return
node = self.nodes[key]
self.decrease_key(key, float('-inf'))
self.extract_min()
del self.nodes[key]
def extract_min(self):
min_node = self.min_node
if min_node is not None:
if min_node.child is not None:
child = min_node.child
while True:
next_child = child.next
child.prev = min_node.prev
child.next = min_node.next
min_node.prev.next = child
min_node.next.prev = child
child.parent = None
if next_child == min_node.child:
break
child = next_child
self._remove_from_list(min_node)
if min_node.next == min_node:
self.min_node = None
else:
self.min_node = min_node.next
self._consolidate()
return min_node.key if min_node else None
# Example usage:
fib_heap = FibonacciHeap()
fib_heap.insert(3)
fib_heap.insert(2)
fib_heap.insert(1)
print("Extracted Min:", fib_heap.extract_min()) # Output: 1
fib_heap.decrease_key(3, 0)
print("Extracted Min:", fib_heap.extract_min()) # Output: 0
fib_heap.delete(2)
print("Extracted Min:", fib_heap.extract_min()) # Output: None (empty heap)
#2 Decrease Key and Delete Node Operations on a Fibonacci Heap implement in Java
Code -
Java Programming
import java.util.*;
class FibonacciHeapNode {
int key;
int degree;
boolean marked;
FibonacciHeapNode parent;
FibonacciHeapNode child;
FibonacciHeapNode prev;
FibonacciHeapNode next;
public FibonacciHeapNode(int key) {
this.key = key;
this.degree = 0;
this.marked = false;
this.parent = null;
this.child = null;
this.prev = this;
this.next = this;
}
}
public class FibonacciHeap {
private FibonacciHeapNode minNode;
private int size;
public FibonacciHeap() {
this.minNode = null;
this.size = 0;
}
public boolean isEmpty() {
return minNode == null;
}
public void insert(int key) {
FibonacciHeapNode newNode = new FibonacciHeapNode(key);
if (minNode == null) {
minNode = newNode;
} else {
mergeLists(minNode, newNode);
if (newNode.key < minNode.key) {
minNode = newNode;
}
}
size++;
}
public int findMin() {
if (isEmpty()) {
throw new NoSuchElementException("Fibonacci Heap is empty");
}
return minNode.key;
}
public int extractMin() {
if (isEmpty()) {
throw new NoSuchElementException("Fibonacci Heap is empty");
}
FibonacciHeapNode min = minNode;
if (min.child != null) {
FibonacciHeapNode child = min.child;
do {
FibonacciHeapNode nextChild = child.next;
minNode.prev.next = child;
child.prev = minNode.prev;
child.next = minNode;
minNode.prev = child;
child.parent = null;
child = nextChild;
} while (child != min.child);
}
min.prev.next = min.next;
min.next.prev = min.prev;
if (min == min.next) {
minNode = null;
} else {
minNode = min.next;
consolidate();
}
size--;
return min.key;
}
private void consolidate() {
List < FibonacciHeapNode> degreeTable = new ArrayList<>();
int maxDegree = (int) Math.ceil(Math.log(size) / Math.log(2));
for (int i = 0; i < = maxDegree; i++) {
degreeTable.add(null);
}
List < FibonacciHeapNode> roots = new ArrayList<>();
FibonacciHeapNode current = minNode;
do {
roots.add(current);
current = current.next;
} while (current != minNode);
for (FibonacciHeapNode root : roots) {
int degree = root.degree;
while (degreeTable.get(degree) != null) {
FibonacciHeapNode other = degreeTable.get(degree);
if (root.key > other.key) {
FibonacciHeapNode temp = root;
root = other;
other = temp;
}
linkNodes(other, root);
degreeTable.set(degree, null);
degree++;
}
degreeTable.set(degree, root);
}
minNode = null;
for (FibonacciHeapNode node : degreeTable) {
if (node != null) {
if (minNode == null) {
minNode = node;
} else {
mergeLists(minNode, node);
if (node.key < minNode.key) {
minNode = node;
}
}
}
}
}
private void linkNodes(FibonacciHeapNode child, FibonacciHeapNode parent) {
child.prev.next = child.next;
child.next.prev = child.prev;
child.prev = child;
child.next = child;
parent.degree++;
if (parent.child == null) {
parent.child = child;
} else {
mergeLists(parent.child, child);
}
child.parent = parent;
child.marked = false;
}
public void decreaseKey(FibonacciHeapNode node, int newKey) {
if (newKey > node.key) {
throw new IllegalArgumentException("New key is greater than the current key");
}
node.key = newKey;
FibonacciHeapNode parent = node.parent;
if (parent != null && node.key < parent.key) {
cut(node, parent);
cascadingCut(parent);
}
if (node.key < minNode.key) {
minNode = node;
}
}
private void cut(FibonacciHeapNode child, FibonacciHeapNode parent) {
child.prev.next = child.next;
child.next.prev = child.prev;
parent.degree--;
if (parent.child == child) {
parent.child = child.next;
}
if (parent.degree == 0) {
parent.child = null;
}
mergeLists(minNode, child);
child.parent = null;
child.marked = false;
}
private void cascadingCut(FibonacciHeapNode node) {
FibonacciHeapNode parent = node.parent;
if (parent != null) {
if (!node.marked) {
node.marked = true;
} else {
cut(node, parent);
cascadingCut(parent);
}
}
}
public void delete(FibonacciHeapNode node) {
decreaseKey(node, Integer.MIN_VALUE);
extractMin();
}
private void mergeLists(FibonacciHeapNode list1, FibonacciHeapNode list2) {
FibonacciHeapNode temp1 = list1.next;
list1.next = list2.next;
list2.next.prev = list1;
list2.next = temp1;
temp1.prev = list2;
}
public static void main(String[] args) {
FibonacciHeap fibonacciHeap = new FibonacciHeap();
// Insert elements
fibonacciHeap.insert(5);
fibonacciHeap.insert(2);
fibonacciHeap.insert(8);
fibonacciHeap.insert(1);
// Print the minimum element
System.out.println("Min element: " + fibonacciHeap.findMin());
// Decrease the key of an element
FibonacciHeapNode nodeToDecrease = fibonacciHeap.minNode.child;
fibonacciHeap.decreaseKey(nodeToDecrease, 0);
// Print the new minimum element
System.out.println("Min element after decreaseKey: " + fibonacciHeap.findMin());
// Delete a node
FibonacciHeapNode nodeToDelete = fibonacciHeap.minNode.child;
fibonacciHeap.delete(nodeToDelete);
// Print the new minimum element after deletion
System.out.println("Min element after delete: " + fibonacciHeap.findMin());
}
}
#3 Decrease Key and Delete Node Operations on a Fibonacci Heap implement in C
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
// Node structure for Fibonacci Heap
typedef struct Node {
int key;
int degree;
int marked;
struct Node* parent;
struct Node* child;
struct Node* left;
struct Node* right;
} Node;
// Fibonacci Heap structure
typedef struct FibonacciHeap {
Node* min;
int numNodes;
} FibonacciHeap;
// Function to create a new Fibonacci Heap
FibonacciHeap* createFibonacciHeap() {
FibonacciHeap* heap = (FibonacciHeap*)malloc(sizeof(FibonacciHeap));
heap->min = NULL;
heap->numNodes = 0;
return heap;
}
// Function to create a new node
Node* createNode(int key) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->key = key;
newNode->degree = 0;
newNode->marked = 0;
newNode->parent = NULL;
newNode->child = NULL;
newNode->left = newNode;
newNode->right = newNode;
return newNode;
}
// Function to link two trees of the same degree
void link(Node* y, Node* x) {
y->left->right = y->right;
y->right->left = y->left;
y->parent = x;
if (x->child == NULL) {
x->child = y;
y->left = y;
y->right = y;
} else {
y->left = x->child;
y->right = x->child->right;
x->child->right->left = y;
x->child->right = y;
}
x->degree++;
}
// Function to consolidate the heap
void consolidate(FibonacciHeap* heap) {
int maxDegree = (int)(log(heap->numNodes) / log(2));
Node** array = (Node**)malloc(sizeof(Node*) * (maxDegree + 1));
for (int i = 0; i < = maxDegree; i++) {
array[i] = NULL;
}
Node* current = heap->min;
int numRoots = 0;
if (current != NULL) {
numRoots++;
current = current->right;
while (current != heap->min) {
numRoots++;
current = current->right;
}
}
while (numRoots > 0) {
int degree = current->degree;
Node* next = current->right;
while (array[degree] != NULL) {
Node* other = array[degree];
if (current->key > other->key) {
Node* temp = current;
current = other;
other = temp;
}
link(other, current);
array[degree] = NULL;
degree++;
}
array[degree] = current;
current = next;
numRoots--;
}
heap->min = NULL;
for (int i = 0; i < = maxDegree; i++) {
if (array[i] != NULL) {
if (heap->min == NULL) {
heap->min = array[i];
} else {
array[i]->left->right = array[i]->right;
array[i]->right->left = array[i]->left;
array[i]->left = heap->min;
array[i]->right = heap->min->right;
heap->min->right->left = array[i];
heap->min->right = array[i];
if (array[i]->key < heap->min->key) {
heap->min = array[i];
}
}
}
}
free(array);
}
// Function to perform the Decrease Key operation
void decreaseKey(FibonacciHeap* heap, Node* node, int newKey) {
if (newKey > node->key) {
printf("New key is greater than the current key.\n");
return;
}
node->key = newKey;
Node* parent = node->parent;
if (parent != NULL && node->key < parent->key) {
cut(heap, node, parent);
cascadingCut(heap, parent);
}
if (node->key < heap->min->key) {
heap->min = node;
}
}
// Function to perform the Cut operation
void cut(FibonacciHeap* heap, Node* child, Node* parent) {
// Remove child from the child list of parent
if (child->right == child) {
parent->child = NULL;
} else {
child->right->left = child->left;
child->left->right = child->right;
if (parent->child == child) {
parent->child = child->right;
}
}
parent->degree--;
// Add child to the root list of the heap
child->left = heap->min;
child->right = heap->min->right;
heap->min->right->left = child;
heap->min->right = child;
child->parent = NULL;
child->marked = 0;
}
// Function to perform the Cascading Cut operation
void cascadingCut(FibonacciHeap* heap, Node* node) {
Node* parent = node->parent;
if (parent != NULL) {
if (!node->marked) {
node->marked = 1;
} else {
cut(heap, node, parent);
cascadingCut(heap, parent);
}
}
}
// Function to delete a node from the heap
void deleteNode(FibonacciHeap* heap, Node* node) {
decreaseKey(heap, node, INT_MIN);
extractMin(heap);
}
// Function to extract the minimum node from the heap
Node* extractMin(FibonacciHeap* heap) {
Node* minNode = heap->min;
if (minNode != NULL) {
Node* child = minNode->child;
while (child != NULL) {
Node* next = child->right;
child->left = heap->min;
child->right = heap->min->right;
heap->min->right->left = child;
heap->min->right = child;
child->parent = NULL;
child = next;
}
minNode->left->right = minNode->right;
minNode->right->left = minNode->left;
if (minNode == minNode->right) {
heap->min = NULL;
} else {
heap->min = minNode->right;
consolidate(heap);
}
heap->numNodes--;
}
return minNode;
}
// Function to display the Fibonacci Heap
void displayHeap(Node* node, int indent) {
if (node != NULL) {
printf("%*s
#4 Decrease Key and Delete Node Operations on a Fibonacci Heap implement in C++
Code -
C++ Programming
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
struct Node {
int key;
int degree;
bool marked;
Node* parent;
Node* child;
Node* next;
Node* prev;
};
class FibonacciHeap {
private:
Node* minNode;
int size;
public:
FibonacciHeap() : minNode(nullptr), size(0) {}
bool isEmpty() const {
return minNode == nullptr;
}
void insert(int key) {
Node* newNode = createNode(key);
if (minNode == nullptr) {
minNode = newNode;
} else {
mergeLists(minNode, newNode);
if (newNode->key < minNode->key) {
minNode = newNode;
}
}
size++;
}
void decreaseKey(Node* node, int newKey) {
if (newKey > node->key) {
cout << "New key is greater than the current key." << endl;
return;
}
node->key = newKey;
Node* parent = node->parent;
if (parent != nullptr && node->key < parent->key) {
cut(node, parent);
cascadingCut(parent);
}
if (node->key < minNode->key) {
minNode = node;
}
}
void deleteNode(Node* node) {
decreaseKey(node, numeric_limits<int>::min());
extractMin();
}
int extractMin() {
Node* extractedMin = minNode;
if (extractedMin != nullptr) {
if (extractedMin->child != nullptr) {
Node* child = extractedMin->child;
do {
Node* nextChild = child->next;
mergeLists(minNode, child);
child->parent = nullptr;
child = nextChild;
} while (child != extractedMin->child);
}
removeNode(extractedMin);
if (extractedMin == extractedMin->next) {
minNode = nullptr;
} else {
minNode = extractedMin->next;
consolidate();
}
size--;
}
return extractedMin != nullptr ? extractedMin->key : numeric_limits < int>::max();
}
private:
Node* createNode(int key) {
Node* newNode = new Node();
newNode->key = key;
newNode->degree = 0;
newNode->marked = false;
newNode->parent = nullptr;
newNode->child = nullptr;
newNode->next = newNode;
newNode->prev = newNode;
return newNode;
}
void mergeLists(Node* list1, Node* list2) {
Node* temp1 = list1->next;
list1->next = list2->next;
list2->next->prev = list1;
list2->next = temp1;
temp1->prev = list2;
}
void removeNode(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void cut(Node* child, Node* parent) {
removeNode(child);
parent->degree--;
if (parent->degree == 0) {
parent->child = nullptr;
} else if (parent->child == child) {
parent->child = child->next;
}
mergeLists(minNode, child);
child->parent = nullptr;
child->marked = false;
}
void cascadingCut(Node* node) {
Node* parent = node->parent;
if (parent != nullptr) {
if (!node->marked) {
node->marked = true;
} else {
cut(node, parent);
cascadingCut(parent);
}
}
}
void consolidate() {
int maxDegree = static_cast < int>(log2(size)) + 1;
vector<Node*> degreeArray(maxDegree, nullptr);
Node* current = minNode;
vector < Node*> nodes;
do {
nodes.push_back(current);
current = current->next;
} while (current != minNode);
for (Node* node : nodes) {
int degree = node->degree;
while (degreeArray[degree] != nullptr) {
Node* other = degreeArray[degree];
if (node->key > other->key) {
swap(node, other);
}
link(other, node);
degreeArray[degree] = nullptr;
degree++;
}
degreeArray[degree] = node;
}
minNode = nullptr;
for (Node* node : degreeArray) {
if (node != nullptr) {
if (minNode == nullptr) {
minNode = node;
} else {
mergeLists(minNode, node);
if (node->key < minNode->key) {
minNode = node;
}
}
}
}
}
void link(Node* child, Node* parent) {
removeNode(child);
child->prev = child->next = child;
child->marked = false;
parent->degree++;
if (parent->child == nullptr) {
parent->child = child;
} else {
mergeLists(parent->child, child);
}
child->parent = parent;
}
};
int main() {
FibonacciHeap fibHeap;
fibHeap.insert(4);
fibHeap.insert(8);
fibHeap.insert(3);
cout << "Min key: " << fibHeap.extractMin() << endl; // Output: 3
Node* node = fibHeap.insert(2);
fibHeap.decreaseKey(node, 1);
cout << "Min key: " << fibHeap.extractMin() << endl; // Output: 1
return 0;
}
Demonstration
Decrease Key and Delete Node Operations on a Fibonacci Heap-DevsEnv