tópicos i unidad i cola de prioridades, montículos semana 3 Árboles, montículos y grafos

Tópicos I

Unidad I

Cola de prioridades, montículos

Semana 3

Árboles, montículos y grafos

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.

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.

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.

Introducción

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

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

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.

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

• 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

Propiedades estructurales 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

Propiedades de orden de los montículos

Ejemplo de montículos de máximos

15

13 12

8 9 5 8

7 5 3 4 5

15 13 12 8 9 5 8 7 5 3 4 5

1 2 3 4 5 6 7 8 9 10 11 12

1

2 3

4 5 6 7

8 9 1011

12

Ubicación en el vector de un elemento

15 13 12 8 9 5 8 7 5 3 4 5

1 2 3 4 5 6 7 8 9 10 11 12

15

13 12

8 9 5 8

7 5 3 4 5

1

2 3

4 5 6 7

8 9 1011

12

i=3i/2=1 2*i=2*3=6 2*i+1=2*3+1=7

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.

Mantenimiento de montículosLa 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.

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

8 3

10 16 7 18

13 15

2 8 3 210 16 7 18 13 15

4

4

Ejemplo de montículos de mínimos

2

8 3

10 4 7 18

13 15

2 8 3 210 4 7 18 13 15

16

16

Reordenando para garantizar las propiedades

4 3

10 8 7 18

13 15

2 4 3 210 8 7 18 13 15

16

16

2

Reordenando para garantizar las propiedades

4 3

10 8 7 18

13 15

2 4 3 210 8 7 18 13 15

16

16

2

Resultado final

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

8 3

10 16 7 18

13 15

2 8 3 210 16 7 18 13 15

Eliminando un elemento del montículo

15

8 3

10 16 7 18

13 15

15 8 3 210 16 7 18 13 n=n-1

Reordenando para garantizar las propiedades

15

8 3

10 16 7 18

13

15 8 3 210 16 7 18 13

Reordenando para garantizar las propiedades

3

8 15

10 16 7 18

13

3 8 15 210 16 7 18 13

Reordenando para garantizar las propiedades

3

8 7

10 16 15 18

13

3 8 7 210 16 15 18 13

Reordenando para garantizar las propiedades

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.

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).

Pasos:

• Almacenar arbitrariamente los n elementos en el árbol.

19

2 13

18 15 3 7

16

19 2 13 218 15 3 7 16

8

8

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.

16

19

2 13

18 15 3 7

19 2 13 218 15 3 7 16

8

8

4

32

1

[n/2] =[9/2]=4

16

19

2 13

8 15 3 7

19 2 13 28 15 3 7 16

18

18

32

1

Pasos:

• Procesando en orden decreciente el nodo n-1, montificar el subárbol con raíz en cada nodo por medio de un hundir.

16

19

2 3

8 15 13 7

19 2 3 28 15 13 7 16

18

18

2

1

Pasos:

• Procesando en orden decreciente el nodo n-2, montificar el subárbol con raíz en cada nodo por medio de un hundir.

16

19

2 3

8 15 13 7

19 2 3 28 15 13 7 16

18

18

1

Pasos:

• Procesando en orden decreciente el nodo n-3, montificar el subárbol con raíz en cada nodo por medio de un hundir.

16

2

19 3

8 15 13 7

2 19 3 28 15 13 7 16

18

18

Pasos:

• Procesando en orden decreciente por el medio de hundir para garantizar la propiedad del montículo.

16

2

19

38

15 13 7

2 8 3 219 15 13 7 16

18

18

Pasos:

• Procesando en orden decreciente por el medio de hundir para garantizar la propiedad del montículo.

16

2

19

38

15 13 7

2 8 3 216 15 13 7 19

18

18

Resultado final

1

2 3 4

4 7 10 13 15 16 8 17 9

6 7 10

61 31 21 14 13 12 19 18 16

5

Montículos parecidos a los binarios, excepto que todos los nodos tienen d hijos.

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:

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).

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

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.

Montí

culo

s b

inari

os

a la izq

uie

rda

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)

1

1 0

0 0

0

1

1 0

0 1

0 0

Montículo a la izquierda No

lcn de cualquier nodo es 1 más que la mínima longitud del camino nulo de sus hijosM

ontí

culo

s b

inari

os

a la izq

uie

rda

No cumple propiedad 1

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í

culo

s b

inari

os

a la izq

uie

rda

6

12 7

18 24

33

3

10 8

21 14

23

17

26

37 18

Ejemplo para fusionar dos montículos a la izquierda (P1, P2)

P1 P2

Montí

culo

s b

inari

os

a la izq

uie

rda

6

12

18 24

33

3

10

21 14

23

7

37 18

8

17

26

P1 P2

Montí

culo

s b

inari

os

a la izq

uie

rda

Ejemplo para fusionar dos montículos a la izquierda (P1, P2)

6

12

18 24

33

3

10

21 14

23

7

37 18

8

17

26

P1 P2

Montí

culo

s b

inari

os

a la izq

uie

rda

Ejemplo para fusionar dos montículos a la izquierda (P1, P2)

6

12

18 24

33

3

10

21 14

23

7

37

18

8

17

26

P1 P2

Montí

culo

s b

inari

os

a la izq

uie

rda

Ejemplo para fusionar dos montículos a la izquierda (P1, P2)

6

12

18 24

33

3

10

21 14

23

7

37

18

8

17

26

P1 P2

NULO

Montí

culo

s b

inari

os

a la izq

uie

rda

Ejemplo para fusionar dos montículos a la izquierda (P1, P2)

6

12

18 24

33

3

10

21 14

23

7

37

18

8

17

26

LCN?

Montí

culo

s b

inari

os

a la izq

uie

rda

Ejemplo para fusionar dos montículos a la izquierda (P1, P2)

6

12

18 24

33

3

10

21 14

23

7

37

18

8

17

26

LCN?

Montí

culo

s b

inari

os

a la izq

uie

rda

Ejemplo para fusionar dos montículos a la izquierda (P1, P2)

6

12

18 24

33

3

10

21 14

23

7

378

1817

26

LCN?

Montí

culo

s b

inari

os

a la izq

uie

rda

Ejemplo para fusionar dos montículos a la izquierda (P1, P2)

6

12

18 24

33

3

10

21 14

23

7

378

LCN?

1817

26

Montí

culo

s b

inari

os

a la izq

uie

rda

Ejemplo para fusionar dos montículos a la izquierda (P1, P2)

6

12

18 24

33

3

10

21 14

23

7

378

LCN?

1817

26

Montí

culo

s b

inari

os

a la izq

uie

rda

Ejemplo para fusionar dos montículos a la izquierda (P1, P2)

3

10

21 14

23

6

12

18 24

33

7

378

1817

26

Montí

culo

s b

inari

os

a la izq

uie

rda Ejemplo para fusionar dos montículos a la izquierda

(P1, P2)

Insertar un nodo

6

M1M2

3

10 8

21 14

23

17

26

Montí

culo

s b

inari

os

a la izq

uie

rda

6

M1 M2

3

10 8

21 14

23

17

26

Nulo

Montí

culo

s b

inari

os

a la izq

uie

rda

Insertar un nodo

6

M1 M2

3

10 8

21 14

23

17

26

Montí

culo

s b

inari

os

a la izq

uie

rda

Insertar un nodo

6

M1 M2

3

10 8

21 14

23

17

26

Montí

culo

s b

inari

os

a la izq

uie

rda

Insertar un nodo

6

M13

10

821 14

23 17

26

Montí

culo

s b

inari

os

a la izq

uie

rda

Resultado de Insertar un nodo

M1

3

10 8

21 14

23

17

26

EliminarMin()M

ontí

culo

s b

inari

os

a la izq

uie

rda

M1

10 8

21 14

23

17

26

M2

Montí

culo

s b

inari

os

a la izq

uie

rda

EliminarMin()

M1

10 8

21 14

23

17

26

M2

Montí

culo

s b

inari

os

a la izq

uie

rda

EliminarMin()

M1

10 8

21 14

23

17

26

M2

NULO

Montí

culo

s b

inari

os

a la izq

uie

rda

EliminarMin()

M1

10

8

21 14

23

17

26

Montí

culo

s b

inari

os

a la izq

uie

rda

EliminarMin()

Tópicos I

Unidad I

Semana 3

Cola de prioridades, montículos

Árboles, montículos y grafos