Cola de prioridades (estructura de datos)

De Wikipedia, la enciclopedia libre

Este artículo o sección sobre informática necesita ser wikificado con un formato adecuado a las convenciones de estilo de Wikipedia. Por favor, edítalo para cumplir con ellas. No elimines este aviso hasta que lo hayas hecho. ¡Colabora wikificando!

Una cola de prioridades es una estructura de datos en la que los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen. Hay 2 formas de implementación:

1. Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.
2. Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.

Tabla de contenidos 1 Tipos de colas de prioridades 2 Operaciones básicas 3 Implementación en Maude 4 Véase también

[editar] Tipos de colas de prioridades

• Colas de prioridades con ordenamiento ascendente: En ellas los elementos se insertan de forma arbitraria, pero a la hora de extraerlos, se extrae el elemento de menor prioridad.

• Colas de prioridades con ordenamiento descendente: Son iguales que la colas de prioridad con ordenamiento ascendente, pero al extraer el elemento se extrae el de mayor prioridad.

[editar] Operaciones básicas

Las operaciones de las colas de prioridad son las mismas que las de las colas genéricas:

• Crear: se crea la cola vacía.
• Encolar: se añade un elemento a la cola, con su correspondiente prioridad.
• Desencolar: se elimina el elemento frontal de la cola.
• Frente: se devuelve el elemento frontal de la cola.

[editar] Implementación en Maude

Para la implementación de las colas de prioridad el elemento a insertar tiene que ser de un tipo que soporte un orden total y eso lo conseguimos creando una teoría, que será la siguiente:

fth ELEMENTO-PRIORIDAD is

 protecting BOOL .
 sorts Elt Prioridad .  

• operaciones

op prioridad : Elt -> Prioridad .
op _>_ : Prioridad Prioridad -> Bool.

endfth

Una vez que tenemos la teoría procedemos a la implementación de la cola de prioridad:

fmod COLA-PRIORIDAD {X :: ELEMENTO-PRIORIDAD} is

sorts Cola PrioNV{X} ColaPrio{X} .
subsort Cola PrioNV{X} < ColaPrio{X} .

• operaciones

op crear : -> Cola PrioNV{X} .
op encolar : X$Elt Cola Prio{X} -> Cola PrioNV{X} [ctor] .

• constructores

op desencolar : Cola Prio{X} -> Cola {X} .

• selectores

op frente : Cola PrioNV{X} -> X$Elt .

• variables

var C : Cola PrioNV{X} .
var E : X$Elt .

• ecuaciones

eq desencolar(crear) = crear .
eq desencolar(encolar(E,crear)) = crear .
eq desencolar(encolar(E,C)) = 
      if prioridad(E) > prioridad(frente(C)) then
         C
      else
         encolar(E,desencolar(C))
      fi .
eq frente(encolar(E,crear)) = E .
eq frente(encolar(E,C)) =
      if prioridad(E) > prioridad(frente(C)) then
         E
      else
         frente(C)
      fi .
endfm

[editar] Véase también

• Estructura de datos
• Cola