Trabajo De Investigacion

1Trabajo de investigación









Trabajo de investigación sobre el heap binominal y Fibonacci











Israel castro ortega.
20 de mayo 2015.










Tabla de Contenidos

Capítulo 1 Introducción e información general 3
Capítulo 2 heap binominal 4
Operaciones con heap binominal 6
Amortización……………………………………………………………………………6
Amortización……………………………………………………………………………7
Capítulo 3heap fibonacci 8
Características Fibonacci heap……………………………….…………………………8
Operación con Fibonacci heap…………………………………………………………10
Capítulo 4 conclusión……………………………………………………………………
List of References 12



Introducción






En Informática, un Montículo de Fibonacci (o Heap de Fibonacci) es una estructura de datos subconjunto de los montículos, que a su vez, son un subconjunto especial dentrode los bosques de árboles. Resulta similar a un montículo binomial, pero dispone de una mejor relación entre el coste y su amortizació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 deuna cola con prioridad que soporte la operación de mezcla.
A continuación indagaremos de manera más amplias estas breves definiciones de estas 2 estructuras de datos, para eso usaremos gráficos, textos escritos y esquemas para informar de la mejor manera posible















“heap” binominal


Binomial heaps fue inventado en 1978 por J. voillemin. Que dan una estructura de datos para elmantenimiento de una colección de elementos, cada uno de los cuales tiene una válvula extraída de un conjunto ordenado, de tal manera que los nuevos elementos se pueden añadir y el elemento de valor mínimo extraído de manera eficiente.
Admiten las siguientes operaciones:

Makeheap(i) -> retorna un nuevo heap que contiene solo elementos i
Findmin (h) -> retorna un puntero al elemento de h de valormínimo
Insert(h,i) -> inserte una elemento i al heap h
Deletemin (h) -> elimina el elemento de valor mínimo de h
Meld (h, h`) -> combina los heaps h y h` dentro de un heap

Estos nombres no necesariamente son fijos y establecidos como “canon”, otros nombres para estas operaciones son
Mínimum (i) = findmin(h)
Deletemin(h) = extractmin(h)
Union(h, h`) = meld(h, h`)

A continuaciónveamos la eficiencia de estos métodos










Donde n es el número de Elemento en el montón.












heap binomiales son colecciones de árboles binomiales, que se definen inductivamente: el árbol binominal Bi, consta de una raízcon i niños B0, .... Bi-1.







(Explicación grafica de lo que intento decir)


Se demuestra fácilmente por inducción que Bi = 2 ** i.
Si los elementos de datos están dispuestas como vértices en un árbol, árbol que se dice que es heap-ordenado si el valor mínimo entre todos los vértices de cualquier subárbol se encuentra en la raíz del subárbol.
Un montón binomial es una colección deheap-ordenado árboles binomiales con un "min" puntero que apunta al árbol cuya raíz tiene un valor mínimo. Vamos a suponer que todos los niños de cualquier vértice se disponen en una lista doblemente enlazada circular, para que podamos vincular y desvincular subárboles en tiempo constante
Definición: el rango de x elementos, indicado como rango (x), es el número de x hijos. Por ejemplo, el rango (raíz deBi) = i. el rango de un árbol es el rango de su raíz.






ACOTACION

Pasando a otro punto (necesario para el siguiente punto (podríamos llamar a esto pre-punto)) una operación básica en los árboles binomiales es la vinculación. Dando dos Bi`s, podemos combinarlos en un Bi + 1, usando la raíz de un Bi un hijo de la raíz de la otra. Hacemos siempre el Bi con el valor de la raíz más grande del...