Montón binomial

Un montón binomial es una estructura de datos que implementa el tipo de datos abstracto " cola de prioridad ", que es un conjunto de árboles binomiales con dos propiedades:

la clave de cada nodo no es menor que la clave de su padre;
todos los árboles binomiales tienen diferentes tamaños.

De estas propiedades se siguen dos consecuencias. Primero, la raíz de cada uno de los árboles tiene la clave más pequeña entre sus vértices. En segundo lugar, el número total de vértices en el montón binomial determina de forma única el tamaño de los árboles incluidos en él. Por ejemplo, un montón binomial con vértices consta de tres árboles de altura 3, 2 y 0 y que tienen 8, 4 y 1 elementos, respectivamente (ver Fig.) ${\ estilo de visualización 13 = 2 ^ {3} + 2 ^ {2} + 2 ^ {0}}$

Las siguientes operaciones se realizan en el tiempo , donde n es el número de vértices: $O(\log n)$

Insertar un nuevo elemento (amortizado ) $O(1)$
Encontrar el elemento con la clave mínima
Eliminar un elemento con una clave mínima
Decrementando el valor de la clave de un elemento dado
Eliminando este artículo
Unión de dos montones.

Por lo tanto, el montón binomial es un montón combinado , es decir, además de las operaciones de cola de prioridad estándar (agregar, eliminar, extraer el mínimo, cambiar claves), proporciona una operación adicional de combinar dos montones.

Véase también

Árbol (estructura de datos)
Árbol de búsqueda binario Árbol (teoría de grafos) estructura de árbol
Árboles binarios	árbol binario árbol en T
Árboles binarios autoequilibrados	árbol AA árbol AVL árbol rojo-negro árbol de juego árbol con multas árbol cartesiano árbol de fibonacci árbol B árbol en T
árboles B	2-3-árbol árbol B⁺ árbol B* B x -árbol árbol de la UB 2-3-4 árbol (a,b)-árbol arbol bailando
árboles de prefijo	árbol de sufijos Árbol de prefijos comprimido Árbol de búsqueda ternario
Partición binaria del espacio	árbol k-dimensional árbol de vicepresidentes
Árboles no binarios	Árbol cuádruple octárbol Octree voxel disperso árbol exponencial árbol PQ
Rompiendo el espacio	R-árbol Árbol R de Hilbert R+-árbol R*-árbol árbol X M-árbol árbol de fenwick Árbol de segmentos
Otros árboles	montón árbol de hachís árbol de los dedos árbol métrico árbol de revestimiento árbol BK Árbol de doble cadena iDistancia Árbol de corte de enlace árbol LSM
Algoritmos	Primera búsqueda en amplitud Primera búsqueda en profundidad algoritmo DSW protocolo de árbol de expansión