Algoritmo de Ordenamento por Montículos

Vista previa del material en texto

[193]
Figura 10. Cola de prioridad con montículo
Pasemos a un ejemplo de uso del TDA montículo (como cola de prioridad) para la resolución de 
un problema en la figura 11. En este caso, se deben generar números aleatorios (del 0 al 100) junto 
con prioridades también generadas aleatoriamente (de 1 a 3) hasta completar el montículo y luego 
realizar la atención de todos los elementos de la cola de acuerdo a su orden de prioridad.
Figura 11. Ejemplo de uso del TDA Cola
Hagamos una breve descripción de las acciones realizadas para la resolución del ejercicio anterior, 
para comprender el uso del TDA montículo como cola de prioridad utilizando los eventos defini-
dos previamente.
[194]
Lo primero que hacemos es importar del TDA montículo las funciones que se utilizaremos, inclui-
do el módulo random para generar números aleatorios, luego hay que crear la variable de tipo heap 
para después generar los números y su prioridad de manera aleatoria y agregarlos a la cola. Final-
mente, realizamos la atención de todos los elementos de la cola mostrando sus valores.
Flotando y hundiendo los elementos mediante 
ordenamiento por montículo
Es un algoritmo cuyo funcionamiento es del tipo selección, creado por John William Joseph Wi-
lliams en 19641. Funciona siguiendo los principios de montículo, es decir que los elementos a orde-
nar siguen las propiedades de dicha estructura, luego para ordenar los elementos toma el mayor o 
menor (dependiendo si es un montículo de tipo máximo o mínimo), es decir el que está situado en 
la primera posición del vector y lo intercambia con el último elemento del vector. Luego reubica el 
elemento colocado en la primera posición hundiéndolo (para restablecer la propiedad de orden del 
montículo) y marca el último elemento como ordenado decrementando el tamaño del vector. Y se 
repite sucesivamente este proceso con el resto de los elementos del vector hasta que el tamaño del 
vector desordenado es uno. A continuación, en la figura 12 se puede observar el funcionamiento del 
algoritmo para ordenar un vector, nótese que inicialmente se debe llamar a la función montículizar 
para transformar el vector en un montículo.
Figura 12. Ejemplo de funcionamiento del algoritmo heapsort
1 Williams, J. W. J. (1964), "Algorithm 232 - Heapsort", Communications of the ACM, 7 (6): 347–348, 
doi:10.1145/512274.512284
[195]
Pasemos ahora a observar la implementación del algoritmo de ordenamiento por montículos en la fi-
gura 13. Nótese que es uno de los algoritmos de ordenamientos más sencillos que hemos vistos, dado 
que solo son cuatro líneas de código, esto es posible por la simplicidad del uso de los montículos.
Figura 13. Método de ordenamiento heapsort
Finalmente realicemos la comparación del algoritmo de ordenamiento por montículos respecto 
a los otros algoritmos de ordenamiento, utilizando los mismos aspectos que mencionamos en el 
capítulo IV.
Complejidad temporal O(n log n)
Complejidad espacial En el lugar
Estabilidad Inestable
Interno /Externo Interno
Recursivo/No recursivo No recursivo
Ordenamiento por comparación Comparativo
[196]
Guía de ejercicios prácticos
A continuación se plantean una serie de problemas, los cuales deberán resolver utilizando el 
TDA montículo.
1. Resolver el ejercicio 15 de la guía de ejercicios del capítulo VII, utilizando cola de prioridad.
2. Desarrollar un algoritmo que permita implementar cola de prioridad para administrar los tur-
nos de atención de la guardia de un hospital, con el siguiente criterio: consultas (1), emergen-
cias (2) y urgencias (3). Resuelva las siguientes actividades:
a. cargar 10 pacientes con diferentes prioridades;
b. realizar la atención de los pacientes, luego de atender cada paciente se pueden agregar 
nuevos a la cola;
c. antes de realizar todas las atenciones, cambiar la prioridad del turno que está en la posi-
ción i-ésima.
3. El general Hux es la persona encargada de administrar todas las operaciones de la base Starki-
ller, para lo cual nos solicita desarrollar un algoritmo que permita controlar las actividades que 
se realizan, contemplando lo siguiente:
a. debe contemplar distintas prioridades para el control de operaciones de acuerdo al siguien-
te criterio: pedidos de líder supremo Snoke y de Kylo Ren nivel tres, de capitán Phasma 
nivel dos y el resto de las operaciones nivel a cargo de los generales de la base de nivel uno;
b. de cada actividad se conoce quien es el encargado, una descripción, la hora y opcional-
mente la cantidad de Stormtroopers requeridos;
c. utilizar una cola de prioridad para administrar las distintas operaciones, debe cargar al 
menos ocho: dos de nivel tres, cuatro de nivel dos y cuatro de nivel uno;
d. opcionalmente se podrán agregar operaciones luego de atender una;
e. realizar la atención de las operaciones de la cola;
f. luego de atender la quinta operación, agregar una operación solicitada por capitán Phasma 
para revisión de intrusos en el hangar B7 que requiere 25 Stormstroopers;
g. luego de atender la sexta operación, agregar una operación solicitada por el líder supremo 
Snoke para destruir el planeta Takodana.
4. Resolver el ejercicio 4 de la guía de ejercicios del capítulo IV utilizando el método de ordena-
miento heapsort y comparar con los otros algoritmos probados en dicho capítulo.
[197]
5. El gran almirante Thrawn es el estratega del imperio galáctico para combatir contra los re-
beldes, el mismo normalmente se encuentra desbordado de pedidos de sugerencia de cómo 
actuar por los distintos generales, para lo cual nos solicita desarrollar un algoritmo que le per-
mita atender los pedidos de ayuda de acuerdo a la prioridad de los mismo en base a los siguien-
te requerimientos:
a. se deben contemplar tres niveles de prioridad para la cola;
b. cada pedido de sugerencia cuenta con la siguiente información: nombre del general solici-
tante, planeta en el que se encuentra o el más próximo y descripción del pedido;
c. aquellos pedidos que provengan del “Gran Inquisidor”, el planeta de Lothal o la descrip-
ción mencione a “Hera Syndulla” tendrán la mayor prioridad;
d. si el pedido es del “Agente Kallus” o la descripción menciona “Destructor Estelar” o vehí-
culos “AT-AT” tendrán prioridad media;
e. el resto de los pedidos serán de prioridad baja;
f. realizar la atención de la cola almacenando los pedidos de mayor prioridad en una pila 
llamada “bitácora” para revisión y seguimiento;
g. luego de cada atención se podrá agregar un pedido a la cola.
6. El comandante de la estrella de la muerte el gran Moff Tarkin debe administrar las asigna-
ciones de vehículos y Stromtroopers a las distintas misiones que parten desde la estrella de 
la muerte, para facilitar esta tarea nos encomienda desarrollar las funciones necesarias para 
gestionar esto mediante prioridades de la siguiente manera:
a. de cada misión se conoce su tipo (exploración, contención o ataque), planeta destino y 
general que la solicitó;
b. si la misión fue pedida por Palpatine o Darth Vader estas tendrán alta prioridad, sino su 
prioridad será baja;
c. si la misión es de prioridad alta los recursos se asignarán manualmente independiente-
mente de su tipo;
d. si la misión es de baja prioridad se asignarán los recursos de la siguiente manera depen-
diendo de su tipo:
I. exploración: 15 Scout Troopers y 2 speeder bike,
II. contención: 30 Stormtroopers y tres vehículos aleatorios (AT-AT, AT-RT, AT-TE, 
AT-DP, AT-ST) pueden ser repetidos,
III. ataque: 50 Stormtroopers y siete vehículos aleatorios (a los anteriores se le suman 
AT-M6, AT-MP, AT-DT),
[198]
e. realizar la atención de todas las misiones y mostrar los recursos asignados a cada una, per-
mitiendo agregar nuevos pedidos de misiones durante la atención;
f. indicar la cantidad total de recursos asignados a las misiones.