[2021] Cola de prioridad | Oración 1 (introducción) {DH}


La cola de prioridad es una extensión de la cola con las siguientes propiedades.

  1. Se asigna una prioridad a cada elemento.
  2. Un elemento de alta prioridad se elimina de la cola antes que un elemento de baja prioridad.
  3. Si dos artículos tienen la misma prioridad, se entregarán en orden en la cola.

En la siguiente cola de prioridad, el elemento con el valor ASCII más alto tiene la prioridad más alta.
Prioridad de cola mínima

Una cola de prioridad típica admite las siguientes operaciones.
insertar (elemento, prioridad): Inserte un elemento con una prioridad específica.
getHighestPriority (): Devuelve el artículo con la mayor prioridad.
deleteHighestPriority (): Elimina el elemento con mayor prioridad.

¿Cómo se implementa la cola de prioridad?
Usar matriz: Una implementación simple es usar una matriz de la siguiente estructura.


struct item {
   int item;
   int priority;
}

La operación insert () se puede implementar agregando un elemento al final de la matriz en el tiempo O (1).

La operación getHighestPriority () se puede implementar buscando linealmente el elemento con la prioridad más alta en la matriz. Este proceso lleva O (n) tiempo.

La operación deleteHighestPriority () se puede implementar buscando primero un elemento linealmente y luego quitando el elemento quitando todo …


Seguir Leyendo:
[2021] Cola de prioridad | Oración 1 (introducción) {DH}

Publicaciones Similares

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *