UN coda prioritaria è un tipo di coda che organizza gli elementi in base ai loro valori di priorità. Gli elementi con valori di priorità più alti vengono in genere recuperati prima degli elementi con valori di priorità più bassi.
In una coda con priorità, a ciascun elemento è associato un valore di priorità. Quando aggiungi un elemento alla coda, viene inserito in una posizione in base al suo valore di priorità. Ad esempio, se aggiungi un elemento con un valore di priorità elevato a una coda con priorità, potrebbe essere inserito nella parte anteriore della coda, mentre un elemento con un valore di priorità basso potrebbe essere inserito nella parte posteriore.
Esistono diversi modi per implementare una coda con priorità, incluso l'utilizzo di un array, un elenco collegato, un heap o un albero di ricerca binario. Ciascun metodo presenta vantaggi e svantaggi e la scelta migliore dipenderà dalle esigenze specifiche della tua applicazione.
Le code prioritarie vengono spesso utilizzate nei sistemi in tempo reale, dove l'ordine in cui gli elementi vengono elaborati può avere conseguenze significative. Sono anche utilizzati negli algoritmi per migliorare la loro efficienza, come ad esempio Algoritmo di Dijkstra per trovare il percorso più breve in un grafico e l'algoritmo di ricerca A* per l'individuazione del percorso.
Proprietà della coda prioritaria
Quindi, una coda prioritaria è un'estensione del file coda con le seguenti proprietà.
- Ad ogni elemento è associata una priorità.
- Un elemento con priorità alta viene rimosso dalla coda prima di un elemento con priorità bassa.
- Se due elementi hanno la stessa priorità, verranno serviti secondo il loro ordine in coda.
Nella coda di priorità sottostante, un elemento con un valore ASCII massimo avrà la priorità più alta. Gli elementi con priorità più alta vengono serviti per primi.
Come viene assegnata la priorità agli elementi in una coda prioritaria?
In una coda con priorità, generalmente, per l'assegnazione della priorità viene considerato il valore di un elemento.
Ad esempio, all'elemento con il valore più alto viene assegnata la priorità più alta e all'elemento con il valore più basso viene assegnata la priorità più bassa. È possibile utilizzare anche il caso inverso, ovvero all'elemento con il valore più basso può essere assegnata la priorità più alta. Inoltre, la priorità può essere assegnata in base alle nostre esigenze.
Operazioni di una coda prioritaria:
Una tipica coda con priorità supporta le seguenti operazioni:
1) Inserimento in una Coda Prioritaria
Quando un nuovo elemento viene inserito in una coda di priorità, si sposta nello slot vuoto dall'alto verso il basso e da sinistra a destra. Tuttavia, se l'elemento non è nella posizione corretta, verrà confrontato con il nodo genitore. Se l'elemento non è nell'ordine corretto, gli elementi vengono scambiati. Il processo di scambio continua finché tutti gli elementi non vengono posizionati nella posizione corretta.
2) Cancellazione in una Coda Prioritaria
Come sai, in un heap massimo, l'elemento massimo è il nodo radice. E rimuoverà per primo l'elemento che ha la massima priorità. Pertanto, rimuovi il nodo root dalla coda. Questa rimozione crea uno slot vuoto, che verrà ulteriormente riempito con il nuovo inserimento. Quindi confronta l'elemento appena inserito con tutti gli elementi all'interno della coda per mantenere invariante l'heap.
3) Sbircia in una coda prioritaria
Questa operazione aiuta a restituire l'elemento massimo da Max Heap o l'elemento minimo da Min Heap senza eliminare il nodo dalla coda di priorità.
Tipi di coda prioritaria:
1) Coda con priorità dell'ordine crescente
Come suggerisce il nome, nella coda di priorità in ordine crescente, all'elemento con un valore di priorità più basso viene assegnata una priorità più alta nell'elenco delle priorità. Ad esempio, se abbiamo i seguenti elementi in una coda di priorità disposti in ordine crescente come 4,6,8,9,10. Qui, 4 è il numero più piccolo, pertanto otterrà la priorità più alta in una coda con priorità e quindi quando effettuiamo la rimozione dalla coda da questo tipo di coda con priorità, 4 verrà rimosso dalla coda e la rimozione dalla coda restituirà 4.
2) Coda prioritaria in ordine discendente
Il nodo radice è l'elemento massimo in un heap massimo, come forse saprai. Verrà inoltre rimosso prima l'elemento con la priorità più alta. Di conseguenza, il nodo radice viene rimosso dalla coda. Questa cancellazione lascia uno spazio vuoto, che verrà riempito con nuovi inserimenti in futuro. L'invariante dell'heap viene quindi mantenuta confrontando l'elemento appena inserito con tutte le altre voci nella coda.
stringa n Java
Tipi di code prioritarie
Differenza tra coda prioritaria e coda normale?
Non esiste alcuna priorità assegnata agli elementi in una coda, viene implementata la regola del first-in-first-out (FIFO) mentre, in una coda con priorità, gli elementi hanno una priorità. Gli elementi con priorità più alta vengono serviti per primi.
Come implementare la coda prioritaria?
La coda prioritaria può essere implementata utilizzando le seguenti strutture dati:
- Array
- Lista collegata
- Struttura dei dati heap
- Albero di ricerca binario
Discutiamo tutti questi in dettaglio.
1) Implementare la coda prioritaria utilizzando l'array:
Una semplice implementazione consiste nell'utilizzare un array con la seguente struttura.
elemento struttura {
elemento intero;
priorità int;
}
- enqueue(): questa funzione viene utilizzata per inserire nuovi dati nella coda. dequeue(): questa funzione rimuove l'elemento con la priorità più alta dalla coda. peek()/top(): questa funzione viene utilizzata per ottenere l'elemento con la priorità più alta nella coda senza rimuoverlo dalla coda.
| Array | accodare() | di conseguenza () | sbirciare() |
|---|---|---|---|
| Complessità temporale | O(1) | SU) | SU) |
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; }> |
>
>
Giava
// 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> |
come trovo le app nascoste su Android
>
>
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.> |
>
>
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> |
>
uri rispetto all'URL
>Produzione
16 14 12>
Nota: Leggere Questo articolo per ulteriori dettagli.
2) Implementare la coda prioritaria utilizzando l'elenco collegato:
In un'implementazione LinkedList, le voci vengono ordinate in ordine decrescente in base alla loro priorità. L'elemento con la priorità più alta viene sempre aggiunto all'inizio della coda di priorità, che è formata utilizzando elenchi collegati. Le funzioni come spingere() , pop() , E sbirciare() vengono utilizzati per implementare una coda con priorità utilizzando un elenco collegato e sono spiegati come segue:
- push(): questa funzione viene utilizzata per inserire nuovi dati nella coda. pop(): questa funzione rimuove l'elemento con la priorità più alta dalla coda. peek() / top(): questa funzione viene utilizzata per ottenere l'elemento con la priorità più alta nella coda senza rimuoverlo dalla coda.
| Lista collegata | spingere() | pop() | sbirciare() |
|---|---|---|---|
| Complessità temporale | SU) | O(1) | O(1) |
C++
// 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->dati = d;> >temp->priorità = p;> >temp->successivo = NULL;> >return> temp;> }> // Return the value at head> int> peek(Node** head) {>return> (*head)->dati; }> // Removes the element with the> // highest priority form the list> void> pop(Node** head)> {> >Node* temp = *head;> >(*head) = (*head)->successivo;> >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)->priorità // Inserisci il nuovo nodo prima di head temp->next = *head; (*testa) = temperatura; } else { // Attraversa l'elenco e trova una // posizione per inserire il nuovo nodo while (start->next != NULL && start->next->priority> p) { start = start->next; } // Alla fine dell'elenco // o nella posizione richiesta temp->next = start->next; inizio->successivo = temp; } } // La funzione per verificare che l'elenco sia vuoto int isEmpty(Node** head) { return (*head) == NULL; } // Codice driver int main() { // Crea una coda prioritaria // 7->4->5->6 Node* pq = newNode(4, 1); spingere(&pq, 5, 2); spingere(&pq, 6, 3); spingere(&pq, 7, 0); while (!èVuoto(&pq)) { cout<< ' ' << peek(&pq); pop(&pq); } return 0; }> |
>
>
Giava
// 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) { inizio = inizio.successivo; } // Alla fine dell'elenco // o nella posizione richiesta temp.next = start.next; inizio.successivo = temperatura; } restituisce testa; } // La funzione per verificare che l'elenco sia vuoto static int isEmpty(Node head) { return ((head) == null)?1:0; } // Codice driver public static void main(String args[]) { // Crea una coda prioritaria // 7.4.5.6 Node pq = newNode(4, 1); pq =spingere(pq, 5, 2); pq =spingere(pq, 6, 3); pq =spingere(pq, 7, 0); while (isEmpty(pq)==0) { System.out.printf('%d ', peek(pq)); pq=pop(pq); } } } // Questo codice è fornito da ishankhandelwals.> |
cos'è ymail
>
>
Pitone
# 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(valore, priorità) newNode.next = temp.next temp.next = newNode # Restituisce 1 per un'esecuzione riuscita return 1 # Metodo per rimuovere l'elemento ad alta priorità # da the Priority Queue def pop(self): # Controllo della condizione per verificare # La Priority Queue è vuota o meno se self.isEmpty() == True: return else: # Rimozione del nodo ad alta priorità da # Priority Queue e aggiornamento front # con next node self.front = self.front.next return 1 # Metodo per restituire alta priorità node # valore Non rimuoverlo def peek(self): # Controllo condizione per verificare la priorità # La coda è vuota o meno se self.isEmpty() == True: return else: return self.front.data # Metodo per attraversare la priorità # Queue def traverse(self): # Controllo della condizione per verificare la priorità # La coda è vuota o meno se self.isEmpty() == True: return ' La coda è vuota!' else: temp = self.front while temp: print(temp.data, end=' ') temp = temp.next # Codice driver if _name_ == '_main_': # Creazione di un istanza di Priority # Queue e aggiunta di valori # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push(4, 1) pq.push(5, 2) pq.push(6, 3) pq .push(7, 0) # Attraversamento della coda con priorità pq.traverse() # Rimozione dell'elemento con priorità più alta # per la coda con priorità 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) { inizio = inizio.successivo; } // Alla fine dell'elenco // o nella posizione richiesta temp.next = start.next; inizio.successivo = temperatura; } restituisce testa; } // La funzione per verificare che l'elenco sia vuoto public static int isEmpty(Node head) { return ((head) == null) ? 1:0; } // Codice driver public static void Main(string[] args) { // Crea una coda prioritaria // 7.4.5.6 Node pq = newNode(4, 1); pq = spingi(pq, 5, 2); pq = spingi(pq, 6, 3); pq = spingi(pq, 7, 0); while (isEmpty(pq) == 0) { Console.Write('{0:D} ', peek(pq)); pq = pop(pq); } } } // Questo codice è fornito da ishankhandelwals.> |
>
>
Javascript
// 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) { inizio = inizio.successivo; } // Alla fine dell'elenco // o nella posizione richiesta temp.next = start.next; inizio.successivo = temperatura; } restituisce testa; } // La funzione per verificare che l'elenco sia vuoto function isEmpty(head) { return head == null ? 1:0; } // Codice driver // Crea una coda prioritaria // 7.4.5.6 var pq = newNode(4, 1); pq = spingi(pq, 5, 2); pq = spingi(pq, 6, 3); pq = spingi(pq, 7, 0); while (èVuoto(pq) == 0) { console.log(peek(pq),' '); pq = pop(pq); } // Questo codice è fornito da ishankhandelwals.> |
>
>Produzione
6 5 4 7>
Fare riferimento a questo articolo per maggiori dettagli.
Nota: Possiamo anche utilizzare la lista collegata, la complessità temporale di tutte le operazioni con la lista collegata rimane la stessa dell'array. Il vantaggio con l'elenco collegato è deleteHighestPriority() può essere più efficiente poiché non dobbiamo spostare gli oggetti.
3) Implementare la coda prioritaria utilizzando gli heap:
L'heap binario è generalmente preferito per l'implementazione della coda con priorità poiché gli heap forniscono prestazioni migliori rispetto agli array o alla LinkedList. Considerando le proprietà di un heap, la voce con la chiave più grande è in alto e può essere rimossa immediatamente. Tuttavia, sarà necessario del tempo O(log n) per ripristinare la proprietà heap per le chiavi rimanenti. Tuttavia, se si deve inserire immediatamente un'altra voce, parte di questo tempo può essere combinato con il tempo O(log n) necessario per inserire la nuova voce. Pertanto la rappresentazione di una coda con priorità come heap si rivela vantaggiosa per n grandi, poiché è rappresentata in modo efficiente in una memoria contigua ed è garantito che richieda solo tempo logaritmico sia per gli inserimenti che per le cancellazioni. Le operazioni sull'heap binario sono le seguenti:
conteggio mysql
- insert(p): inserisce un nuovo elemento con priorità p. extractMax(): estrae un elemento con la massima priorità. rimuovi(i): rimuove un elemento puntato da un iteratore i. getMax(): restituisce un elemento con la massima priorità. changePriority(i, p): modifica la priorità di un elemento puntato da i a pag .
| Heap binario | inserire() | rimuovere() | sbirciare() |
|---|---|---|---|
| Complessità temporale | O(log n) | O(log n) | O(1) |
Fare riferimento a questo articolo per l'implementazione del codice.
4) Implementare la coda prioritaria utilizzando l'albero di ricerca binario:
Per implementare una coda di priorità è inoltre possibile utilizzare un albero di ricerca binario autobilanciante come l'albero AVL, l'albero rosso-nero, ecc. Operazioni come peek(), insert() e delete() possono essere eseguite utilizzando BST.
| Albero di ricerca binaria | sbirciare() | inserire() | eliminare() |
|---|---|---|---|
| Complessità temporale | O(1) | O(log n) | O(log n) |
Applicazioni della coda prioritaria:
- Pianificazione della CPU
- Algoritmi grafici come l'algoritmo del percorso più breve di Dijkstra, il Minimum Spanning Tree di Prim, ecc.
- Implementazione dello stack
- Tutte le applicazioni della coda prioritaria
- Coda prioritaria in C++
- Coda prioritaria in Java
- Coda prioritaria in Python
- Coda prioritaria in JavaScript
- Articoli recenti sulla coda prioritaria!