Heap Binomial

Heap Binomial

Historia

En Ciencia de la Computación se denomina Heap Binomial a una estructura de datos parecida al Heap Binario pero que brinda una operación eficiente de mezcla entre dos Heaps. Esta propiedad hace que se utilice como un mergeable heap, al igual que el Heap de Fibonacci, en la implementación de una cola de prioridades que soporte la operación de mezcla.

Árboles Binomiales y Heaps Binomiales

Un Heap binomial es una colección de Árboles Binomiales. Un Árbol Binomial es un árbol ordenado definido recursivamente de la siguiente forma:

1. Un árbol binomial de orden 0 ( B₀ ) es un solo nodo
2. Un árbol binomial de orden k ( B_k ) tiene un nodo raíz cuyos hijos son raíces de árboles binomiales de orden k-1, k-2… 2, 1, 0 en ese orden.

 

Observe que la definición 2 es similar a decir que un árbol binomial de orden k está formado por la unión de dos árboles binomiales de orden k-1 donde la raíz de uno de ellos es el hijo más a la izquierda del otro.

 

Esta estructura tiene gran importancia en la implementación de la operación de unión entre dos Heaps binomiales.

Propiedades de los Árboles Binomiales

Un árbol binomial de orden k (Bk) tiene:

• 2^k nodos
• Altura k

${\displaystyle {\binom {k}{i}}}$ 

nodos a la profundidad i. (el nombre proviene de esta propiedad, ver Coeficientes Binomiales)

Estructura de un Heap Binomial

Un Heap Binomial es implementado como un conjunto de árboles binomiales que satisfacen las propiedades del Heap Binomial

Propiedades del Heap Binomial:

1. Cada árbol binomial en el Heap binomial cumple la propiedad de min-heap (La llave de cualquier nodo del árbol es mayor o igual que la llave de su padre)
2. Solo puede haber 0 o 1 árboles binomiales de cada orden en el heap.

La primera propiedad asegura que la raíz de cada árbol binomial contiene la menor llave de ese árbol, y la segunda que un Heap Binomial de n nodos posee a lo sumo log n + 1 Árboles Binomiales. De hecho, el número y orden de los árboles está determinado por la cantidad de nodos. Cada Árbol Binomial se corresponde con un dígito en la representación binaria de n. Por ejemplo para n =13 su número binario es 1101, o sea:

13=2³+2²+2⁰

Entonces un Heap Binomial con 13 nodos poseería 3 árboles binomiales de órdenes 3,2 y 0 (ver figura).

 

Usualmente un Heap Binomial se implementa como una lista enlazada de árboles binomiales ordenada crecientemente por el orden de cada árbol binomial.

Operaciones sobre un Heap Binomial

Mezcla

Como se menciona anteriormente, la más sencilla e importante operación es la mezcla de 2 árboles binomiales del mismo orden en dos Heap binomiales. Esto se logra fácilmente debido a la estructura de los mismos. Como el nodo raíz de cada uno posee el elemento mínimo de ese árbol, comparando las dos raíces se puede decidir la raíz del nuevo árbol (la menor de las dos). Entonces el otro árbol se convierte en un subárbol del primero. Esta operación es la base de la mezcla de dos Heaps Binomiales. La operación de mezcla de dos heaps es, quizás, la más importante. Esta operación es utilizada como subrutina de muchas otras operaciones en el heap. En la mezcla de dos Heaps se deben unificar las colecciones de Árboles Binomiales de ambos. Para esto se realiza lo siguiente: Para cada posible orden k de los árboles en los heaps:

1. Si el árbol binomial de orden k no se encuentra en ninguno de los dos se pasa al siguiente orden
2. Si solo uno de los heaps contiene el árbol binomial de orden k este se agrega al nuevo heap y se pasa al siguiente orden.
3. Si los dos heaps contienen un árbol binomial de orden k se mezclan estos dos árboles mediante el procedimiento anterior y se obtiene un árbol de orden k+1 (Note que es posible que este árbol nuevo surgido de la mezcla sea nuevamente mezclado con otro árbol de orden k+1 ya existente en alguno de los dos heaps).

En el transcurso del algoritmo debemos examinar a lo sumo 3 árboles del mismo orden (2 procedentes de los 2 heaps que estamos mezclando y 1 de la mezcla en la iteración anterior de 2 árboles más pequeños). Dado que cada árbol binomial se corresponde con un bit en la representación binaria de n (tamaño de cada heap), se puede establecer una analogía entre mezclar dos heaps y la adición binaria de los tamaños de cada heap. Donde aparece un acarreo en la adición ocurre una mezcla de 2 árboles binomiales. Como cada heap tiene a lo sumo log n árboles binomiales y mezclar dos árboles se puede implementar en O(1) el orden de la mezcla es O(log n).

Insertar

Insertar un nuevo elemento en el heap se puede hacer fácilmente creando un nuevo heap que solo contenga a ese elemento y mezclando este con el heap original. Debido a la mezcla, la inserción es de O(log n) no obstante tiene un costo amortizado de O(1).

Buscar Mínimo

Para encontrar el mínimo elemento del heap se busca la menor llave de todas las raíces de los árboles binomiales que forman el heap. Como se cumple la propiedad de min-heap para cada árbol, en las raíces de estos se encuentra el menor elemento de cada uno. Esto puede realizarse fácilmente en O(log n) ya que solo existen a lo sumo log n árboles binomiales en el Heap. Usando un puntero adicional al árbol binomial que contiene la menor llave en la raíz se puede implementar esta operación en O(1). El puntero debe ser actualizado cuando se ejecute cualquier acción distinta de Find Min. Esto se puede hacer en O(log n) sin incrementar el orden de las otras operaciones.

Extraer Mínimo

Para borrar el menor elemento del heap primero se busca, luego se borra de su árbol binomial y se obtiene como resultado una lista de los subárboles que contenía como hijos. Entonces se transforma esta lista en un heap Binomial organizando los árboles binomiales por el orden de menor a mayor y se mezcla con el heap original. Como a lo sumo hay log n árboles binomiales y cada árbol binomial tiene altura a lo sumo log n y mezclar Heaps binomiales es O(log n) esta operación es de O(log n).

ExtraeMínimo(H)

1. x <- árbol binomial con la mínima raíz en la lista de raíces de H
2. borrar x de H
3. min <- raíz de x
4. x' <- lista de hijos de x
5. invertir el orden de x'
6. x<- HeapBinomial(x')
7. H.mezcla(x)
8. return min

Disminuir Llave

Después de disminuir la llave de un elemento, este puede ser menor que la llave de su padre violando la propiedad de min-heap. Si este es el caso se intercambia el elemento con su padre hasta que la propiedad sea cumplida o el nodo sea la raíz del árbol, esta actualización se conoce también como HEAPIFY en los Heaps Binarios. Como cada árbol binomial tiene altura a lo sumo log n, esta operación es de O(log n) para el caso peor.

DisminuirLLave(H,x,k)

1. if ( k > x.key )
2. ____Lanzar error "La nueva llave es mayor que la anterior"
3. x.key <- k
4. y <- x
5. z <- y.parent
6. while(z!= NIL and y.key < z.key)
7. ____intercambiar y.key y z.key
8. ____y <- z
9. ____z <- y.parent

Borrar

Para borrar un elemento del heap se disminuye su llave a menos infinito (o sea, algún valor menor que cualquier elemento en el heap) y después se elimina el menor elemento del heap.

 Borrar(H,x) 

1. __ H.DisminuirLLave(x,-infinito)
2. __ H.ExtraeMínimo()

Heap Binario vs Heap Binomial

En la figura se muestra una comparación en los costos de cada operación entre el Heap binomial y el binario.

 

Aplicaciones

• Simulación por computadora
• Priority queues

Véase también

• Heap de Fibonacci
• Heap

Bibliografía

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 19: Binomial Heaps, pp.455–475.
2. Vuillemin, J. (1978). A data structure for manipulating priority queues. Communications of the ACM 21, 309–314.

Enlaces externos

• Binomial Heaps (English)
• Visualization of binomial heap
• Python implementation of binomial heap
• 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

•   Datos: Q864032
•   Multimedia: Category:Binomial heap