A cola de prioridad Es un tipo de cola que organiza elementos según sus valores de prioridad. Los elementos con valores de prioridad más altos normalmente se recuperan antes que los elementos con valores de prioridad más bajos.
En una cola de prioridad, cada elemento tiene un valor de prioridad asociado. Cuando agrega un elemento a la cola, se inserta en una posición según su valor de prioridad. Por ejemplo, si agrega un elemento con un valor de prioridad alto a una cola de prioridad, puede insertarse cerca del frente de la cola, mientras que un elemento con un valor de prioridad bajo puede insertarse cerca de la parte posterior.
Hay varias formas de implementar una cola de prioridad, incluido el uso de una matriz, una lista vinculada, un montón o un árbol de búsqueda binario. Cada método tiene sus propias ventajas y desventajas y la mejor elección dependerá de las necesidades específicas de su aplicación.
Las colas de prioridad se utilizan a menudo en sistemas en tiempo real, donde el orden en el que se procesan los elementos puede tener consecuencias importantes. También se utilizan en algoritmos para mejorar su eficiencia, como El algoritmo de Dijkstra para encontrar el camino más corto en un gráfico y el algoritmo de búsqueda A* para encontrar caminos.
Propiedades de la cola de prioridad
Entonces, una cola prioritaria es una extensión de la cola con las siguientes propiedades.
- Cada elemento tiene una prioridad asociada.
- Un elemento con alta prioridad se retira de la cola antes que un elemento con baja prioridad.
- Si dos elementos tienen la misma prioridad, se sirven según su orden en la cola.
En la siguiente cola de prioridad, un elemento con un valor ASCII máximo tendrá la prioridad más alta. Los elementos con mayor prioridad se sirven primero.
¿Cómo se asigna prioridad a los elementos de una cola de prioridad?
En una cola de prioridad, generalmente, se considera el valor de un elemento para asignar la prioridad.
Por ejemplo, al elemento con el valor más alto se le asigna la prioridad más alta y al elemento con el valor más bajo se le asigna la prioridad más baja. También se puede utilizar el caso inverso, es decir, al elemento con el valor más bajo se le puede asignar la prioridad más alta. Además, la prioridad se puede asignar según nuestras necesidades.
Operaciones de una cola prioritaria:
Una cola de prioridad típica admite las siguientes operaciones:
1) Inserción en una cola prioritaria
Cuando se inserta un nuevo elemento en una cola de prioridad, se mueve al espacio vacío de arriba a abajo y de izquierda a derecha. Sin embargo, si el elemento no está en el lugar correcto, se comparará con el nodo principal. Si el elemento no está en el orden correcto, los elementos se intercambian. El proceso de intercambio continúa hasta que todos los elementos se colocan en la posición correcta.
2) Eliminación en una cola de prioridad
Como sabes, en un montón máximo, el elemento máximo es el nodo raíz. Y eliminará primero el elemento que tiene máxima prioridad. Por lo tanto, elimina el nodo raíz de la cola. Esta eliminación crea una ranura vacía, que se llenará aún más con una nueva inserción. Luego, compara el elemento recién insertado con todos los elementos dentro de la cola para mantener el montón invariante.
3) Echar un vistazo a una cola prioritaria
Esta operación ayuda a devolver el elemento máximo de Max Heap o el elemento mínimo de Min Heap sin eliminar el nodo de la cola de prioridad.
Tipos de cola prioritaria:
1) Cola de prioridad de orden ascendente
Como sugiere el nombre, en la cola de prioridad en orden ascendente, el elemento con un valor de prioridad más bajo recibe una prioridad más alta en la lista de prioridades. Por ejemplo, si tenemos los siguientes elementos en una cola de prioridad ordenados en orden ascendente como 4,6,8,9,10. Aquí, 4 es el número más pequeño, por lo tanto, obtendrá la prioridad más alta en una cola de prioridad y, por lo tanto, cuando retiremos la cola de este tipo de cola de prioridad, 4 se eliminará de la cola y la cola devuelve 4.
2) Cola de prioridad en orden descendente
El nodo raíz es el elemento máximo en un montón máximo, como ya sabrá. También eliminará primero el elemento con mayor prioridad. Como resultado, el nodo raíz se elimina de la cola. Esta eliminación deja un espacio vacío, que se llenará con nuevas inserciones en el futuro. Luego, la invariante del montón se mantiene comparando el elemento recién insertado con todas las demás entradas de la cola.
Tipos de colas prioritarias
¿Diferencia entre cola prioritaria y cola normal?
No hay prioridad asignada a los elementos en una cola, se implementa la regla de primero en entrar, primero en salir (FIFO), mientras que, en una cola de prioridad, los elementos tienen prioridad. Los elementos con mayor prioridad se sirven primero.
¿Cómo implementar la cola de prioridad?
La cola de prioridad se puede implementar utilizando las siguientes estructuras de datos:
- matrices
- Lista enlazada
- Estructura de datos del montón
- Árbol de búsqueda binaria
Analicemos todo esto en detalle.
1) Implementar cola de prioridad mediante matriz:
Una implementación simple es utilizar una matriz de la siguiente estructura.
elemento de estructura {
elemento entero;
prioridad interna;
}
- enqueue(): esta función se utiliza para insertar nuevos datos en la cola. dequeue(): esta función elimina el elemento con mayor prioridad de la cola. peek()/top(): esta función se utiliza para obtener el elemento de mayor prioridad en la cola sin eliminarlo de la cola.
| matrices | poner en cola() | respectivamente () obtener la longitud de la matriz en c | ojeada() |
|---|---|---|---|
| Complejidad del tiempo | O(1) | En) | En) |
C++
// C++ program to implement Priority Queue> // using Arrays> #include> 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 highestPriority = pr[i].priority; ind = i; } else if (highestPriority 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 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; }> |
>
>
Java
// Java program to implement Priority Queue> // using Arrays> import> java.util.*;> // Structure for the elements in the> // priority queue> class> item {> >public> int> value;> >public> int> priority;> };> class> GFG {> >// Store the element of a priority queue> >static> item[] pr =>new> item[>100000>];> >// Pointer to the last index> >static> int> size = ->1>;> >// Function to insert a new element> >// into priority queue> >static> void> enqueue(>int> value,>int> priority)> >{> >// Increase the size> >size++;> >// Insert the element> >pr[size] =>new> item();> >pr[size].value = value;> >pr[size].priority = priority;> >}> >// Function to check the top element> >static> int> peek()> >{> >int> highestPriority = Integer.MIN_VALUE;> >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 highestPriority = pr[i].priority; ind = i; } else if (highestPriority highestPriority = pr[i].priority; ind = i; } } // Return position of the element return ind; } // Function to remove the element with // the highest priority static 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 pr[i] = pr[i + 1]; } // Decrease the size of the // priority queue by one size--; } public static void main(String[] args) { // 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(); System.out.println(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); System.out.println(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); System.out.println(pr[ind].value); } } // this code is contributed by phasing17> |
>
>
Python3
import> sys> # Structure for the elements in the> # priority queue> class> item :> >value>=> 0> >priority>=> 0> class> GFG :> > ># Store the element of a priority queue> >pr>=> [>None>]>*> (>100000>)> > ># Pointer to the last index> >size>=> ->1> > ># Function to insert a new element> ># into priority queue> >@staticmethod> >def> enqueue( value, priority) :> > ># Increase the size> >GFG.size>+>=> 1> > ># Insert the element> >GFG.pr[GFG.size]>=> item()> >GFG.pr[GFG.size].value>=> value> >GFG.pr[GFG.size].priority>=> priority> > ># Function to check the top element> >@staticmethod> >def> peek() :> >highestPriority>=> ->sys.maxsize> >ind>=> ->1> > ># Check for the element with> ># highest priority> >i>=> 0> >while> (i <>=> GFG.size) :> > ># If priority is same choose> ># the element with the> ># highest value> >if> (highestPriority>=>=> GFG.pr[i].priority>and> ind>>->1> and> GFG.pr[ind].value highestPriority = GFG.pr[i].priority ind = i elif(highestPriority highestPriority = GFG.pr[i].priority ind = i i += 1 # Return position of the element return ind # Function to remove the element with # the highest priority @staticmethod def dequeue() : # Find the position of the element # with highest priority ind = GFG.peek() # Shift the element one index before # from the position of the element # with highest priority is found i = ind while (i GFG.pr[i] = GFG.pr[i + 1] i += 1 # Decrease the size of the # priority queue by one GFG.size -= 1 @staticmethod def main( args) : # Function Call to insert elements # as per the priority GFG.enqueue(10, 2) GFG.enqueue(14, 4) GFG.enqueue(16, 4) GFG.enqueue(12, 3) # Stores the top element # at the moment ind = GFG.peek() print(GFG.pr[ind].value) # Dequeue the top element GFG.dequeue() # Check the top element ind = GFG.peek() print(GFG.pr[ind].value) # Dequeue the top element GFG.dequeue() # Check the top element ind = GFG.peek() print(GFG.pr[ind].value) if __name__=='__main__': GFG.main([]) # This code is contributed by aadityaburujwale.> |
>
>
lista ordenada java
C#
// C# program to implement Priority Queue> // using Arrays> using> System;> // Structure for the elements in the> // priority queue> public> class> item {> >public> int> value;> >public> int> priority;> };> public> class> GFG> {> > >// Store the element of a priority queue> >static> item[] pr =>new> item[100000];> >// Pointer to the last index> >static> int> size = -1;> >// Function to insert a new element> >// into priority queue> >static> void> enqueue(>int> value,>int> priority)> >{> >// Increase the size> >size++;> > >// Insert the element> >pr[size] =>new> item();> >pr[size].value = value;> >pr[size].priority = priority;> >}> > >// Function to check the top element> >static> int> peek()> >{> >int> highestPriority =>int>.MinValue;> >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 highestPriority = pr[i].priority; ind = i; } else if (highestPriority highestPriority = pr[i].priority; ind = i; } } // Return position of the element return ind; } // Function to remove the element with // the highest priority static 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 pr[i] = pr[i + 1]; } // Decrease the size of the // priority queue by one size--; } public static void Main(string[] args) { // 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(); Console.WriteLine(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); Console.WriteLine(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); Console.WriteLine(pr[ind].value); } } //this code is contributed by phasing17> |
>
>
JavaScript
// JavaScript program to implement Priority Queue> // using Arrays> // Structure for the elements in the> // priority queue> class item {> >constructor()> >{> >this>.value;> >this>.priority;> >}> };> // Store the element of a priority queue> let pr = [];> for> (>var> i = 0; i <100000; i++)> >pr.push(>new> item());> // Pointer to the last index> let size = -1;> // Function to insert a new element> // into priority queue> function> enqueue(value, priority)> {> >// Increase the size> >size++;> >// Insert the element> >pr[size] =>new> item();> >pr[size].value = value;> >pr[size].priority = priority;> }> // Function to check the top element> function> peek()> {> >let highestPriority = Number.MIN_SAFE_INTEGER;> >let ind = -1;> >// Check for the element with> >// highest priority> >for> (>var> 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 highestPriority = pr[i].priority; ind = i; } else if (highestPriority highestPriority = pr[i].priority; ind = i; } } // Return position of the element return ind; } // Function to remove the element with // the highest priority function dequeue() { // Find the position of the element // with highest priority let ind = peek(); // Shift the element one index before // from the position of the element // with highest priority is found for (var i = ind; i pr[i] = pr[i + 1]; } // Decrease the size of the // priority queue by one size--; } // 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 let ind = peek(); console.log(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); console.log(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); console.log(pr[ind].value); // this code is contributed by phasing17> |
>
>Producción
16 14 12>
Nota: Leer Este artículo para más detalles.
2) Implementar cola de prioridad mediante lista vinculada:
En una implementación de LinkedList, las entradas se ordenan en orden descendente según su prioridad. El elemento de mayor prioridad siempre se agrega al frente de la cola de prioridad, que se forma mediante listas vinculadas. Las funciones como empujar() , estallido() , y ojeada() se utilizan para implementar una cola de prioridad utilizando una lista vinculada y se explican a continuación:
- push(): esta función se utiliza para insertar nuevos datos en la cola. pop(): esta función elimina el elemento con mayor prioridad de la cola. peek() / top(): esta función se utiliza para obtener el elemento de mayor prioridad en la cola sin eliminarlo de la cola.
| Lista enlazada | empujar() | estallido() | ojeada() |
|---|---|---|---|
| Complejidad del tiempo | En) | O(1) | O(1) |
C++
Amplitud modulada
// C++ code to implement Priority Queue> // using Linked List> #include> using> namespace> std;> // Node> typedef> struct> node {> >int> data;> >// Lower values indicate> >// higher priority> >int> priority;> >struct> node* next;> } Node;> // Function to create a new node> Node* newNode(>int> d,>int> p)> {> >Node* temp = (Node*)>malloc>(>sizeof>(Node));> >temp->datos = d;> >temp->prioridad = p;> >temp->siguiente = NULL;> >return> temp;> }> // Return the value at head> int> peek(Node** head) {>return> (*head)->datos; }> // Removes the element with the> // highest priority form the list> void> pop(Node** head)> {> >Node* temp = *head;> >(*head) = (*head)->siguiente;> >free>(temp);> }> // Function to push according to priority> void> push(Node** head,>int> d,>int> p)> {> >Node* start = (*head);> >// Create new Node> >Node* temp = newNode(d, p);> >// Special Case: The head of list has> >// lesser priority than new node> >if> ((*head)->prioridad // Insertar nuevo nodo antes de head temp->next = *head; (*cabeza) = temporal; } else { // Recorre la lista y encuentra una // posición para insertar un nuevo nodo while (start->next != NULL && start->next->priority> p) { start = start->next; } // Ya sea al final de la lista // o en la posición requerida temp->next = start->next; inicio->siguiente = temporal; } } // La función para verificar si la lista está vacía int isEmpty(Node** head) { return (*head) == NULL; } // Código del controlador int main() { // Crear una cola de prioridad // 7->4->5->6 Nodo* pq = newNode(4, 1); empujar(&pq, 5, 2); empujar(&pq, 6, 3); empujar(&pq, 7, 0); mientras (! está vacío (&pq)) { cout<< ' ' << peek(&pq); pop(&pq); } return 0; }> |
>
>
Java
// Java code to implement Priority Queue> // using Linked List> import> java.util.* ;> class> Solution> {> // Node> static> class> Node {> >int> data;> > >// Lower values indicate higher priority> >int> priority;> >Node next;> > }> static> Node node =>new> Node();> > // Function to Create A New Node> static> Node newNode(>int> d,>int> p)> {> >Node temp =>new> Node();> >temp.data = d;> >temp.priority = p;> >temp.next =>null>;> > >return> temp;> }> > // Return the value at head> static> int> peek(Node head)> {> >return> (head).data;> }> > // Removes the element with the> // highest priority from the list> static> Node pop(Node head)> {> >Node temp = head;> >(head) = (head).next;> >return> head;> }> > // Function to push according to priority> static> Node push(Node head,>int> d,>int> p)> {> >Node start = (head);> > >// Create new Node> >Node temp = newNode(d, p);> > >// Special Case: The head of list has lesser> >// priority than new node. So insert new> >// node before head node and change head node.> >if> ((head).priority // Insert New Node before head temp.next = head; (head) = temp; } else { // Traverse the list and find a // position to insert new node while (start.next != null && start.next.priority>p) { inicio = inicio.siguiente; } // Ya sea al final de la lista // o en la posición requerida temp.next = start.next; inicio.siguiente = temporal; } retorno de cabeza; } // La función para verificar si la lista está vacía static int isEmpty(Node head) { return ((head) == null)?1:0; } // Código del controlador public static void main(String args[]) { // Crear una cola de prioridad // 7.4.5.6 Nodo pq = newNode(4, 1); pq =empujar(pq, 5, 2); pq =empujar(pq, 6, 3); pq =empujar(pq, 7, 0); while (isEmpty(pq)==0) { System.out.printf('%d ', peek(pq)); pq=pop(pq); } } } // Este código es una contribución de ishankhandelwals.> |
>
>
Pitón
# Python3 code to implement Priority Queue> # using Singly Linked List> # Class to create new node which includes> # Node Data, and Node Priority> class> PriorityQueueNode:> >def> _init_(>self>, value, pr):> >self>.data>=> value> >self>.priority>=> pr> >self>.>next> => None> # Implementation of Priority Queue> class> PriorityQueue:> >def> _init_(>self>):> >self>.front>=> None> ># Method to check Priority Queue is Empty> ># or not if Empty then it will return True> ># Otherwise False> >def> isEmpty(>self>):> >return> True> if> self>.front>=>=> None> else> False> ># Method to add items in Priority Queue> ># According to their priority value> >def> push(>self>, value, priority):> ># Condition check for checking Priority> ># Queue is empty or not> >if> self>.isEmpty()>=>=> True>:> ># Creating a new node and assigning> ># it to class variable> >self>.front>=> PriorityQueueNode(value,> >priority)> ># Returning 1 for successful execution> >return> 1> >else>:> ># Special condition check to see that> ># first node priority value> >if> self>.front.priority # Creating a new node newNode = PriorityQueueNode(value, priority) # Updating the new node next value newNode.next = self.front # Assigning it to self.front self.front = newNode # Returning 1 for successful execution return 1 else: # Traversing through Queue until it # finds the next smaller priority node temp = self.front while temp.next: # If same priority node found then current # node will come after previous node if priority>= temp.next.priority: break temp = temp.next newNode = PriorityQueueNode(valor, prioridad) newNode.next = temp.next temp.next = newNode # Devolviendo 1 para una ejecución exitosa return 1 # Método para eliminar el elemento de alta prioridad # de la Cola de prioridad def pop(self): # Comprobación de condiciones para verificar # La Cola de prioridad está vacía o no si self.isEmpty() == Verdadero: devuelve else: # Eliminando el nodo de alta prioridad de # Cola de prioridad y actualizando el frente # con el siguiente node self.front = self.front.next return 1 # Método para devolver el valor del nodo # de alta prioridad No eliminarlo def peek(self): # Comprobación de condición para comprobar la Prioridad # La cola está vacía o no si self.isEmpty() == Verdadero: devuelve otra cosa: devuelve self.front.data # Método para atravesar la prioridad # Cola def traverse(self): # Comprobación de condición para verificar la prioridad # La cola está vacía o no si self.isEmpty() == Verdadero: devuelve ' ¡La cola está vacía!' else: temp = self.front while temp: print(temp.data, end=' ') temp = temp.next # Código del controlador if _name_ == '_main_': # Creando un instancia de Priority # Queue, y sumando valores # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push(4, 1) pq.push(5, 2) pq.push(6, 3) pq .push(7, 0) # Atravesando la cola de prioridad pq.traverse() # Eliminando el elemento de mayor prioridad # para la cola de prioridad pq.pop()> |
>
>
C#
// C# code to implement Priority Queue> // using Linked List> using> System;> class> GFG> {> >// Node> >public> class> Node> >{> >public> int> data;> >// Lower values indicate> >// higher priority> >public> int> priority;> >public> Node next;> >}> >public> static> Node node =>new> Node();> >// Function to Create A New Node> >public> static> Node newNode(>int> d,>int> p)> >{> >Node temp =>new> Node();> >temp.data = d;> >temp.priority = p;> >temp.next =>null>;> >return> temp;> >}> >// Return the value at head> >public> static> int> peek(Node head)> >{> >return> (head).data;> >}> >// Removes the element with the> >// highest priority from the list> >public> static> Node pop(Node head)> >{> >Node temp = head;> >(head) = (head).next;> >return> head;> >}> >// Function to push according to priority> >public> static> Node push(Node head,> >int> d,>int> p)> >{> >Node start = (head);> >// Create new Node> >Node temp = newNode(d, p);> >// Special Case: The head of list> >// has lesser priority than new node.> >// So insert new node before head node> >// and change head node.> >if> ((head).priority { // Insert New Node before head temp.next = head; (head) = temp; } else { // Traverse the list and find a // position to insert new node while (start.next != null && start.next.priority>p) { inicio = inicio.siguiente; } // Ya sea al final de la lista // o en la posición requerida temp.next = start.next; inicio.siguiente = temporal; } retorno de cabeza; } // La función para verificar si la lista está vacía public static int isEmpty(Node head) { return ((head) == null)? 1: 0; } // Código del controlador public static void Main(string[] args) { // Crear una cola de prioridad // 7.4.5.6 Nodo pq = newNode(4, 1); pq = empujar(pq, 5, 2); pq = empujar(pq, 6, 3); pq = empujar(pq, 7, 0); while (isEmpty(pq) == 0) { Console.Write('{0:D} ', peek(pq)); pq = pop(pq); } } } // Este código es una contribución de ishankhandelwals.> |
>
>
JavaScript
más java
// JavaScript code to implement Priority Queue> // using Linked List> // Node> class Node {> >// Lower values indicate> >// higher priority> >constructor() {> >this>.data = 0;> >this>.priority = 0;> >this>.next =>null>;> >}> }> var> node =>new> Node();> // Function to Create A New Node> function> newNode(d, p) {> >var> temp =>new> Node();> >temp.data = d;> >temp.priority = p;> >temp.next =>null>;> >return> temp;> }> // Return the value at head> function> peek(head) {> >return> head.data;> }> // Removes the element with the> // highest priority from the list> function> pop(head) {> >var> temp = head;> >head = head.next;> >return> head;> }> // Function to push according to priority> function> push(head, d, p) {> >var> start = head;> >// Create new Node> >var> temp = newNode(d, p);> >// Special Case: The head of list> >// has lesser priority than new node.> >// So insert new node before head node> >// and change head node.> >if> (head.priority // Insert New Node before head temp.next = head; head = temp; } else { // Traverse the list and find a // position to insert new node while (start.next != null && start.next.priority>p) { inicio = inicio.siguiente; } // Ya sea al final de la lista // o en la posición requerida temp.next = start.next; inicio.siguiente = temporal; } retorno de cabeza; } // La función para verificar si la lista está vacía function isEmpty(head) { return head == null ? 1: 0; } // Código del controlador // Crear una cola de prioridad // 7.4.5.6 var pq = newNode(4, 1); pq = empujar(pq, 5, 2); pq = empujar(pq, 6, 3); pq = empujar(pq, 7, 0); while (isEmpty(pq) == 0) { console.log(peek(pq),' '); pq = pop(pq); } // Este código es una contribución de ishankhandelwals.> |
>
>Producción
6 5 4 7>
Consulte este artículo para obtener más detalles.
Nota: También podemos usar la lista vinculada, la complejidad temporal de todas las operaciones con la lista vinculada sigue siendo la misma que la de la matriz. La ventaja de la lista enlazada es eliminar la prioridad más alta() Puede ser más eficiente ya que no tenemos que mover elementos.
3) Implementar cola de prioridad utilizando montones:
Generalmente se prefiere Binary Heap para la implementación de colas prioritarias porque los montones proporcionan un mejor rendimiento en comparación con las matrices o LinkedList. Teniendo en cuenta las propiedades de un montón, la entrada con la clave más grande está en la parte superior y se puede eliminar inmediatamente. Sin embargo, llevará un tiempo O(log n) restaurar la propiedad del montón para las claves restantes. Sin embargo, si se va a insertar otra entrada inmediatamente, parte de este tiempo puede combinarse con el tiempo O(log n) necesario para insertar la nueva entrada. Por lo tanto, la representación de una cola de prioridad como un montón resulta ventajosa para n grande, ya que se representa eficientemente en almacenamiento contiguo y se garantiza que requerirá solo un tiempo logarítmico tanto para las inserciones como para las eliminaciones. Las operaciones en Binary Heap son las siguientes:
- insert(p): Inserta un nuevo elemento con prioridad p. extractMax(): Extrae un elemento con máxima prioridad. remove(i): Elimina un elemento señalado por un iterador i. getMax(): Devuelve un elemento con máxima prioridad. changePriority(i, p): Cambia la prioridad de un elemento señalado por yo a p .
| montón binario | insertar() | eliminar() | ojeada() |
|---|---|---|---|
| Complejidad del tiempo | O(log n) | O(log n) | O(1) |
Consulte este artículo para conocer la implementación del código.
4) Implementar la cola de prioridad utilizando el árbol de búsqueda binaria:
También se puede utilizar un árbol de búsqueda binaria autoequilibrado como el árbol AVL, el árbol rojo-negro, etc. para implementar una cola de prioridad. Operaciones como peek(), insert() y delete() se pueden realizar usando BST.
| Árbol de búsqueda binaria | ojeada() | insertar() | borrar() |
|---|---|---|---|
| Complejidad del tiempo | O(1) | O(log n) | O(log n) |
Aplicaciones de cola prioritaria:
- Programación de CPU
- Algoritmos gráficos como el algoritmo de ruta más corta de Dijkstra, el árbol de expansión mínima de Prim, etc.
- Implementación de pila
- Todas las aplicaciones de cola prioritaria
- Cola de prioridad en C++
- Cola de prioridad en Java
- Cola de prioridad en Python
- Cola de prioridad en JavaScript
- Artículos recientes sobre Priority Queue!