Montón binomial

¿Qué es un árbol binomial? 

Un Árbol Binomial de orden 0 tiene 1 Node. Se puede construir un árbol binomial de orden k tomando dos árboles binomiales de orden k-1 y haciendo que uno sea el hijo más a la izquierda o el otro. 

Un árbol binomial de orden k tiene las siguientes propiedades. 

• Tiene exactamente ^2k Nodes. 
• Tiene profundidad como k. 
• Hay exactamente kaiC _i Nodes en la profundidad i para i = 0, 1, . . . , k. 
• La raíz tiene grado k y los hijos de la raíz son árboles binomiales de orden k-1, k-2,… 0 de izquierda a derecha. 

k = 0 (Single Node)

 o

k = 1 (2 nodes) 
[We take two k = 0 order Binomial Trees, and
make one as a child of other]
  o
 /  
o     

k = 2 (4 nodes)
[We take two k = 1 order Binomial Trees, and
make one as a child of other]
     o
   /   \
  o     o
 /       
o        

k = 3 (8 nodes)
[We take two k = 2 order Binomial Trees, and
make one as a child of other]
      o   
   /  | \ 
  o   o  o
 / \  | 
o   o o   
     \           
      o         

Se hace referencia al siguiente diagrama de la segunda edición del libro CLRS . 

Montón binomial: 

Un montón binomial es un conjunto de árboles binomiales donde cada árbol binomial sigue la propiedad Min Heap. Y puede haber como máximo un árbol binomial de cualquier grado. 

Ejemplos Montón binomial: 

12------------10--------------------20
             /  \                 /  | \
           15    50             70  50  40
           |                  / |    |     
           30               80  85  65 
                            |
                           100
A Binomial Heap with 13 nodes. It is a collection of 3 
Binomial Trees of orders 0, 2, and 3 from left to right. 

    10--------------------20
   /  \                 /  | \
 15    50             70  50  40
 |                  / |    |     
 30               80  85  65 
                  |
                 100

Un montón binomial con 12 Nodes. Es una colección de 2 
árboles binomiales de órdenes 2 y 3 de izquierda a derecha. 

Representación binaria de un número y montones binomiales 
Un montón binomial con n Nodes tiene el número de árboles binomiales igual al número de bits establecidos en la representación binaria de n. Por ejemplo, sea n 13, hay 3 bits establecidos en la representación binaria de n (00001101), por lo tanto, 3 árboles binomiales. También podemos relacionar el grado de estos árboles binomiales con las posiciones de los bits establecidos. Con esta relación, podemos concluir que hay árboles binomiales O(Logn) en un montón binomial con ‘n’ Nodes. 

Operaciones de Binomial Heap: 
La operación principal en Binomial Heap es union(), todas las demás operaciones utilizan principalmente esta operación. La operación union() es combinar dos Binomial Heaps en uno. Discutamos primero otras operaciones, discutiremos la unión más tarde.

1. insert(H, k): inserta una clave ‘k’ en el montón binomial ‘H’. Esta operación primero crea un montón binomial con una sola clave ‘k’, luego llama a la unión en H y al nuevo montón binomial. 
2. get(H): una forma sencilla de ingresar() es recorrer la lista de raíces de Binomial Trees y devolver la clave mínima. Esta implementación requiere tiempo O (Iniciar sesión). Puede optimizarse a O(1) manteniendo un puntero a la clave raíz mínima. 
3. extracting(H): Esta operación aa también usa una union(). Primero llamamos a getMin() para encontrar el árbol binomial clave mínimo, luego eliminamos el Node y creamos un nuevo montón binomial conectando todos los subárboles del Node mínimo eliminado. Finalmente, llamamos a union() en H y en el Binomial Heap recién creado. Esta operación requiere tiempo O (Iniciar sesión). 
4. delete(H): Al igual que Binary Heap, la operación de eliminación primero reduce la clave a menos infinito, luego llama a extracting(). 
5. tecla de disminución (H): tecla de disminución() también es similar a Binary Heap. Comparamos la clave disminuida con su padre y si la clave del padre es más, intercambiamos claves y recurrimos para el padre. Nos detenemos cuando llegamos a un Node cuyo padre tiene una clave más pequeña o llegamos al Node raíz. La complejidad de tiempo de la tecla decreciente() es O(Logn). 

   Operación de unión en Binomial Heap: 
   Dados dos Binomial Heaps H1 y H2, union(H1, H2) crea un solo Binomial Heap. 

6. El primer paso es simplemente fusionar los dos montones en un orden de grados no decreciente. En el siguiente diagrama, la figura (b) muestra el resultado después de la fusión. 
7. Después de la combinación simple, debemos asegurarnos de que haya como máximo un árbol binomial de cualquier orden. Para hacer esto, necesitamos combinar árboles binomiales del mismo orden. Recorremos la lista de raíces fusionadas, hacemos un seguimiento de los tres puntos, anterior, x y siguiente-x. Puede haber los siguientes 4 casos cuando recorremos la lista de raíces. 
   —–Caso 1: Los órdenes de x y next-x no son iguales, simplemente avanzamos. 
   En los siguientes 3 casos, los órdenes de x y next-x son los mismos. 
   —–Caso 2: Si el orden de next-next-x también es el mismo, sigue adelante. 
   —–Caso 3: si la clave de x es menor o igual que la clave de next-x, entonces haga de next-x un hijo de x vinculándolo con x. 
   —–Caso 4: Si la clave de x es mayor, entonces haz de x el hijo de la siguiente. 

   El siguiente diagrama está tomado de la segunda edición del libro CLRS . 
    

Análisis de Complejidad de Tiempo:

Operaciones	montón binario	Montón binomial	Montón de Fibonacci
Procedimiento	Peor de los casos	Peor de los casos	Amortizado
hacer montón	Θ(1)	Θ(1)	Θ(1)
Insertar un Node	Θ(log(n))	O(registro(n))	Θ(1)
Encontrar la clave mínima	Θ(1)	O(registro(n))	O(1)
Extraer clave mínima	Θ(log(n))	Θ(log(n))	O(registro(n))
Unión o fusión	Θ(n)	O(registro(n))	Θ(1)
Disminución de una clave	Θ(log(n))	Θ(log(n))	Θ(1)
Eliminación de un Node	Θ(log(n))	Θ(log(n))	O(registro(n))

¿Cómo representar Binomial Heap?  
Un montón binomial es un conjunto de árboles binomiales. Un árbol binomial debe representarse de una manera que permita el acceso secuencial a todos los hermanos, comenzando por el hermano más a la izquierda (Necesitamos esto y extraer() y eliminar()). La idea es representar árboles binomiales como la representación del hijo más a la izquierda y del hermano derecho, es decir, cada Node almacena dos punteros, uno al hijo más a la izquierda y el otro al hermano derecho.  

Implementación del montón binomial