Cola de prioridades (estructura de datos)


Cola de prioridades (estructura de datos)

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.

Contenido

Características generales

Este tipo especial de colas tienen las mismas operaciones que las colas , pero con la condición de que los elementos se atienden en orden de prioridad.

Ejemplos de la vida diaria serían la sala de urgencias de un hospital, ya que los enfermos se van atendiendo en función de la gravedad de su enfermedad.

Entendiendo la prioridad como un valor numérico y asignando a altas prioridades valores pequeños, las colas de prioridad nos permiten añadir elementos en cualquier orden y recuperarlos de menor a mayor.

Implementación

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.

Tipos

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

Operaciones

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.
  • Destruye: elimina la cola de memoria.

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:

***( Vamos a manejar explicitamente las prioridades dentro de la cola, por lo que precisamos
que el tipo base proporcione operaciones para acceder a la prioridad, y para compararlas.

Se asume que p1 > p2, donde p1 y p2 son prioridades, significa que p1 es preferente
frente a p2, esto es, un elemento con prioridad p1 es más prioritario que otro con prioridad p2.
)

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

Posible instanciación

***( Usamos pares de naturales, en la que el primer valor
es un dato, y el segundo su prioridad. Suponemos que un valor natural más pequeño
indica mayor prioridad.
)

fmod PAR-NAT is
        protecting NAT .
        sort ParNat .
        
        op <_:_> : Nat Nat -> ParNat .
        op info : ParNat -> Nat .
        op clave : ParNat -> Nat .
        
        vars E C : Nat .
        vars P1 P2 : ParNat .
        
        eq info(< E : C >) = E .
        eq clave(< E : C >) = C .
endfm


*** Realizamos la vista correspondiente

view VParNat from ELEMENTO-PRIORIDAD to PAR-NAT is
        sort Elt to ParNat .
        sort Prioridad to Nat .
        op prioridad to clave .
        op _>_ to _<_ .
endv


*** Procedemos a la instanciación

fmod COLA-PAR-NAT is
        protecting COLA-PRIORIDAD{VParNat} .
endfm

Ejemplo Cola Prioridad en Maude

 COLA-MEDIEVAL es un ejemplo de colas de prioridad en la que los elemento de la cola son
plebeyos y nobles, en la cual la prioridad la tienen los nobles.
 fth MEDIEVAL is
        sort Elt .
        op esNoble?: Elt --> Bool .
 endfth

 fmod COLA-MEDIEVAL {x::MEDIEVAL} is
        protecting NAT, BOOL .
        sort colaM{x} .
        subsort colaMNV{x} < colaM{x} .
        
        op crear: --> colaM{x} [ctor] .
        op insertar: x$Elt colaM{x} --> colaMNV{x} [ctor] .

        op extraer: colaM{x} --> colaM{x} .
        op frente: colaMNV{x} --> x$Elt .
        op NNobles: colaM{x} --> Nat .
        op NPlebleyos: colaM{x} --> Nat .

        var C: colaMNV{x} .
        var E: x$Elt .

        eq extraer(crear) = crear .
        eq extraer(insertar(E,crear)) = crear .
        eq extraer(insertar(E,C)) = if NOT(esNoble?(frente(c))) AND esNoble?(E) then
                                        c
                                    else
                                        insertar(E,extraer(c))
                                    fi .
        
        eq frente(insertar(E,crear)) = E .
        eq frente(insertar(E,C)) = if (esNoble?(E)) AND (esNoble?(frente(C))) then
                                        E
                                   else
                                        frente(C)
                                   fi .

        eq NNobles(crear) = 0 .
        eq NNobles(insertar(E,C)) = if esNobles?(E) then
                                        1 + NNobles(C)
                                    else
                                        NNobles(C)
                                    fi .

        
        eq NPlebleyos(crear) = 0 .
        eq NPlebleyos(insertar(E,C)) = if NOT(esNobles?(E)) then
                                        1 + NPlebeyos(C)
                                    else
                                        NPlebeyos(C)
                                    fi .
 endfm

Implementación en Java

Partimos a partir de la implementación en Java utilizando clases.

package colaPrioridadSimpleEnlazada;
import colaException.*;
 
public class ColaPrioridad implements colaPrioridadInterface.ColaPrioridad {
    class Celda {
        Object elemento;
        int prioridad;
        Celda sig;
    }
    private Celda cola;
    public ColaPrioridad() {
        cola = new Celda();
        cola.sig = null;
    }
    public boolean vacia() {
        return (cola.sig==null);
    } 
    public Object primero() throws ColaVaciaException {
        if (vacia()) throw new ColaVaciaException();
        return cola.sig.elemento;
    }
    public int primero_prioridad() throws ColaVaciaException {
        if (vacia()) throw new ColaVaciaException();
        return cola.sig.prioridad;
    }      
    public void inserta(Object elemento, int prioridad) {
        Celda p,q;
        boolean encontrado = false;
        p = cola;
        while((p.sig!=null)&&(!encontrado)) {
            if (p.sig.prioridad<prioridad) 
                encontrado = true;
            else p = p.sig;
        }
        q = p.sig;
        p.sig = new Celda();
        p = p.sig;
        p.elemento = elemento;
        p.prioridad = prioridad;
        p.sig = q;
    }     
        public void suprime() throws ColaVaciaException {
        if (vacia()) throw new ColaVaciaException();
        cola = cola.sig;
    }
} // fin clase ColaPrioridad

Véase también

  • Cola
  • Colas circulares (anillos)
  • Bicolas

Enlaces externos


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Cola (informática) — Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés …   Wikipedia Español

  • Cola doblemente terminada — Una cola doblemente terminada o deque (del inglés double ended queue) es una estructura de datos lineal que permite insertar y eliminar elementos por ambos extremos, podría verse como un mecanismo que permite aunar en una única estructura las… …   Wikipedia Español

  • ADEOS — Saltar a navegación, búsqueda Para otros usos de este término, véase Advanced Earth Observation Satellite. ADEOS (siglas de Adaptative Domain Environment Operating Systems), ADEOS proporciona un entorno flexible para compartir los recursos… …   Wikipedia Español

  • Adaptive Domain Environment Operating Systems — Para otros usos de este término, véase Advanced Earth Observation Satellite. ADEOS (siglas de Adaptive Domain Environment Operating Systems), ADEOS proporciona un entorno flexible para compartir los recursos hardware para múltiples sistemas… …   Wikipedia Español

  • Sistema operativo de tiempo real — Se ha sugerido que Sistema de tiempo real sea fusionado en este artículo o sección (discusión). Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí. Un sistema operativo de tiempo real (SOTR o RTOS Real Time… …   Wikipedia Español

  • Wikipedia:Café (todos) — Atajos WP:CWP:C …   Wikipedia Español

  • Vuelo 800 de TWA — Para el accidente de un Boeing 707 de TWA en Roma, Italia., véase Vuelo 800 de TWA (1964). Vuelo 800 de TWA Fecha 18 de julio de 1996 Hora 00:31 horas UTC Causa Explosión durante el vuelo Lugar …   Wikipedia Español

  • Bioma — Saltar a navegación, búsqueda Reparto geográfico de diferentes biomas Bosques caducifolios Bosques de coniferas Otros …   Wikipedia Español

  • Sistema operativo — No debe confundirse con Sistemas operados. Interacción entre el SO con el resto de las partes …   Wikipedia Español

  • Command (patrón de diseño) — En programación orientada a objetos, Command es un patrón de diseño. Contenido 1 Intención 2 Propósito 3 Motivo 4 Aplicaciones …   Wikipedia Español