1Estructuras de Datos

Tema 3. Montculos

1. Definiciones bsicas2. Implementacin3. Operaciones con montculos4. Funciones de manipulacin

Montculos

Definiciones bsicas:

Un rbol binario satisface la condicin de montculosi cada padre es mayor que sus hijos

A diferencia de los rboles binarios ordenados, no hay ninguna condicin que relacione a los hijos de un mismo padre

Un rbol binario es un montculo si satisface la condicin de montculo y, adems, es un rbol binario completo

2

Montculos

Definiciones bsicas:

En un rbol binario completo todos los niveles del rbol (excepto tal vez el ltimo) estn completos y en el ltimo nivel todos los hijos estn acumulados del mismo lado (por ejemplo a la izquierda)

El elemento (uno de los) de mayor valor del montculo se denomina raz del montculo

Montculos

12

10

9

8 6 12

10

9

8 6

no es completo10

12

9

8 6 es un montculo

no satisface la condicin de montculo

3Montculos

Utilizacin:

Problemas que requieran que los datos estn siempre ordenados para tener acceso al elemento:

Mayor: montculo de mximos Menor: montculo de mnimos

Al estado de orden del montculo se le denomina propiedad de montculo Cada vez que se modifica la estructura se debe

restaurar la propiedad de montculo

Montculos

Implementacin:

Al ser rboles binarios completos se implementan mediante un array

Si el array es de 1 .. N:Los nodos de profundidad k del rbol se almacenan ledos

de izda. a dcha en:T[2k], T[2k+1],T[2k+1-1]

Los hijos del nodo T[i] son respectivamente:T[2i] y T[2i+1]

El padre de T[i] est en la posicin: i div 2

4

Montculos

Implementacin:Si el array es de 0 .. N-1:

Los nodos de profundidad k del rbol se almacenan ledos de izda. a dcha en:

T[2k -1], T[2k],T[2k+1- 2]

Los hijos del nodo T[i] son respectivamente:

T[2i+1] y T[2i+2]

El padre de T[i] est en la posicin: (i-1) div 2

Montculos

Operaciones:

Hay dos operaciones principales:

Crear un montculo

Eliminar la raz de un montculo restaurando la propiedad del montculo

5Montculos

Operaciones. Crear un montculo Creacin de un montculo a partir de los elementos: 10,

5, 3, 6, 12

10

(1)

10

(2)

5

10

(3)

5 3

10

(4)

5 3

6

10

6 3

5

Montculos

Operaciones. Crear un montculo Creacin de un montculo a partir de los elementos: 10,

5, 3, 6, 12

(5)

10

6 3

5 12

10

12 3

5 6

12

10 3

5 6

6

Montculos

Operaciones. Crear un montculo

Se inserta un nuevo elemento al final del montculo (primera posicin libre) Si se mantiene la propiedad del montculo no hay que hacer ninguna

operacin

Si no se mantiene la propiedad del montculo hay que restaurarla Se restaura la propiedad del montculo intercambiando el nuevo elemento

con su padre cuantas veces sea necesario, a esta operacin de subir en el montculo se la denomina flotar un elemento

El nuevo elemento sube en el montculo (flota) y sus padres bajan en el montculo (se hunden)

A la operacin de bajar en un montculo se la denomina hundir

Montculos

Operaciones. Crear un montculo

Nmero de operaciones en el peor de los casos para crear un montculo con N elementos:

Al insertar el K-simo elemento, ste puede subir un mximo de log2 k niveles

El nmero mximo de veces que tendramos que intercambiar dos elementos al construir un montculo es log2 1 + log2 2 + ... + log2 N, que es O(N log2 N) = O(N log N)

7Montculos

Operaciones. Eliminar la raz sucesivamente

(1)

12

10 3

5 6

6

10 3

5

10

6 3

5

Montculos

Operaciones. Eliminar la raz sucesivamente

(2)

10

6 3

5

5

6 3

6

5 3

8

Montculos

Operaciones. Eliminar la raz sucesivamente

(3)

6

5 3

3

5

5

3

(4)

5

3

3

(5)

3

Montculos

Operaciones. Eliminar la raz sucesivamente

Se elimina la raz del montculo y como esa posicin no debe quedar vaca se reemplaza por el ltimo elemento del montculo

Si no se mantiene la propiedad del montculo hay que restaurarlaPara restaurarla se intercambia la nueva raz con el mayor de sus

hijos cuantas veces sea necesario

En cada paso la nueva raz va bajando (hundindose) y el mayor de sus hijos va subiendo (flotando) hasta que la nueva raz no sea menor que ninguno de sus hijos

9Montculos

Operaciones. Eliminar la raz sucesivamente

Nmero de operaciones en el peor de los casos para eliminar los N elementos de un montculo:

Al eliminar el K-sima raz la nueva puede bajar un mximo de log2 (N-k-1) niveles

El nmero mximo de veces que tendramos que intercambiar dos elementos al destruir un montculo es log2 (N-1) + log2 (N-2) + ... + log2 2, que es O(N log2 N) = O(N log N)

Montculos

Ordenar un array por medio de un montculo

Si se tiene un array de tamao N se crea un montculo y luego se destruye se obtiene un array ordenado

Este algoritmo de ordenamiento se denomina ordenamiento por montculo

El coste de este algoritmo es de O(N log N) en el peor de los casos: igual que otros conocidos basados en intercambios

10

Montculos

Funciones de manipulacin

Creacinfun montculoVaco(v: array) dev m:montculo;

Devuelve un montculo vaco. Ejemplo:

montiEjemplo montculoVaco();

Montculos

Funciones de manipulacin

Modificacin: hundirfun hundir(i:ndice, m:montculo) dev m:montculo

Restaura la propiedad de montculo perdida por ser T[i] menor que alguno de sus hijos. Ejemplo:

montiEjemplo hundir(i, montiEjemplo);

11

Montculos

Funciones de manipulacin

Modificacin: flotarfun flotar(i:ndice, m:montculo) dev m:montculo

Restaura la propiedad de montculo perdida por ser T[i] mayor que su padre. Ejemplo:

montiEjemplo flotar(i, montiEjemplo);

Montculos

Funciones de manipulacin

Modificacin: aadir nodofun anadirNodo(e:elemento, m:montculo) dev

m:montculo

Aade el valor e y flota este valor hasta restaurar la propiedad de montculo . Ejemplo:

montiEjemplo anadirNodo(e, montiEjemplo);

12

Montculos

Funciones de manipulacin

Modificacin: borrar razfun borrarRaiz(m:montculo) dev m:montculo

Elimina la raz del montculo y restaura la propiedad de montculo. Ejemplo:

montiEjemplo borrarRaiz(montiEjemplo);

Montculos

Funciones de manipulacin

Consulta: vacofun vacio(m:montculo) dev b:booleano

Comprueba si en el montculo hay algn elemento. Ejemplo:

varBooleana vacio(montiEjemplo);

13

Montculos

Funciones de manipulacin

Consulta: razfun raiz(m:montculo) dev e:elemento

Devuelve elemento de mayor valor del montculo sin borrarlo. Ejemplo:

elemento raiz(montiEjemplo);

Montculos

Funciones de manipulacin. Coste

CteraizCtevacioO(log N)borrarRaizO(log N)anadirNodoO(log N)flotarO(log N)hundirCtemontculoVacoCosteFunciones