Priority Queue es una extensión de la estructura de datos Queue donde cada elemento tiene una prioridad particular asociada. Se basa en el valor de prioridad, los elementos de la cola se eliminan.
Operaciones en cola de prioridad:
- enqueue(): esta función se utiliza para insertar nuevos datos en la cola.
- dequeue(): esta función elimina el elemento con la prioridad más alta de la cola.
- peek()/top(): esta función se usa para obtener el elemento de mayor prioridad en la cola sin eliminarlo de la cola.
Enfoque: la idea es crear una estructura para almacenar el valor y la prioridad del elemento y luego crear una array de esa estructura para almacenar elementos. A continuación se detallan las funcionalidades que se van a implementar:
- enqueue(): Se utiliza para insertar el elemento al final de la cola.
- ojeada():
- Recorra la cola de prioridad y encuentre el elemento con la prioridad más alta y devuelva su índice.
- En el caso de múltiples elementos con la misma prioridad, busque el elemento con el valor más alto que tenga la prioridad más alta.
- sacar de la cola():
- Encuentre el índice con la prioridad más alta usando la función peek() . Llamemos a esa posición como ind , y luego cambie la posición de todos los elementos después de la posición ind una posición a la izquierda.
- Disminuya el tamaño en uno.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure for the elements in the
// priority queue
struct item {
int value;
int priority;
};
// Store the element of a priority queue
item pr[100000];
// Pointer to the last index
int size = -1;
// Function to insert a new element
// into priority queue
void enqueue(int value, int priority)
{
// Increase the size
size++;
// Insert the element
pr[size].value = value;
pr[size].priority = priority;
}
// Function to check the top element
int peek()
{
int highestPriority = INT_MIN;
int ind = -1;
// Check for the element with
// highest priority
for (int i = 0; i <= size; i++) {
// If priority is same choose
// the element with the
// highest value
if (highestPriority
== pr[i].priority
&& ind > -1
&& pr[ind].value
< pr[i].value) {
highestPriority = pr[i].priority;
ind = i;
}
else if (highestPriority
< pr[i].priority) {
highestPriority = pr[i].priority;
ind = i;
}
}
// Return position of the element
return ind;
}
// Function to remove the element with
// the highest priority
void dequeue()
{
// Find the position of the element
// with highest priority
int ind = peek();
// Shift the element one index before
// from the position of the element
// with highest priority is found
for (int i = ind; i < size; i++) {
pr[i] = pr[i + 1];
}
// Decrease the size of the
// priority queue by one
size--;
}
// Driver Code
int main()
{
// Function Call to insert elements
// as per the priority
enqueue(10, 2);
enqueue(14, 4);
enqueue(16, 4);
enqueue(12, 3);
// Stores the top element
// at the moment
int ind = peek();
cout << pr[ind].value << endl;
// Dequeue the top element
dequeue();
// Check the top element
ind = peek();
cout << pr[ind].value << endl;
// Dequeue the top element
dequeue();
// Check the top element
ind = peek();
cout << pr[ind].value << endl;
return 0;
}
Producción
16 14 12
Análisis de Complejidad:
- poner en cola(): O(1)
- mirar(): O (N)
- sacar de la cola: O(N)
Aplicación de cola de prioridad :
- Para los algoritmos de programación , la CPU debe procesar ciertas tareas que tienen prioridades. El proceso de tener mayor prioridad se ejecuta primero.
- En un sistema informático de tiempo compartido, el proceso de espera del tiempo de la CPU se carga en la cola de prioridad .
- Se utiliza una cola de prioridad de ordenación para ordenar montones .
Publicación traducida automáticamente
Artículo escrito por pradiptamukherjee y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA