Montón binomial

El "árbol binomial" vuelve a dirigir aquí. Para árboles de precios binomiales, consulte el modelo de precios de opciones binomiales .

En informática , un montón binomial es una estructura de datos que actúa como una cola de prioridad, pero también permite fusionar pares de montones. Es importante como implementación del tipo de datos abstractos del montón fusionable (también llamado montón fusionable ), que es una cola de prioridad que admite la operación de fusión. Se implementa como un montón similar a un montón binario pero usando una estructura de árbol especial que es diferente de los árboles binarios completos utilizados por los montones binarios. ^{[1] Los} montones binomiales fueron inventados en 1978 por Jean Vuillemin .^{[1] [2]}

Montón binomial

Un montón binomial se implementa como un conjunto de árboles binomiales (compárese con un montón binario , que tiene la forma de un solo árbol binario ), que se definen de forma recursiva de la siguiente manera: ^[1]

• Un árbol binomial de orden 0 es un solo nodo
• Un árbol binomial de orden tiene un nodo raíz cuyos hijos son raíces de árboles binomiales de pedidos , , ..., 2, 1, 0 (en este orden).${\displaystyle k}$${\displaystyle k-1}$${\displaystyle k-2}$

Árboles binomiales de orden 0 a 3: cada árbol tiene un nodo raíz con subárboles de todos los árboles binomiales de orden inferior, que se han resaltado. Por ejemplo, el árbol binomial de orden 3 está conectado a un árbol binomial de orden 2, 1 y 0 (resaltados como azul, verde y rojo respectivamente).

Un árbol binomial de orden tiene nodos y altura . El nombre proviene de la forma: un árbol binomial de orden tiene nodos en profundidad , un coeficiente binomial . Debido a su estructura, se puede construir un árbol binomial de orden a partir de dos árboles de orden adjuntando uno de ellos como el hijo más a la izquierda de la raíz del otro árbol. Esta característica es fundamental para la operación de combinación de un montón binomial, que es su principal ventaja sobre otros montones convencionales. ^{[1] [3]}${\displaystyle k}$${\displaystyle 2^{k}}$${\displaystyle k}$${\displaystyle k}$${\displaystyle {\tbinom {k}{d}}}$${\displaystyle d}$${\displaystyle k}$${\displaystyle k-1}$

Estructura de un montón binomial

Un montón binomial se implementa como un conjunto de árboles binomiales que satisfacen las propiedades del montón binomial : ^[1]

• Cada árbol binomial en un montón obedece a la propiedad de montón mínimo : la clave de un nodo es mayor o igual que la clave de su padre.
• Puede haber como máximo un árbol binomial para cada orden, incluido el orden cero.

La primera propiedad asegura que la raíz de cada árbol binomial contenga la clave más pequeña del árbol. De ello se deduce que la clave más pequeña de todo el montón es una de las raíces. ^[1]

La segunda propiedad implica que un montón binomial con nodos consta como máximo de árboles binomiales, donde es el logaritmo binario . El número y los órdenes de estos árboles están determinados de forma única por el número de nodos : hay un árbol binomial para cada bit distinto de cero en la representación binaria del número . Por ejemplo, el número decimal 13 es 1101 en binario, y, por lo tanto, un montón binomial con 13 nodos constará de tres árboles binomiales de órdenes 3, 2 y 0 (consulte la figura siguiente). ^{[1] [3]}${\displaystyle n}$${\displaystyle 1+\log _{2}n}$${\displaystyle \log _{2}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle 2^{3}+2^{2}+2^{0}}$

Ejemplo de un montón binomial que contiene 13 nodos con claves distintas.
El montón consta de tres árboles binomiales con órdenes 0, 2 y 3.

El número de formas diferentes en que los elementos con claves distintas se pueden organizar en un montón binomial es igual al divisor impar más grande de . Porque estos números son${\displaystyle n}$${\displaystyle n!}$${\displaystyle n=1,2,3,\dots }$

1, 1, 3, 3, 15, 45, 315, 315, 2835, 14175, ... (secuencia A049606 en la OEIS )

Si los elementos se insertan en un montón binomial en un orden aleatorio uniforme, cada uno de estos arreglos es igualmente probable. ^[3]${\displaystyle n}$

Implementación

Debido a que ninguna operación requiere acceso aleatorio a los nodos raíz de los árboles binomiales, las raíces de los árboles binomiales se pueden almacenar en una lista vinculada , ordenada por orden creciente del árbol. Debido a que el número de hijos para cada nodo es variable, no funciona bien que cada nodo tenga enlaces separados a cada uno de sus hijos, como sería común en un árbol binario.; en cambio, es posible implementar este árbol usando enlaces de cada nodo a su hijo de orden más alto en el árbol, y a su hermano del siguiente orden más pequeño que él. Estos punteros hermanos se pueden interpretar como los siguientes punteros en una lista enlazada de los hijos de cada nodo, pero con el orden opuesto de la lista enlazada de raíces: de mayor a menor orden, en lugar de viceversa. Esta representación permite vincular dos árboles del mismo orden entre sí, formando un árbol del siguiente orden mayor, en tiempo constante. ^{[1] [3]}

Fusionar

Para fusionar dos árboles binomiales del mismo orden, primero compare la clave raíz. Como 7> 3, el árbol negro de la izquierda (con el nodo raíz 7) se adjunta al árbol gris de la derecha (con el nodo raíz 3) como un subárbol. El resultado es un árbol de orden 3.

La operación de fusionar dos montones se utiliza como subrutina en la mayoría de las demás operaciones. Una subrutina básica dentro de este procedimiento fusiona pares de árboles binomiales del mismo orden. Esto se puede hacer comparando las claves en las raíces de los dos árboles (las claves más pequeñas en ambos árboles). El nodo raíz con la clave más grande se convierte en un hijo del nodo raíz con la clave más pequeña, aumentando su orden en uno: ^{[1] [3]}

función mergeTree (p, q) if p.root.key <= q.root.key return p.addSubTree (q) else  return q.addSubTree (p)

Esto muestra la fusión de dos montones binomiales. Esto se logra fusionando dos árboles binomiales del mismo orden uno por uno. Si el árbol combinado resultante tiene el mismo orden que un árbol binomial en uno de los dos montones, esos dos se fusionan nuevamente.

Para fusionar dos montones de manera más general, las listas de raíces de ambos montones se recorren simultáneamente de una manera similar a la del algoritmo de fusión , en una secuencia de órdenes de árboles más pequeños a órdenes más grandes. Cuando solo uno de los dos montones que se fusionan contiene un árbol de orden , este árbol se mueve al montón de salida. Cuando los dos montones contienen un árbol de orden , los dos árboles se fusionan en un árbol de orden para que se satisfaga la propiedad de pila mínima. Más adelante, puede ser necesario fusionar este árbol con algún otro árbol de orden en uno de los dos montones de entrada. En el curso del algoritmo, examinará como máximo tres árboles de cualquier orden, dos de los dos montones que fusionamos y uno compuesto por dos árboles más pequeños. ^{[1] [3]}${\displaystyle j}$${\displaystyle j}$${\displaystyle j+1}$${\displaystyle j+1}$

function merge(p, q) while not (p.end() and q.end()) tree = mergeTree(p.currentTree(), q.currentTree())  if not heap.currentTree().empty() tree = mergeTree(tree, heap.currentTree())  heap.addTree(tree) heap.next(); p.next(); q.next()

Because each binomial tree in a binomial heap corresponds to a bit in the binary representation of its size, there is an analogy between the merging of two heaps and the binary addition of the sizes of the two heaps, from right-to-left. Whenever a carry occurs during addition, this corresponds to a merging of two binomial trees during the merge.^[1][3]

Each tree has order at most ${\displaystyle \log _{2}n}$ and therefore the running time is ${\displaystyle O(\log n)}$.^[1][3]

Insert

Inserting a new element to a heap can be done by simply creating a new heap containing only this element and then merging it with the original heap. Because of the merge, a single insertion takes time ${\displaystyle O(\log n)}$. However, this can be sped up using a merge procedure that shortcuts the merge after it reaches a point where only one of the merged heaps has trees of larger order. With this speedup, across a series of ${\displaystyle k}$ consecutive insertions, the total time for the insertions is ${\displaystyle O(k+\log n)}$. Another way of stating this is that (after logarithmic overhead for the first insertion in a sequence) each successive insert has an amortized time of ${\displaystyle O(1)}$ (i.e. constant) per insertion.^[1][3]

A variant of the binomial heap, the skew binomial heap, achieves constant worst case insertion time by using forests whose tree sizes are based on the skew binary number system rather than on the binary number system.^[4]

Find minimum

To find the minimum element of the heap, find the minimum among the roots of the binomial trees. This can be done in ${\displaystyle O(\log n)}$ time, as there are just ${\displaystyle O(\log n)}$ tree roots to examine.^[1]

By using a pointer to the binomial tree that contains the minimum element, the time for this operation can be reduced to ${\displaystyle O(1)}$. The pointer must be updated when performing any operation other than finding the minimum. This can be done in ${\displaystyle O(\log n)}$ time per update, without raising the overall asymptotic running time of any operation.^{[citation needed]}

Delete minimum

To delete the minimum element from the heap, first find this element, remove it from the root of its binomial tree, and obtain a list of its child subtrees (which are each themselves binomial trees, of distinct orders). Transform this list of subtrees into a separate binomial heap by reordering them from smallest to largest order. Then merge this heap with the original heap. Since each root has at most ${\displaystyle \log _{2}n}$ children, creating this new heap takes time ${\displaystyle O(\log n)}$. Merging heaps takes time ${\displaystyle O(\log n)}$, so the entire delete minimum operation takes time ${\displaystyle O(\log n)}$.^[1]

function deleteMin(heap) min = heap.trees().first() for each current in heap.trees() if current.root < min.root then min = current for each tree in min.subTrees() tmp.addTree(tree) heap.removeTree(min) merge(heap, tmp)

Decrease key

After decreasing the key of an element, it may become smaller than the key of its parent, violating the minimum-heap property. If this is the case, exchange the element with its parent, and possibly also with its grandparent, and so on, until the minimum-heap property is no longer violated. Each binomial tree has height at most ${\displaystyle \log _{2}n}$, so this takes ${\displaystyle O(\log n)}$ time.^[1] However, this operation requires that the representation of the tree include pointers from each node to its parent in the tree, somewhat complicating the implementation of other operations.^[3]

Delete

To delete an element from the heap, decrease its key to negative infinity (or equivalently, to some value lower than any element in the heap) and then delete the minimum in the heap.^[1]

Applications

• Discrete event simulation
• Priority queues

See also

• Weak heap, a combination of the binary heap and binomial heap data structures

References

1. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Chapter 19: Binomial Heaps". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 455–475. ISBN 0-262-03293-7.
2. Vuillemin, Jean (1 April 1978). "A data structure for manipulating priority queues". Communications of the ACM. 21 (4): 309–315. doi:10.1145/359460.359478.
3. Brown, Mark R. (1978). "Implementation and analysis of binomial queue algorithms". SIAM Journal on Computing. 7 (3): 298–319. doi:10.1137/0207026. MR 0483830.
4. Brodal, Gerth Stølting; Okasaki, Chris (November 1996), "Optimal purely functional priority queues", Journal of Functional Programming, 6 (6): 839–857, doi:10.1017/s095679680000201x

External links

• Two C implementations of binomial heap (a generic one and one optimized for integer keys)
• Haskell implementation of binomial heap
• Common Lisp implementation of binomial heap