如何实现斐波那契堆（–删除，提取最小值和减小键（Fibonacci Heap））

在上一篇文章中, 我们讨论了斐波那契堆的插入和联合。在本文中, 我们将讨论Fibonacci堆上的Extract_min(), Decrease_key()和Deletion()操作。
先决条件：
斐波那契堆(简介)
斐波那契堆–插入和联合操作
Extract_min()：我们创建一个删除最小节点并将最小指针设置为剩余堆中最小值的函数。遵循以下算法：

删除最小节点。
将head设置为下一个min节点, 并将已删除节点的所有树添加到根列表中。
创建一个已删除节点大小的度指针数组。
将度数指针设置为当前节点。
移至下一个节点。
- 如果度数不同, 则将度数指针设置为下一个节点。
- 如果度数相同, 则通过联合操作加入斐波那契树。
重复步骤4和5, 直到完成堆。

例子：

如何实现斐波那契堆（–删除，提取最小值和减小键（Fibonacci Heap））

文章图片
Decrease_key()：为了减少堆中任何元素的值, 我们遵循以下算法：
将节点" x"的值减小到新选择的值。
情况1)如果未违反min堆属性,

如有必要, 更新最小指针。

情况2)如果违反了最小堆属性, 并且未标记" x"的父项,

切断" x"与其父级之间的链接。
标记" x"的父项。
将以" x"为根的树添加到根列表中, 并在必要时更新min指针。

情况3)如果违反了最小堆属性, 并且标记了" x"的父项,

切断" x"与其父级p [x]之间的链接。
在根目录列表中添加" x", 并在必要时更新min指针。
切断p [x]和p
]之间的链接。
将p [x]添加到根列表中, 必要时更新min指针。
如果未标记p
], 则将其标记。
否则, 剪掉p
]并重复步骤4.2至4.5, 将p
]当作" x"。

例子：

文章图片
Deletion()：要删除斐波那契堆中的任何元素, 请遵循以下算法：

通过Decrease_key()函数将要删除的节点的值" x"减小到最小值。
通过使用min heap属性, 对包含" x"的堆进行堆化, 将" x"带入根列表。
将Extract_min()算法应用于Fibonacci堆。

例子：

文章图片
以下是一个演示斐波那契堆上的Extract min(), Deletion()和Decrease key()操作的程序：

// C++ program to demonstrate Extract min, Deletion() // and Decrease key() operations in a fibonacci heap #include < cmath> #include < cstdlib> #include < iostream> #include < malloc.h> using namespace std; // Creating a structure to represent a node in the heap struct node { node* parent; // Parent pointer node* child; // Child pointer node* left; // Pointer to the node on the left node* right; // Pointer to the node on the right int key; // Value of the node int degree; // Degree of the node char mark; // Black or white mark of the node char c; // Flag for assisting in the Find node function }; // Creating min pointer as "mini" struct node* mini = NULL; // Declare an integer for number of nodes in the heap int no_of_nodes = 0; // Function to insert a node in heap void insertion( int val) { struct node* new_node = ( struct node*) malloc ( sizeof ( struct node)); new_node-> key = val; new_node-> degree = 0; new_node-> mark = 'W' ; new_node-> c = 'N' ; new_node-> parent = NULL; new_node-> child = NULL; new_node-> left = new_node; new_node-> right = new_node; if (mini != NULL) { (mini-> left)-> right = new_node; new_node-> right = mini; new_node-> left = mini-> left; mini-> left = new_node; if (new_node-> key < mini-> key) mini = new_node; } else { mini = new_node; } no_of_nodes++; } // Linking the heap nodes in parent child relationship void Fibonnaci_link( struct node* ptr2, struct node* ptr1) { (ptr2-> left)-> right = ptr2-> right; (ptr2-> right)-> left = ptr2-> left; if (ptr1-> right == ptr1) mini = ptr1; ptr2-> left = ptr2; ptr2-> right = ptr2; ptr2-> parent = ptr1; if (ptr1-> child == NULL) ptr1-> child = ptr2; ptr2-> right = ptr1-> child; ptr2-> left = (ptr1-> child)-> left; ((ptr1-> child)-> left)-> right = ptr2; (ptr1-> child)-> left = ptr2; if (ptr2-> key < (ptr1-> child)-> key) ptr1-> child = ptr2; ptr1-> degree++; } // Consolidating the heap void Consolidate() { int temp1; float temp2 = ( log (no_of_nodes)) / ( log (2)); int temp3 = temp2; struct node* arr[temp3]; for ( int i = 0; i < = temp3; i++) arr[i] = NULL; node* ptr1 = mini; node* ptr2; node* ptr3; node* ptr4 = ptr1; do { ptr4 = ptr4-> right; temp1 = ptr1-> degree; while (arr[temp1] != NULL) { ptr2 = arr[temp1]; if (ptr1-> key > ptr2-> key) { ptr3 = ptr1; ptr1 = ptr2; ptr2 = ptr3; } if (ptr2 == mini) mini = ptr1; Fibonnaci_link(ptr2, ptr1); if (ptr1-> right == ptr1) mini = ptr1; arr[temp1] = NULL; temp1++; } arr[temp1] = ptr1; ptr1 = ptr1-> right; } while (ptr1 != mini); mini = NULL; for ( int j = 0; j < = temp3; j++) { if (arr[j] != NULL) { arr[j]-> left = arr[j]; arr[j]-> right = arr[j]; if (mini != NULL) { (mini-> left)-> right = arr[j]; arr[j]-> right = mini; arr[j]-> left = mini-> left; mini-> left = arr[j]; if (arr[j]-> key < mini-> key) mini = arr[j]; } else { mini = arr[j]; } if (mini == NULL) mini = arr[j]; else if (arr[j]-> key < mini-> key) mini = arr[j]; } } }// Function to extract minimum node in the heap void Extract_min() { if (mini == NULL) cout < < "The heap is empty" < < endl; else { node* temp = mini; node* pntr; pntr = temp; node* x = NULL; if (temp-> child != NULL) {x = temp-> child; do { pntr = x-> right; (mini-> left)-> right = x; x-> right = mini; x-> left = mini-> left; mini-> left = x; if (x-> key < mini-> key) mini = x; x-> parent = NULL; x = pntr; } while (pntr != temp-> child); } (temp-> left)-> right = temp-> right; (temp-> right)-> left = temp-> left; mini = temp-> right; if (temp == temp-> right & & temp-> child == NULL) mini = NULL; else { mini = temp-> right; Consolidate(); } no_of_nodes--; } }// Cutting a node in the heap to be placed in the root list void Cut( struct node* found, struct node* temp) { if (found == found-> right) temp-> child = NULL; (found-> left)-> right = found-> right; (found-> right)-> left = found-> left; if (found == temp-> child) temp-> child = found-> right; temp-> degree = temp-> degree - 1; found-> right = found; found-> left = found; (mini-> left)-> right = found; found-> right = mini; found-> left = mini-> left; mini-> left = found; found-> parent = NULL; found-> mark = 'B' ; }// Recursive cascade cutting function void Cascase_cut( struct node* temp) { node* ptr5 = temp-> parent; if (ptr5 != NULL) { if (temp-> mark == 'W' ) { temp-> mark = 'B' ; } else { Cut(temp, ptr5); Cascase_cut(ptr5); } } }// Function to decrease the value of a node in the heap void Decrease_key( struct node* found, int val) { if (mini == NULL) cout < < "The Heap is Empty" < < endl; if (found == NULL) cout < < "Node not found in the Heap" < < endl; found-> key = val; struct node* temp = found-> parent; if (temp != NULL & & found-> key < temp-> key) { Cut(found, temp); Cascase_cut(temp); } if (found-> key < mini-> key) mini = found; }// Function to find the given node void Find( struct node* mini, int old_val, int val) { struct node* found = NULL; node* temp5 = mini; temp5-> c = 'Y' ; node* found_ptr = NULL; if (temp5-> key == old_val) { found_ptr = temp5; temp5-> c = 'N' ; found = found_ptr; Decrease_key(found, val); } if (found_ptr == NULL) { if (temp5-> child != NULL) Find(temp5-> child, old_val, val); if ((temp5-> right)-> c != 'Y' ) Find(temp5-> right, old_val, val); } temp5-> c = 'N' ; found = found_ptr; }// Deleting a node from the heap void Deletion( int val) { if (mini == NULL) cout < < "The heap is empty" < < endl; else {// Decreasing the value of the node to 0 Find(mini, val, 0); // Calling Extract_min function to // delete minimum value node, which is 0 Extract_min(); cout < < "Key Deleted" < < endl; } }// Function to display the heap void display() { node* ptr = mini; if (ptr == NULL) cout < < "The Heap is Empty" < < endl; else { cout < < "The root nodes of Heap are: " < < endl; do { cout < < ptr-> key; ptr = ptr-> right; if (ptr != mini) { cout < < "--> " ; } } while (ptr != mini & & ptr-> right != NULL); cout < < endl < < "The heap has " < < no_of_nodes < < " nodes" < < endl < < endl; } }// Driver code int main() { // We will create a heap and insert 3 nodes into it cout < < "Creating an initial heap" < < endl; insertion(5); insertion(2); insertion(8); // Now we will display the root list of the heap display(); // Now we will extract the minimum value node from the heap cout < < "Extracting min" < < endl; Extract_min(); display(); // Now we will decrease the value of node '8' to '7' cout < < "Decrease value of 8 to 7" < < endl; Find(mini, 8, 7); display(); // Now we will delete the node '7' cout < < "Delete the node 7" < < endl; Deletion(7); display(); return 0; }

【如何实现斐波那契堆（–删除，提取最小值和减小键（Fibonacci Heap））】输出如下：

Creating an initial heap The root nodes of Heap are: 2--> 5--> 8 The heap has 3 nodesExtracting min The root nodes of Heap are: 5 The heap has 2 nodesDecrease value of 8 to 7 The root nodes of Heap are: 5 The heap has 2 nodesDelete the node 7 Key Deleted The root nodes of Heap are: 5 The heap has 1 nodes