7/21/2019 03 IA Monticulo Binario

1/12

Montculo Binario

1

7/21/2019 03 IA Monticulo Binario

2/12

COLAS DE PRIORIDADCaractersticas:

Se puede aadir elementos en cualquier orden

Los elementos se recuperan en orden creciente En la cola de espera el valor del elemento establece su

prioridad (valor mnimo = mxima prioridad).

Pueden ser colas de prioridad de mnimos o mximos

Las operaciones soportadas: es vaca, aadir, eliminar

Permiten el accesoal mnimo o mximo elemento

Insertar, eliminar(mnimo o mximo)

2

7/21/2019 03 IA Monticulo Binario

3/12

MONTICULO BINARIO Un montculo binario es un rbol binario completo:

todos los niveles estn llenos, con la excepcin delnivel ms bajo que se lleva de izquierda a derecha.

Un rbol binario completo de altura h tiene ente 2hy2h+1-1 nodos

Esta caracterstica facilita su implementacin con un

vector Para cualquier elemento de la posicin k del vector, el

hijo izquierdo esta en la posicin2k, y el hijo derechoen2k+1, y el padre en k 2.

3

7/21/2019 03 IA Monticulo Binario

4/12

MONTICULO BINARIO Un rbol binario se dice parcialmente ordenado si

verifica las siguientes condiciones:

El elemento raz es menor o igual (o mayor o igual) queel resto de los elementos del rbol

Los hijos izquierdo y derecho son rboles binariosparcialmente ordenados

4

7/21/2019 03 IA Monticulo Binario

5/12

MONTICULO BINARIO

5

7/21/2019 03 IA Monticulo Binario

6/12

RepresentacinMontculo = (V, C)

V: Vector que almacena los elementos del montculo

C: Cantidad de elementos del montculo

6

7/21/2019 03 IA Monticulo Binario

7/12

Operaciones en montculo binario Es_vacia

Aadir

Eliminar

7/21/2019 03 IA Monticulo Binario

8/12

Operacin Insertar

8

Nombre operacin: Insertar

Descripcin operacional:

Insertar: Elemento x Montculo_BinarioMontculo_BinarioExplicacin de la operacin:

Inserta un nuevo elemento al montculo binario.

Modelo:Si Cantidad(A) = Tamao_Mximo(A)Entonces

Error, Montculo LlenoSino

Insertar (e, A) = Cantidad(A) Cantidad(A) + 1

Vector(A)Cantidade

Flotar(A)

Fin Si

7/21/2019 03 IA Monticulo Binario

9/12

Operacin Eliminar

9

Nombre operacin: Eliminar

Descripcin operacional:

Eliminar: Montculo_Binario Montculo_BinarioExplicacin de la operacin:

Elimina el elemento de la raz.

Modelo:Vector(A)0Vector[A]Cantidad

Cantidad Cantidad -1Eliminar( A) =

Si (Cantidad > 0)

Hundir(A)

7/21/2019 03 IA Monticulo Binario

10/12

Aadir a un montculo: 10, 20, 30, 15, 50, 12, 40, 7, 18, 45, 1

10

7/21/2019 03 IA Monticulo Binario

11/12

Eliminar del montculo de la figura 2 elementos, Grafique el

rbol resultante

11

7/21/2019 03 IA Monticulo Binario

12/12

TAREA Utilice le montculo binario para implementar una

aplicacin de colas de prioridad de una entidadbancaria, donde los existen las prioridades: 1: Aperturade una nueva cuenta bancaria; 2: Depsito; 3: Retiro dedinero; 4: Transferencia bancaria; y 5: Otrastransacciones. Cada cliente al llegar al banco indica laoperacin que realizar a un agente inteligente y este le

proporciona un ticket que contiene el nmero deorden en el que ser atendido.

12