Download i/2 - Biblioteca de la UNS

Tópicos I
Unidad I
Árboles, montículos y grafos
Semana 3
Cola de prioridades, montículos
Objetivos Generales
Entender el manejo, uso de algoritmos y
estructuras de datos avanzados, haciendo
énfasis en los algoritmos de internet,
seguridad y redes.
Objetivo Específico
Implementar
algoritmos
utilizando
estructura de datos avanzadas.
Objetivo Instruccional
Implementar algoritmos que permitan la
asignación de prioridades adecuadas y
que sirvan como base para la
construcción
de
algoritmos
mas
avanzados.
Contenidos
Cola de Prioridades
Montículos binarios
Montículos – d
Montículos binarios a la izquierda
Cola de prioridades
Introducción
En muchas aplicaciones los registros con clave se
deben procesar en orden, pero no necesariamente
en orden completo, ni todos a la vez. A veces se
forma un conjunto de registros y se procesa el mayor;
a continuación posiblemente se incluyan otros
elementos y luego se procesa el nuevo registro
máximo y así sucesivamente.
Una estructura de datos apropiada para un entorno
como este es aquella que permita insertar un nuevo
elemento y eliminar el mayor. Esta estructura que se
puede contrastar con las colas (donde se elimina el mas
antiguo) o con las pilas (donde se elimina el mas reciente), se
denomina cola de prioridad.
Cola de prioridades
Introducción
• Las colas de prioridad son estructuras de datos
que resultan ser útiles en muchas aplicaciones
informáticas.
• Es útil pensar en
los valores de las claves
asociados con los elementos como prioridades.
Así, las claves obedecen a un relación de orden
total.
Cola de prioridades
Las aplicaciones de las colas de
prioridades incluyen por ejemplo:
• la gestión de un planificador de tareas en
un Sistema MultiUsuario.
– los trabajos que consumen menos recursos
– los trabajos del administrador del sistema
• la gestión de los trabajos enviados a
impresión
– los trabajos más importantes primero
– los trabajos más cortos primero
Cola de prioridades
Por razones de utilidad se debe precisar algo mas
sobre la forma de tratar las colas de prioridad,
puesto que existen varias operaciones que pueden
ser necesario llevar a cabo sobre ellas, para
preservarlas y poderlas utilizar con eficacia en las
aplicaciones.
Lo que se desea es construir y mantener una
estructura de datos que contenga registros con
claves numéricas (prioridades) y que cuente con
algunas de las operaciones siguientes:
• Construir una cola de prioridad a partir de N elementos
• Insertar un nuevo elemento
• Suprimir el elemento mas grande
• Cambiar la prioridad de un elemento
• Unir dos colas de prioridad en una mas grande
Cola de prioridades
Las operaciones más importantes en una cola de
prioridades se refieren aquellas que permiten
repetidamente seleccionar el elemento de la cola
de prioridad que tiene como clave el valor mínimo
(máximo).
Esto conlleva a que una cola de prioridad P debe
soportar las siguiente operaciones:
ColaPrioridad(T)
Insertar(P,x): añade el elemento x a la cola de
prioridad
EncontrarMin(P): Devuelve el elemento de P con la
prioridad con menor valor.
EliminarMin(P): Quita y devuelve el elemento con la
prioridad con menor valor.
Cola de prioridades
Implementaciones de una Cola de
Prioridades
• Arboles equilibrados (AVL, Rojo y Negro)
 Permite las operaciones en O(log n).
 Se mantiene la propiedad de ABB.
 Se añade costo adicional por las operaciones
de equilibrio.
• Montículos Binarios
• Montículos a la izquierda
Montículos binarios
Propiedades estructurales de los
montículos
• Un montículo binario (o simplemente montículo o heap) es
un árbol binario completo: todos los niveles están
llenos con la posible excepción del nivel mas bajo,
que se llena de izquierda a derecha.
• Un árbol binario completo de altura h, tiene entre 2h
y 2h+1-1 nodos
• Esta regularidad facilita su representación mediante
un vector
• Para cualquier elemento en la posición i del vector,
el hijo izquierdo esta en la posición 2i, el hijo
derecho en 2i+1 y el padre en i/2
Montículos binarios
Propiedades de orden de los
montículos
1. El mínimo (máximo) esta en la raíz
2. Y como todo subárbol también es un montículo,
todo nodo debe ser menor (mayor) o igual que
todos sus descendientes
Montículos binarios
Ejemplo de montículos de
máximos
15
1
2
4
8
8
5
9
10
5
7
12
3
13
9
8
7
12
11
5
4
3
5
6
15
13
12
8
9
5
8
7
5
3
4
5
1
2
3
4
5
6
7
8
9
10
11
12
Montículos binarios
Ubicación en el vector de un
elemento
15
1
2
13
8
4
8
9
10
5
7
9
5
5
7
8
5
4
3
12
12
11
i=3
i/2=1
6
3
2*i=2*3=6
2*i+1=2*3+1=7
15
13
12
8
9
5
8
7
5
3
4
5
1
2
3
4
5
6
7
8
9
10
11
12
Montículos binarios
Al hacer uso de un vector, se observa
que:
• No hay necesidad de almacenar
punteros como en los ABB.
• Los cálculos de índices tardan menos
tiempo que los de referencia de
punteros
asociados
a
una
representación enlazada.
Montículos binarios
Mantenimiento de montículos
La
operación
EncontrarMin()
o
EncontrarMax(), se realiza en orden constante
ya que solo será necesario acceder al valor
de la raíz.
Las operaciones Insertar(x), EliminarMin() o
EliminarMax()
no tienen implantaciones
triviales en un montículo binario. Es necesario
asegurar que ambas operaciones no
destruyan las propiedades del montículo.
Montículos binarios
Insertar (x):
Al insertar un elemento x en un montículo de n
elementos debe resultar un árbol binario de n+1
elementos, esto es:
•El nodo se añade como una hoja extrema creciendo
de izquierda a derecha (n+1).
(garantiza la
propiedad de forma)
•Se garantiza la propiedad de ordenamiento
2
2 8 3 10
2 16 7 18 13 15 4
8
10
13
3
16
15
4
7
18
Ejemplo de
montículos de
mínimos
Montículos binarios
Reordenando para
garantizar las propiedades
2
8
10
13
3
4
15
7
18
16
2 8 3 10
2 4 7 18 13 15 16
Montículos binarios
Reordenando para
garantizar las propiedades
2
4
10
13
3
8
15
7
18
16
2 4 3 10
2 8 7 18 13 15 16
Montículos binarios
Resultado final
2
4
10
13
3
8
15
7
18
16
2 4 3 10
2 8 7 18 13 15 16
Montículos binarios
Eliminar():
Al eliminar un elemento X en un montículo de
n elementos, se elimina el elemento de clave
mínima o máxima, es decir el elemento de la
raíz.
•Se debe
garantizar la propiedad de
ordenamiento
2
2 8 3 10
2 16 7 18 13 15
8
10
13
3
16
15
7
18
Eliminando un
elemento del
montículo
Montículos binarios
Reordenando para
garantizar las propiedades
15
8
10
13
3
16
7
18
15
15 8 3 10
2 16 7 18 13
n=n-1
Montículos binarios
Reordenando para
garantizar las propiedades
15
8
10
3
16
7
18
13
15 8 3 10
2 16 7 18 13
Montículos binarios
Reordenando para
garantizar las propiedades
3
8
10
15
16
7
18
13
3 8 15 10
2 16 7 18 13
Montículos binarios
Reordenando para
garantizar las propiedades
3
8
10
7
16
15
18
13
3 8 7 10
2 16 15 18 13
Montículos binarios
Entonces:
• En la operación de inserción es
necesario realizar un subir (filtrado
ascendente) del nodo a insertar para
asegurar la propiedad de forma.
• En la operación de eliminación es
necesario realizar un hundir (filtrado
descendente)
del nodo pivote para
asegurar la propiedad de forma.
Montículos binarios
Ejercicio:
Creación de un montículo a partir de una
colección existente de datos.
• Solución 1:
Hacer n inserciones en un montículo
inicialmente vacío O(nlog n). Enfoque
de arriba hacia abajo.
• Solución 2:
Utilizar un enfoque de abajo hacia
arriba, O(n).
Detalle de la Solución 2: Utilizar un enfoque de abajo
hacia arriba, O(n).
Montículos binarios
Pasos:
• Almacenar arbitrariamente los n elementos en el
árbol.
19
2
18
16
13
15
3
7
8
19 2 13 18
2 15 3 7 16 8
Montículos binarios
Pasos:
• Con el nodo [n/2]
procesando en orden
decreciente hasta el nodo 1, montificar el
subárbol con raíz en cada nodo por medio de un
hundir.
1
19
2
2
4
18
16
3
13
15
8
3
7
[n/2] =[9/2]=4
19 2 13 18
2 15 3 7 16 8
Pasos:
Montículos binarios
• Procesando en orden decreciente el nodo n-1,
montificar el subárbol con raíz en cada nodo por
medio de un hundir.
1
19
2
3
2
8
16
13
15
3
7
18
19 2 13 28 15 3 7 16 18
Montículos binarios
Pasos:
• Procesando en orden decreciente el nodo n-2,
montificar el subárbol con raíz en cada nodo por
medio de un hundir.
1
19
2
2
8
16
3
15
13
7
18
19 2 3 28 15 13 7 16 18
Montículos binarios
Pasos:
• Procesando en orden decreciente el nodo n-3,
montificar el subárbol con raíz en cada nodo por
medio de un hundir.
1
19
2
8
16
3
15
13
7
18
19 2 3 28 15 13 7 16 18
Montículos binarios
Pasos:
• Procesando en orden decreciente por el medio
de hundir para garantizar la propiedad del
montículo.
2
19
8
16
3
15
13
7
18
2 19 3 28 15 13 7 16 18
Montículos binarios
Pasos:
• Procesando en orden decreciente por el medio
de hundir para garantizar la propiedad del
montículo.
2
8
19
16
3
15
13
7
18
2 8 3 19
2 15 13 7 16 18
Montículos binarios
Resultado final
2
8
16
19
3
15
13
7
18
2 8 3 16
2 15 13 7 19 18
Montículos - d
Montículos parecidos a los binarios,
excepto que todos los nodos tienen d
hijos.
1
5
62
61
4
317
21
10
3
4 10
7
14
13
13
15
12
16
19
8
18
17
16
9
Montículos - d
Características
•Más bajos que los montículos binarios
altura logd n.
•Mejora la operación de insertar
•EliminarMin es más costosa O(d logd n)
•Se pueden implantar en arreglos
•Bueno cuando hay muchas inserciones
y pocas eliminaciones
•Bueno cuando el tamaño del montículo
es muy grande.
Problema:
Montículos - d
La operación de combinar dos montículos en
uno (fusionar) no tiene un soporte eficiente
Estructuras para fusionar eficientemente.
• Montículos a
la izquierda: es un árbol
binario. Se diferencia del montículo binario
porque el montículo a la izquierda no está
perfectamente equilibrado (intenta ser muy
desequilibrado).
Montículos binarios a la izquierda
Longitud del camino nulo (lcn)
Longitud del camino nulo lcn(x): es la
longitud del camino más corto entre x y un
nodo hoja.
• Longitud del camino nulo de un nodo hoja con un
hijo es 0.
• lcn(nulo) = -1 (longitud del camino nulo es -1)
1
1
0
0
0
0
Montículos binarios a la izquierda
Propiedad del montículo a la
izquierda
1. La lcn del hijo izquierdo es al menos tan grande
como la del hijo derecho
2. El árbol se desvía con mayor profundidad al lado
izquierdo.
Un montículo a la izquierda posee dos propiedades:
•Propiedad estructural basada en la longitud del
camino nulo
•Propiedad de orden (como el montículo binario)
Montículos binarios a la izquierda
Montículo a la izquierda
No
1
1
1
0
0
0
1
0
0
No cumple propiedad 1
0
1
0
0
lcn de cualquier nodo es 1 más que la mínima
longitud del camino nulo de sus hijos
Montículos binarios a la izquierda
Teorema:
 Un árbol a la izquierda con d nodos en el
camino derecho debe tener al menos 2d - 1
nodos
 Un árbol a la izquierda de n nodos tiene un
camino derecho con a lo más log(n+1)
nodos
 La idea es trabajarlo por el lado derecho
que es más corto.
Montículos binarios a la izquierda
Ejemplo para fusionar dos montículos a la izquierda
(P1, P2)
3
6
10
8
21
14
23
P1
17
26
12
7
18
24
33
P2
37
18
Montículos binarios a la izquierda
Ejemplo para fusionar dos montículos a la izquierda
(P1, P2)
3
6
10
12
8
21
14
23
P1
17
26
7
18
24
33
P2
37
18
Montículos binarios a la izquierda
Ejemplo para fusionar dos montículos a la izquierda
(P1, P2)
3
6
10
12
8
7
21
14
17
18
24
37
23
P1
26
33
P2
18
Montículos binarios a la izquierda
Ejemplo para fusionar dos montículos a la izquierda
(P1, P2)
3
6
10
12
8
7
21
14
17
18
24
37
23
P1
26
33
18
P2
Montículos binarios a la izquierda
Ejemplo para fusionar dos montículos a la izquierda
(P1, P2)
3
6
10
12
8
7
NULO
21
14
17
18
24
37
23
P1
26
33
18
P2
Montículos binarios a la izquierda
Ejemplo para fusionar dos montículos a la izquierda
(P1, P2)
3
6
LCN?
10
12
8
7
21
14
17
18
18
24
37
23
26
33
Montículos binarios a la izquierda
Ejemplo para fusionar dos montículos a la izquierda
(P1, P2)
LCN?
6
3
7
12
10
8
37
21
14
18
24
17
23
33
26
18
Montículos binarios a la izquierda
Ejemplo para fusionar dos montículos a la izquierda
(P1, P2)
LCN?
6
3
7
12
10
37
8
21
14
18
24
17
23
33
26
18
Montículos binarios a la izquierda
Ejemplo para fusionar dos montículos a la izquierda
(P1, P2)
LCN?
6
3
12
10
21
14
23
7
18
37
8
24
33
17
26
18
Montículos binarios a la izquierda
Ejemplo para fusionar dos montículos a la izquierda
(P1, P2)
3
LCN?
6
10
12
21
7
14
18
37
8
24
23
33
17
26
18
Montículos binarios a la izquierda
Ejemplo para fusionar dos montículos a la izquierda
(P1, P2)
3
10
6
12
7
21
18
37
8
24
33
17
26
18
14
23
Montículos binarios a la izquierda
Insertar un nodo
M1
M2
6
3
10
21
8
14
23
17
26
Montículos binarios a la izquierda
Insertar un nodo
M1
M2
6
3
10
21
8
14
23
17
26
Nulo
Montículos binarios a la izquierda
Insertar un nodo
M1
M2
6
3
8
10
21
17
14
23
26
Montículos binarios a la izquierda
Insertar un nodo
M1
M2
6
3
8
10
21
17
14
23
26
Montículos binarios a la izquierda
Resultado de Insertar un nodo
M1
3
6
10
8
21
14
17
23
26
Montículos binarios a la izquierda
EliminarMin()
M1
3
10
21
23
8
14
17
26
Montículos binarios a la izquierda
EliminarMin()
M1
M2
10
21
23
8
14
17
26
Montículos binarios a la izquierda
EliminarMin()
M1
M2
10
21
23
8
14
17
26
Montículos binarios a la izquierda
EliminarMin()
M1
M2
8
10
21
17
14
23
26
NULO
Montículos binarios a la izquierda
EliminarMin()
M1
8
17
10
26
21
14
23
Tópicos I
Unidad I
Árboles, montículos y grafos
Semana 3
Cola de prioridades, montículos