Download Heapsort - Freddy Melgar Algarañaz
Document related concepts
Transcript
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