Download Heapsort - Freddy Melgar Algarañaz

Montículos Binarios
(Binary Heaps)
En este punto vamos a:
- definir un montículo de mínimos
- ver ejemplos
- operaciones sobre montículos:
Head/Cabecera
Dequeue/Borrado/Desencolado
Enqueue/Insertar/Encolar
Definición
• Un heap o montículo es una estructura de
datos similar a un árbol binario de búsqueda
pero ordenado de distinta forma por
prioridades y además se representa siempre
como un árbol binario completo representado
como un arreglo.
Definición
Un montículo es un árbol binario completo tal
que puede :
– Estar vacío
– El valor de la prioridad en la raíz es mayor,
(menor) o igual que la prioridad de cualquiera de
sus hijos
– Ambos subárboles son montículos o heap
60 50
1
2
40 30 20 10
3
4
5
6
…
7
8
9
max
3
Definición
• Un árbol binario no vacio es un montículo de
mínimos si:
– la clave asociada con la raíz es menor o igual a la
asociada con los sub-árboles
– ambos sub-arboles son montículos de mínimos
Definición
• A partir de la definición:
– un nodo simple es un montículo de mínimos
– todas las claves en el sub-árbol son mayores que
la raíz
Propiedades del heap
• Debe cumplir dos propiedades:
– un árbol binario completamente lleno, con la
posible excepción del nivel más bajo, el cual se
rellena de izquierda a derecha. Estos árboles se
denominan árboles binarios completos.
– Todo nodo debe ser mayor que todos sus
descendientes. Por lo tanto, el maximo estará en
la raíz y su búsqueda y eliminación se podrá
realizar rápidamente.
6
Características
• Todos los heaps son árboles binarios. No son
necesariamente ABBs.
• El árbol está completamente balanceado
excepto el último nivel, que debe estar lleno
de izquierda a derecha.
• Para un elemento del heap en la posición k,
sus hijos deberán estar en las posiciones 2k y
2k+1 del heap.
• Un HEAP puede representarse en un arreglo.
• Toda lista ordenada es un heap.
7
Ejemplo
• El siguiente es un montículo de mínimos:
Ejemplo
• Para visualizar las propiedades coloreamos los
nodos:
Ejemplo
• Observaciones:
– el árbol de la izquierda tiene tanto el elemento
más pequeño (7) como el mayor (89)
– no existen relaciones entre items con prioridad
similar
Head
• Obtener el elemento más pequeño:
– retornar la raíz
• En nuestro ejemplo, el mínimo elemento es 3
Dequeue (Desencolado/Borrado)
• Para eliminar el mínimo elemento
simplemente se promueve el nodo del subárbol que tiene el menor valor
• Luego, se aplica recursión hacia abajo del
árbol que ha promovido el valor más pequeño
Dequeue (Desencolado/Borrado)
• Usando nuestro ejemplo, eliminamos 3:
Dequeue (Desencolado/Borrado)
• Promovemos 7 (el menor de 7 y 12) a la raíz:
Dequeue (Desencolado/Borrado)
• En el sub-árbol de la izquierda, promovemos
el 9:
Dequeue
(Desencolado/Borrado)
• Recursivamente, promovemos el 19:
Dequeue
(Desencolado/Borrado)
• Finalmente , 55 es el nodo hoja, entonces lo
promovemos y liberamos el nodo
Dequeue (Desencolado/Borrado)
• Repitiendo esta operación otra vez, podemos
remover 7:
Dequeue (Desencolado/Borrado)
• Si removemos 9, ahora la promoción debe
hacerse desde el sub-árbol de la derecha:
Enqueue (Encolado/Inserción)
• La inserción en un montículo puede hacerse
ya bien:
– en la raíz (insertar el mayor elemento en uno de
los sub-árboles)
– en una hoja (mover hacia arriba si es más
pequeño que el padre)
• Nosotros utilizaremos el segundo enfoque
Enqueue (Encolado/Inserción)
• En el heap anterior insertaremos 17
• Seleccionamos un nodo arbitrario para
insertar un nuevo nodo hoja:
Enqueue (Encolado/Inserción)
• El nodo 17 es menor que el nodo 32,
entonces, los intercambiamos
Enqueue (Encolado/Inserción)
• El nodo 17 es menor que el 31, entonces, los
intercambiamos
Enqueue (Encolado/Inserción)
• El nodo 17 es menor que el nodo 19,
entonces, los intercambiamos
Enqueue (Encolado/Inserción)
• El nodo 17 es mayor que el 12, entonces,
hemos terminado
Enqueue (Encolado/Inserción)
• Observación: tanto el sub-árbol de la derecha
como el de la izquierda de 19 son mayores
que 19, entonces eso nos garantiza que no se
tiene que enviar un nuevo nodo abajo
• Este proceso se llama percolation (infiltrado),
esto es, los elementos más livianos
(pequeños) se mueven hacia arriba desde
abajo del montículo.
Encolado en un árbol completo
• Si queremos insertar en un árbol completo,
sólo se necesita ubicar el nuevo nodo como
una hoja en la posición adecuada e infiltrarlo
Encolado en un árbol completo
• Por ejemplo, insertando 25:
Encolado en un árbol completo
• Infiltramos 25 arriba hasta su ubicación
apropiada
• El montículo resultante es todavía un árbol
completo
Desencolado en un árbol completo
• Qué pasa cuando se remueve el elemento
mínimo?
• Si nosotros simplemente infiltramos,
crearemos un árbol no completo, ej.,
eliminando 12:
Desencolado en un árbol completo
• Estrategia alternativa: luego de infiltrar 32
arriba, el último elemento en el árbol binario
completo (32) es menor que cualquier subárbol, entonces lo copiamos arriba:
Desencolado en un árbol completo
• El resultado ahora es un árbol completo
Desencolado en un árbol completo
• Removiendo el siguiente elemento mínimo:
Desencolado en un árbol completo
• Removiendo el siguiente elemento mínimo:
Desencolado en un árbol completo
• Removiendo el siguiente elemento mínimo:
Operaciones
• Insertar / Agregar
• Eliminar
36
Agregar
• Pasos para insertar en un Heap
– Agregamos el nodo. (de izquierda a derecha)
– Comparamos son su padre.
• Si es mayor permutamos hasta llegar a la raíz
– Repetimos el paso 1 y 2 hasta llenar el nivel.
– Una vez llenado ese nivel pasamos al siguiente
nivel.
37
Agregar (Ejemplo)
Agregamos el 19
Agregamos el 24
19
19
24
Agregamos el 14
24
24
=>
19
19
Comparamos el 24 > 19
14
Comparamos el 14 > 24
Agregamos el 30
24
19
30
24
14
30
Comparamos el 30 > 19
=>
30
14
19
Comparamos el 30 > 24
=>
24
14
19
38
Agregar (Ejemplo)
Agregamos el 18
Agregamos el 25
30
24
19
30
=>
14
25
25
19
30
14
25
24
19
14
24
18
Comparamos el 25 > 24
Agregamos el 5
Comparamos el 18 > 14
30
=>
19
30
25
18
24
14
25
19
18
24
14
5
39
Eliminar
• Siempre se elimina la RAIZ
• Pasos para eliminar
– Eliminamos la raíz del heap
– Una vez eliminada remplazamos la raíz con el último nodo del
último nivel.
– Comparamos si los hijos de la nueva raíz son menores
• Si son menores no se hace ninguna permutación
• Si son mayores (o uno de ellos) se hace permutación
con el hijo mayor.
– Repetimos los pasos anteriores hasta no tener nodos para
eliminar.
40
Eliminar (Ejemplo)
Eliminamos el 30
Comparamos si el 5 > 25
30
5
25
19
=>
24
14
5
18
25
19
24
14
18
Comparamos si el 5 > 19
25
=>
25
5
19
24
14
18
=>
24
19
5
14
18
41
Eliminar ( Ejemplo)
Eliminamos el 25
Comparamos si el 24 > 19
Y si el 24 >18
25
=>
24
19
5
14
18
5
5
Comparamos
si el 14 > 19
Comparamos
si el 14 > 5
19
14
18
14
14
14
24
=>
5
19
18
19
24
19
5
Eliminamos el 24
19
24
18
18
=>
5
14
18
42
Eliminar (Ejemplo)
Eliminamos 19
Comparamos
si el 5 > 14
19
5
=>
18
14
Comparamos
si el 14 > 18
=>
18
14
5
18
14
5
Eliminamos 18
=>
14
18
18
5
14
5
5
=>
14
14
5
43
Eliminar (Ejemplo)
Eliminamos 14
Eliminamos 5
14
=>
5
5
=>
vació
5
Los nodos eliminados fueron:
30 25 24 19 18 14 5
44