高级数据结构（如何实现斐波那契堆–插入和联合操作（））

【高级数据结构（如何实现斐波那契堆–插入和联合操作（））】先决条件：斐波那契堆(简介)
斐波那契堆是具有最小堆或最大堆属性的树的集合。在斐波那契堆中, 即使所有树都可以是单个节点, 树木也可以具有任何形状(这与二项式堆不同, 后者每棵树都必须是二项式树)。
在本文中, 我们将讨论斐波那契堆上的插入和联合操作。
插入：要将节点插入斐波那契堆H中, 请遵循以下算法：

创建一个新节点"x"。
检查堆H是否为空。
如果H为空, 则：使x为根列表中的唯一节点。并将H(min)指针设置为x。
否则：将x插入根列表并更新H(min)。

例子：

文章图片
联合：两个斐波纳契堆H1和H2的并集可以按以下方式完成：

将Fibonacci堆的H1和H2的根列表联接起来, 并制作单个Fibonacci堆H。
如果H1(min)< H2(min), 则：H(min)= H1(min)。
否则：H(min)= H2(min)。

例子：

文章图片
以下是演示在斐波那契堆中进行构建和插入的程序：

// C++ program to demonstrate building // and inserting in a Fibonacci heap #include < cstdlib> #include < iostream> #include < malloc.h> using namespace std; struct node { node* parent; node* child; node* left; node* right; int key; }; // 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-> 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; } }// Function to display the heap void display( struct node* mini) { 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; } } // Function to find min node in the heap void find_min( struct node* mini) { cout < < "min of heap is: " < < mini-> key < < endl; }// Driver code int main() {no_of_nodes = 7; insertion(4); insertion(3); insertion(7); insertion(5); insertion(2); insertion(1); insertion(10); display(mini); find_min(mini); return 0; }

输出如下：