next up previous contents
Siguiente: Ejercicio de programación Subir: Colas Anterior: Estructura de las colas   Índice General

Colas con prioridad

Una cola con prioridad es una estructura de datos en la que se ordenan los datos almacenados de acuerdo a un criterio de prioridad. Hay dos tipos de colas de prioridad:

En las colas de prioridad ascendente se pueden insertar elementos en forma arbitraria y solamente se puede remover el elemento con menor prioridad. Si CPA es una cola de prioridad ascendente, la operación insert(CPA,x) inserta el elemento x en la cola CPA; y la operación x=minRemove(CPA) asigna a x el valor del elemento menor (de su prioridad) y lo remueve de la cola.

En las colas de prioridad descendente es similar, pero sólo permite la supresión del elemento más grande. Las operaciones aplicables a la cola de prioridad descendente son insert(CPD,x) y x=maxRemove(CPD), cuando CPD es una cola de prioridad descendente y x es un elemento.

La operación empty(C) se aplica a cualquier tipo de cola y determina si una cola de prioridad está vacía. Las operaciones de insertar y borrar se aplican solamente si la pila no está vacía.

Los elementos de la cola de prioridad no necesitan ser números o caracteres para que puedan compararse directamente. Pueden ser estructuras complejas ordenadas en uno o varios campos. Por ejemplo, las agendas telefónicas constan de apellidos, nombres, direcciones y números de teléfono y están ordenadas por apellido.

A diferencia de las pilas y las colas, en las colas de prioridad se pueden sacar los elementos que no están en el primer sitio del extremo donde salen los elementos. Esto es porque el elemento a retirar puede estar en cualquier parte del arreglo.

Cuando se requiere eliminar un dato de una cola de prioridad se necesita verificar cada uno de los elementos almacenados para saber cuál es el menor (o el mayor). Esto conlleva algunos problemas, el principal problema es que el tiempo necesario para eliminar un elemento puede crecer tanto como elementos tenga la cola.

Para resolver este problema hay varias soluciones:

  1. Se coloca una marca de ``vacío'' en la casilla de un elemento suprimido. Este enfoque realmente no es muy bueno, porque de cualquier modo se accesan los elementos para saber si es una localidad vacía o no lo es. Por otro lado, cuando se remueven elementos, se van creando lugares vacíos y después es necesario hacer una compactación, reubicando los elementos en el frente de la cola.

  2. Cada supresión puede compactar el arreglo, cambiando los elementos depués del elemento eliminado en una posición y después decrementando rear en 1. La inserción no cambia. En promedio, se cambian la mitad de los elementos de una cola de prioridad para cada supresión, por lo que esta operación no es eficiente.


next up previous contents
Siguiente: Ejercicio de programación Subir: Colas Anterior: Estructura de las colas   Índice General
Abdiel Caceres-Gonzalez Jun-02-2005