Montón de Fibonacci: inserción y unión

Fibonacci Heap es una colección de árboles con propiedades min-heap o max-heap. En Fibonacci Heap, los árboles pueden tener cualquier forma, incluso todos los árboles pueden ser Nodes únicos (esto es diferente a Binomial Heap donde cada árbol tiene que ser un árbol binomial). En este artículo, discutiremos la operación de inserción y unión en el montón de Fibonacci. 

Prerrequisitos: Montón de Fibonacci (Introducción)

Inserción: Para insertar un Node en un montón H de Fibonacci, se sigue el siguiente algoritmo: 

1. Cree un nuevo Node ‘x’.
2. Compruebe si el montón H está vacío o no.
3. Si H está vacío entonces: 
   • Haga que x sea el único Node en la lista raíz.
   • Establezca el puntero H(min) en x.
4. Más: 
   • Inserte x en la lista raíz y actualice H(min).

Ejemplo: 

Unión: la unión de dos montones de Fibonacci H1 y H2 se puede lograr de la siguiente manera: 

1. Únase a las listas raíz de los montones de Fibonacci H1 y H2 y cree un único montón de Fibonacci H.
2. Si H1(min) < H2(min) entonces: 
   • H(mín) = H1(mín).
3. Más: 
   • H(mín) = H2(mín).

Ejemplo: 

El siguiente es un programa para demostrar cómo construir e insertar en un montón de Fibonacci:  

// 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;
}

# Python program to demonstrate building
# and inserting in a Fibonacci heap
 
 
class node:
    def __init__(self):
        self.parent = None  # Assign data
        self.child = None  # Initialize next as null
        self.left = None
        self.right = None
        self.key = -1
 
 
# Creating min pointer as "mini"
mini = node()
 
# Declare an integer for number of nodes in the heap
no_of_nodes = 0
 
# Function to insert a node in heap
 
 
def insertion(val):
    new_node = node()
    new_node.key = val
    new_node.parent = None
    new_node.child = None
    new_node.left = new_node
    new_node.right = new_node
 
    global mini
    if mini.key != -1:
        (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
 
 
def display(mini):
    ptr = mini
    if (ptr == None):
        print("The Heap is Empty")
    else:
 
        print("The root nodes of Heap are: ")
        print(ptr.key, end="")
        ptr = ptr.right
        if(ptr != mini):
            print("-->", end="")
 
        while ptr != mini and ptr.right != None:
            print(ptr.key, end="")
            ptr = ptr.right
            if ptr != mini:
                print("-->", end="")
        print()
        print(f"The heap has {no_of_nodes} nodes")
 
# Function to find min node in the heap
 
 
def find_min(mini):
    print(f"min of heap is: {mini.key}")
 
 
# Driver code
no_of_nodes = 7
insertion(4)
insertion(3)
insertion(7)
insertion(5)
insertion(2)
insertion(1)
insertion(10)
 
display(mini)
 
find_min(mini)
 
# The code is contributed by Gautam goel (gautamgoel962)

The root nodes of Heap are: 
1-->2-->3-->4-->7-->5-->10
The heap has 7 nodes
Min of heap is: 1