Monticulos Binario

Colas con prioridades y
Montículos
(Lección 19…)

Cola con prioridades
• Cola con prioridades:
– Se pueden añadir elementos en cualquier orden,
– Los elementos se recuperan en orden creciente
– “Cola de espera” pero el valor de cada elemento establece
su “prioridad” (mínimo valor= máxima prioridad)
• El primero en salir es el elemento de mayor prioridad
• Ejemplo: cola en losservicios de urgencia en hospitales
– Elementos de cualquier tipo, con relación de orden total
para el campo que exprese la “prioridad”
– Puede ser Cola con prioridad de mínimos o cola con
prioridad de máximos

• TAD con las operaciones:

– Inserción de un elemento
– Observación del elemento de valor mínimo (= max. prioridad)
– Eliminación del mínimo elemento

Especificación Algebraica
especcolasConPrioridades
parámetro formal
género elemento
Operación _≤_: elemento elemento → bool
Ecuaciones ≤ es una relación de orden total
{a≤b significa que a tiene más prioridad que b}
fpf
género colaP
operaciones
colaVacía: → colaP
añadir: colaP elemento → colaP
parcial min: colaP → elemento
parcial eliminarMin: colaP → colaP
vacía?: colaP → bool

Especificación Algebraicadominios de definición c:colaP; e:elemento
min(añadir(c,e))
eliminarMin(añadir(c,e))
ecuaciones c:colaP; e,e1,e2:elemento
añadir(añadir(c,e1),e2) = añadir(añadir(c,e2),e1)
min(añadir(colaVacía,e)) = e
e1≤e2  min(añadir(añadir(c,e1),e2)) = min(añadir(c,e1))
e1>e2  min(añadir(añadir(c,e1),e2)) = min(añadir(c,e2))
eliminarMin(añadir(colaVacía,e)) = colaVacía
e1≤e2 eliminarMin(añadir(añadir(c,e1),e2)) =añadir(eliminarMin(añadir(c,e1)),e2)
e1>e2 
eliminarMin(añadir(añadir(c,e1),e2)) =añadir(eliminarMin(añadir(c,e2)),e1)
vacía?(colaVacía) = verdad
vacía?(añadir(c,e)) = falso
Fespec

Implementación de colas con prioridad
• Diferentes implementaciones para colas con
prioridad:

– Lista no ordenada
• Añadir, colaVacía y vacía? con coste constante
• Min y eliminarMin con costelineal
– Lista ordenada (de menor a mayor)
• Añadir coste lineal
• Min, eliminarMin, vacía? y colaVacía con coste constante
– Montículo (heap)
• Implementación eficiente para colas con prioridad

Montículos
• Un árbol binario se dice parcialmente ordenado si verifica
las siguientes propiedades:
– El elemento raíz es menor o igual que el resto de los
elementos del árbol, y
– Lossubárboles izquierdo y derecho son árboles binarios
parcialmente ordenados

Montículos
• Un árbol es completo cuando todas sus hojas tienen la

misma profundidad
• Un árbol se dice casi-completo (tb. llamado semicompleto)
cuando se puede obtener a partir de un árbol completo
eliminando hojas consecutivas del último nivel, comenzando
por la que está más a la derecha

Montículos
• Sedenomina montículo a un
árbol binario parcialmente
ordenado casi-completo

• Un montículo de mínimos es un árbol binario casicompleto donde:
– el elemento raíz es menor que todos los elementos en el hijo
izquierdo y en el derecho, y
– ambos hijos son a su vez montículos de mínimos

• Un montículo de máximos es un árbol binario casi-completo donde:
– el elemento raíz es mayor que todos loselementos en el hijo izquierdo y en
el derecho, y
– ambos hijos son a su vez montículos de máximos
•

Un applet que permite construir montículos de máximos: http://people.ksp.sk/~kuko/bak/

Montículos

• Representación de la cola con prioridades como un montículo:
– operaciones colaVacía, min y vacía?, serán de coste constante
– Operaciones añadir y eliminarMin: requieren recorrer un caminodesde la raíz hasta una hoja ( o a la inversa)
• En el peor caso la longitud del camino en un árbol es del
orden del número de elementos del árbol
• Pero si se garantiza un árbol binario casi-completo  el coste
en el peor caso se reduce al orden del logaritmo del número
de elementos del árbol

Montículos
• Añadir un nuevo elemento en un montículo:
– 1º) Se coloca el nuevo...