【高级数据结构(如何实现斐波那契堆–插入和联合操作())】先决条件:斐波那契堆(简介)
斐波那契堆是具有最小堆或最大堆属性的树的集合。在斐波那契堆中, 即使所有树都可以是单个节点, 树木也可以具有任何形状(这与二项式堆不同, 后者每棵树都必须是二项式树)。
在本文中, 我们将讨论斐波那契堆上的插入和联合操作。
插入:要将节点插入斐波那契堆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;
}
输出如下:
The root nodes of Heap are:
1-->
2-->
3-->
4-->
7-->
5-->
10
The heap has 7 nodes
Min of heap is: 1
推荐阅读
- 算法(使用步数1、2或3计算到达第n个楼梯的所有方式)
- 算法(如何查找矩阵中每一列的最大元素())
- 算法设计(如何打印字符串中每个单词的最后一个字符())
- 如何在Windows中为Python安装OpenCV()
- JavaScript性能问题和优化指南
- Android自定义XML属性
- Android手机图片适配问题
- android权限--android开发中的权限及含义(上)
- android 安卓 微信布局