Menú

Estructura de datos de cola de prioridad en C ++ con ilustración

  • Principal
  • Otro
  • Estructura de datos de cola de prioridad en C ++ con ilustración

priority queue data structure c with illustration

Pruebe Nuestro Instrumento Para Eliminar Los Problemas

Introducción a la cola de prioridad en C ++ con ilustración.

Priority Queue es una extensión de la cola que discutimos en nuestro último tutorial.

Es similar a la cola en ciertos aspectos y, sin embargo, se diferencia de la cola ordinaria en los siguientes puntos:

  • Cada elemento de la cola de prioridad está asociado con una prioridad.
  • El elemento con la prioridad más alta es el primer elemento que se elimina de la cola.
  • Si más de un elemento tiene la misma prioridad, se considera su orden en la cola.

=> Haga clic aquí para ver la serie de capacitación Absolute C ++.

Cola de prioridad en C ++

Podemos visualizar la cola de prioridad como una versión modificada de la cola, excepto que cuando el elemento se va a sacar de la cola, el elemento con la prioridad más alta se recupera primero. Por lo tanto, preferimos utilizar las colas de prioridad en lugar de las colas cuando necesitamos procesar los elementos en función de la prioridad.

Lo que vas a aprender:

Operaciones básicas

Analicemos algunas de las operaciones básicas que admite la cola de prioridad.

  • Insertar (elemento, prioridad): Inserta un elemento en la cola de prioridad con una prioridad determinada.
  • getHighestPriority (): Devuelve un artículo con la máxima prioridad.
  • deleteHighestPriority (): Elimina un elemento con la mayor prioridad.

Aparte de las operaciones anteriores, también podemos usar las operaciones de cola normales como isEmpty (), isFull () y peek ().

Ilustración

Veamos una ilustración de la cola de prioridad. Para simplificar, usaremos caracteres ASCII como elementos en la cola de prioridad. Cuanto mayor sea el valor ASCII, mayor será la prioridad.

Estado inicial - Cola de prioridad (PQ) - {} => vacío

ilustración de la cola de prioridad

En la ilustración anterior, vemos que la operación de inserción es similar a una cola normal. Pero cuando llamamos a 'deleteHighestPriority' para la cola de prioridad, el elemento con la prioridad más alta se elimina primero.

Por lo tanto, la primera vez que llamamos a esta función, se elimina el elemento O, mientras que la segunda vez, se elimina el elemento M, ya que tiene mayor prioridad que G y A.

Implementación de colas de prioridad en C ++

Las colas de prioridad se pueden implementar usando:

# 1) Matrices / Listas vinculadas

Podemos implementar las colas de prioridad usando arreglos y esta es la implementación más simple para las colas de prioridad.

Para representar los elementos en la cola de prioridad, podemos simplemente declarar una estructura como se muestra a continuación:

|_+_|

También hemos declarado la prioridad para cada artículo.

Para insertar un nuevo elemento en la cola de prioridad, simplemente tenemos que insertar el elemento al final de la matriz.

Para obtener el elemento de la cola usando getHighestPriority (), necesitamos recorrer la matriz desde el principio y devolver el elemento con la mayor prioridad.

De manera similar, para eliminar el elemento de la cola mediante la operación deleteHighestPriority, necesitamos recorrer toda la matriz y eliminar el elemento con la mayor prioridad. Luego, mueva todos los demás elementos después del elemento eliminado, una posición hacia atrás.

También podemos implementar la cola de prioridad usando una lista vinculada. Podemos realizar todas las operaciones de forma similar a las matrices. La única diferencia es que no necesitamos mover los elementos después de llamar a deleteHighestPriority.

# 2) Montones

El uso de montones para implementar una cola de prioridad es la forma más eficiente y proporciona un rendimiento mucho mejor en comparación con las listas y matrices vinculadas. A diferencia de la lista y la matriz vinculadas, la implementación del montón lleva un tiempo O (logn) para las operaciones de inserción y eliminación de la cola de prioridad. Obtener operación, getHighestPriority toma O (1) tiempo.

# 3) Cola de prioridad incorporada en la biblioteca de plantillas estándar (STL) en C ++

En C ++, tenemos una cola de prioridad como clase adaptable de contenedor, diseñada de tal manera que el elemento más alto es el primer elemento de la cola y todos los elementos están en orden decreciente.

Por tanto, cada elemento de la cola de prioridad tiene una prioridad fija.

Tenemos clase en STL, que contiene la implementación de la cola de prioridad.

Las diversas operaciones admitidas por la cola de prioridad son las siguientes:

  1. cola_prioridad :: tamaño (): Devuelve el tamaño de la cola.
  2. cola_prioridad :: vacía (): Comprueba si la cola está vacía y devuelve su estado.
  3. Priority_queue :: top (): Devuelve una referencia al elemento superior de la cola de prioridad.
  4. Priority_queue :: push (): Agrega un elemento al final de la cola de prioridad.
  5. cola_prioridad :: pop (): Elimina el primer elemento de la cola de prioridad.
  6. Priority_queue :: swap (): Se utiliza para intercambiar el contenido de una cola prioritaria por otra del mismo tipo y tamaño.
  7. tipo de valor de cola de prioridad: El tipo de valor proporciona el tipo de elemento almacenado dentro de una cola de prioridad. Esto también actúa como sinónimo del parámetro de plantilla.
  8. cola_prioridad :: emplace (): Se utiliza para insertar un nuevo elemento en el contenedor de cola de prioridad en la parte superior de la cola.

En el próximo programa, veremos la funcionalidad de la cola de prioridad en STL en C ++.

|_+_|

Producción:

java array eliminar elemento en el índice

Tamaño de la cola (pq.size ()): 5
Elemento superior de la cola (pq.top ()): 9
La cola de prioridad pq ​​es: 9 7 5 3 1
Cola de prioridad, después de la operación pq.pop (): 7 5 3 1

Implementación de Java para Priority Queue

La cola de prioridad en java es una cola especial en la que todos los elementos de la cola se ordenan de acuerdo con el orden natural o el orden personalizado utilizando un comparador proporcionado con la cola.

Una cola de prioridad en Java se ve como se muestra a continuación:

Implementación de Java para cola de prioridad

En la cola de prioridad de Java, los elementos se organizan de manera que el elemento menor esté al principio de la cola y el elemento más grande esté al final de la cola. Entonces, cuando eliminamos el elemento de la cola de prioridad, siempre es el elemento más pequeño el que se elimina.

La clase que implementa la cola de prioridad en Java es 'PriorityQueue' y es parte del marco de colecciones de Java. Implementa la interfaz 'Queue' de Java.

A continuación se muestra la jerarquía de clases para la clase Java PriorityQueue.

jerarquía de clases para la clase Java PriorityQueue

A continuación se muestra un ejemplo de la funcionalidad Priority Queue con números enteros como elementos en Java.

|_+_|

Producción:

peek () :: Valor de cabeza: 1
La cola de prioridad:
1 3 5 7
Después de la función poll (), cola de prioridad:
3 7 5
Después de la función Eliminar (5), cola de prioridad:
3 7
¿La cola de prioridad contiene 3 ?: verdadero
Elementos de matriz:
Valor: 3
Valor: 7

En el programa anterior, hacemos uso de la clase PriorityQueue de Java para crear un objeto de PriorityQueue que contiene un objeto Integer. Agregamos elementos a la cola usando la función 'agregar'. Luego, se llama a la función poll () y borra el elemento del frente de la cola que resulta ser el elemento menor.

Nuevamente llamamos a la función 'remove ()' que elimina el elemento especificado como parámetro de la cola. También usamos la función 'Contiene ()' para verificar si un elemento en particular está presente en la cola. Finalmente, convertimos la cola en un objeto de matriz usando la función 'toArray ()'.

Solicitud

  • Equilibrio de carga del sistema operativo y manejadores de interrupciones: Las funciones del sistema operativo, como el equilibrio de carga y el manejo de interrupciones, se implementan mediante colas de prioridad. La actividad de equilibrio de carga programa los recursos con la máxima prioridad para llevar a cabo nuestro equilibrio de carga de manera eficaz. El manejo de interrupciones se realiza atendiendo las interrupciones con la máxima prioridad. Esta funcionalidad se puede implementar de forma eficaz utilizando las colas de prioridad.
  • Enrutamiento: El enrutamiento es una función que se utiliza para enrutar los recursos de la red de modo que obtengamos el máximo rendimiento con el mínimo tiempo de respuesta. Esto también se puede implementar utilizando la cola de prioridad.
  • Emergencia hospitalaria: En la sala de emergencias de un hospital, los pacientes son atendidos según la gravedad del estado del paciente. Esto se puede simular utilizando colas de prioridad.
  • Algoritmo de ruta más corta de Dijkstra: Aquí, el gráfico se almacena como una lista de adyacencia y podemos usar una cola de prioridad para extraer el borde mínimo ponderado de manera eficiente de la lista de adyacencia para implementar el algoritmo de ruta más corta de Dijkstra.
  • La cola de prioridad también se puede utilizar para almacenar claves de nodo y extraer el nodo de clave mínimo mientras se implementa el árbol de expansión.

Conclusión

Las colas de prioridad no son más que la extensión de la cola. Pero a diferencia de las colas que agregan / eliminan elementos utilizando el enfoque FIFO, en la cola de prioridad los elementos se eliminan de la cola de acuerdo con la prioridad. Por tanto, cada elemento de la cola está asociado con una prioridad y el elemento con la prioridad más alta es el primero que se retira de la cola.

La cola de prioridad tiene tres operaciones principales, es decir, insert (), getHighestPriority () y deleteHighestPriority (). La cola de prioridad se puede implementar utilizando matrices o listas enlazadas, pero el trabajo no es muy eficiente. La cola de prioridad también se puede implementar usando montones y el rendimiento es mucho más rápido.

En C ++, también tenemos una clase de contenedor que implementa la funcionalidad de una cola de prioridad. En Java, hay una clase priority_queue incorporada que proporciona la funcionalidad de una cola de prioridad.

La cola de prioridad se utiliza principalmente en aplicaciones que requieren que los elementos se procesen de acuerdo con la prioridad. Por ejemplo, se utiliza en el manejo de interrupciones.

Nuestro próximo tutorial explorará todo sobre la cola circular, que es una extensión más de la cola.

=> Visite aquí para conocer el curso completo de C ++ de expertos.

Lectura recomendada

^