EN prioritert kø er en type kø som arrangerer elementer basert på deres prioriterte verdier. Elementer med høyere prioritetsverdier hentes vanligvis før elementer med lavere prioritetsverdier.
I en prioritetskø har hvert element en prioritetsverdi knyttet til seg. Når du legger til et element i køen, settes det inn i en posisjon basert på prioritetsverdien. For eksempel, hvis du legger til et element med høy prioritet verdi i en prioritert kø, kan det settes inn nær foran køen, mens et element med lav prioritet verdi kan settes inn bakerst.
Det er flere måter å implementere en prioritert kø, inkludert å bruke en matrise, koblet liste, haug eller binært søketre. Hver metode har sine egne fordeler og ulemper, og det beste valget vil avhenge av de spesifikke behovene til din applikasjon.
Prioriterte køer brukes ofte i sanntidssystemer, hvor rekkefølgen elementer behandles i kan få betydelige konsekvenser. De brukes også i algoritmer for å forbedre effektiviteten, som f.eks Dijkstras algoritme for å finne den korteste veien i en graf og A*-søkealgoritmen for stifinning.
Egenskaper for prioritert kø
Så en prioritert kø er en forlengelse av kø med følgende egenskaper.
- Hvert element har en prioritet knyttet til seg.
- Et element med høy prioritet settes ut av kø før et element med lav prioritet.
- Hvis to elementer har samme prioritet, serveres de i henhold til rekkefølgen i køen.
I prioritetskøen nedenfor vil et element med en maksimal ASCII-verdi ha høyeste prioritet. Elementene med høyere prioritet serveres først.
Hvordan tildeles prioritet til elementene i en prioritert kø?
I en prioritetskø vurderes generelt verdien til et element for tildeling av prioritet.
For eksempel tildeles elementet med høyest verdi høyest prioritet og elementet med lavest verdi får lavest prioritet. Det omvendte tilfellet kan også brukes, dvs. elementet med den laveste verdien kan tildeles høyest prioritet. Prioriteten kan også tildeles i henhold til våre behov.
Operasjoner av en prioritert kø:
En typisk prioritetskø støtter følgende operasjoner:
1) Innsetting i en prioritert kø
Når et nytt element settes inn i en prioritert kø, flyttes det til det tomme sporet fra topp til bunn og venstre mot høyre. Men hvis elementet ikke er på riktig sted, vil det bli sammenlignet med den overordnede noden. Hvis elementet ikke er i riktig rekkefølge, byttes elementene. Bytteprosessen fortsetter til alle elementene er plassert i riktig posisjon.
2) Sletting i en prioritert kø
Som du vet at i en maks haug, er det maksimale elementet rotnoden. Og det vil fjerne elementet som har maksimal prioritet først. Dermed fjerner du rotnoden fra køen. Denne fjerningen skaper et tomt spor, som vil bli ytterligere fylt med ny innsetting. Deretter sammenligner den det nylig innsatte elementet med alle elementene i køen for å opprettholde heap-invarianten.
3) Kikk i en prioritert kø
Denne operasjonen hjelper til med å returnere maksimumselementet fra Max Heap eller minimumselementet fra Min Heap uten å slette noden fra prioritetskøen.
Typer prioritert kø:
1) Stigende rekkefølgeprioritetskø
Som navnet antyder, i stigende prioritetskø, blir elementet med lavere prioritetsverdi gitt høyere prioritet i prioritetslisten. For eksempel, hvis vi har følgende elementer i en prioritetskø ordnet i stigende rekkefølge som 4,6,8,9,10. Her er 4 det minste tallet, derfor vil det få høyeste prioritet i en prioritetskø, og så når vi tar ut kø fra denne typen prioritetskø, vil 4 fjernes fra køen og dekø returnerer 4.
2) Synkende rekkefølge Prioritetskø
Rotnoden er det maksimale elementet i en maks haug, som du kanskje vet. Det vil også fjerne elementet med høyest prioritet først. Som et resultat fjernes rotnoden fra køen. Denne slettingen etterlater en tom plass, som vil bli fylt med nye innsettinger i fremtiden. Heap-invarianten opprettholdes deretter ved å sammenligne det nylig innsatte elementet med alle andre oppføringer i køen.
tostring-metoden i java
Typer prioriterte køer
Forskjellen mellom Priority Queue og Normal Queue?
Det er ingen prioritet knyttet til elementer i en kø, regelen om først-inn-først-ut (FIFO) er implementert, mens elementene i en prioritetskø har prioritet. Elementene med høyere prioritet serveres først.
Hvordan implementere Priority Queue?
Prioritetskø kan implementeres ved hjelp av følgende datastrukturer:
- Matriser
- Koblet liste
- Heap datastruktur
- Binært søketre
La oss diskutere alt dette i detalj.
1) Implementer Priority Queue ved å bruke Array:
En enkel implementering er å bruke en rekke med følgende struktur.
strukturelement {
int element;
int prioritet;
}
- enqueue(): Denne funksjonen brukes til å sette inn nye data i køen. dequeue(): Denne funksjonen fjerner elementet med høyest prioritet fra køen. peek()/top(): Denne funksjonen brukes til å få det høyeste prioriterte elementet i køen uten å fjerne det fra køen.
| Matriser | kø() | tilsvarende () | kikke() |
|---|---|---|---|
| Tidskompleksitet | O(1) | På) | På) |
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> |
sql rekkefølge etter dato
>
>
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> |
>
java samling rammeverk
>Produksjon
16 14 12>
Merk: Lese denne artikkelen for flere detaljer.
2) Implementer prioritert kø ved å bruke koblet liste:
I en LinkedList-implementering blir oppføringene sortert i synkende rekkefølge basert på deres prioritet. Det høyeste prioriterte elementet legges alltid til foran i prioritetskøen, som dannes ved hjelp av koblede lister. Funksjonene som trykk() , pop() , og kikke() brukes til å implementere en prioritert kø ved hjelp av en koblet liste og forklares som følger:
- push(): Denne funksjonen brukes til å sette inn nye data i køen. pop(): Denne funksjonen fjerner elementet med høyest prioritet fra køen. peek() / top(): Denne funksjonen brukes til å få det høyeste prioriterte elementet i køen uten å fjerne det fra køen.
| Koblet liste | trykk() | pop() | kikke() |
|---|---|---|---|
| Tidskompleksitet | På) | 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->data = d;> >temp->prioritet = p;> >temp->neste = NULL;> >return> temp;> }> // Return the value at head> int> peek(Node** head) {>return> (*head)->data; }> // Removes the element with the> // highest priority form the list> void> pop(Node** head)> {> >Node* temp = *head;> >(*head) = (*head)->neste;> >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)->prioritet // Sett inn ny node før hodet temp->neste = *hode; (*hode) = temp; } else { // Gå gjennom listen og finn en //-posisjon for å sette inn ny node mens (start->neste != NULL && start->neste->prioritet> p) { start = start->neste; } // Enten på slutten av listen // eller på ønsket posisjon temp->neste = start->neste; start->neste = temp; } } // Funksjonen for å sjekke om listen er tom int isEmpty(Node** hode) { return (*hode) == NULL; } // Driverkode int main() { // Opprett en prioritert kø // 7->4->5->6 Node* pq = newNode(4, 1); push(&pq, 5, 2); push(&pq, 6, 3); push(&pq, 7, 0); while (!isEmpty(&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) { start = start.neste; } // Enten i enden av listen // eller i ønsket posisjon temp.next = start.next; start.neste = temp; } returnere hodet; } // Funksjonen for å sjekke at listen er tom statisk int isEmpty(Nodehode) { return ((head) == null)?1:0; } // Driver code public static void main(String args[]) { // Create a Priority Queue // 7.4.5.6 Node pq = newNode(4, 1); pq =push(pq, 5, 2); pq =push(pq, 6, 3); pq =push(pq, 7, 0); while (isEmpty(pq)==0) { System.out.printf('%d ', kikk(pq)); pq=pop(pq); } } } // Denne koden er bidratt av ishankhandelwals.> |
javascript trim understreng
>
>
Python
# 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(verdi, prioritet) newNode.next = temp.next temp.next = newNode # Returnerer 1 for vellykket utførelse return 1 # Metode for å fjerne høyprioritet element # fra the Priority Queue def pop(self): # Betingelsessjekk for kontroll # Priority Queue er tom eller ikke hvis self.isEmpty() == True: return else: # Fjerner node med høy prioritet fra # Priority Queue, og oppdaterer front # med neste node self.front = self.front.next return 1 # Metode for å returnere node med høy prioritet # verdi Fjerner den ikke def peek(self): # Tilstandssjekk for å sjekke Prioritet # Køen er tom eller ikke hvis self.isEmpty() == True: return else: return self.front.data # Metode for å gå gjennom prioritet # Kø def travers(selv): # Betingelsessjekk for kontroll av prioritet # Køen er tom eller ikke hvis self.isEmpty() == True: return ' Køen er tom!' else: temp = self.front mens temp: print(temp.data, end=' ') temp = temp.next # Driverkode hvis _name_ == '_main_': # Opprette en forekomst av Priority # Queue, og legge til verdier # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push(4, 1) pq.push(5, 2) pq.push(6, 3) pq .push(7, 0) # Gå gjennom prioritetskøen pq.traverse() # Fjerner element med høyeste prioritet # for prioritetskøen pq.pop()> |
>
>
C#
java konverter streng til heltall
// 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) { start = start.neste; } // Enten i enden av listen // eller i ønsket posisjon temp.next = start.next; start.neste = temp; } returnere hodet; } // Funksjonen for å sjekke at listen er tom offentlig statisk int isEmpty(Nodehode) { return ((head) == null) ? 1:0; } // Driver code public static void Main(string[] args) { // Create a Priority Queue // 7.4.5.6 Node pq = newNode(4, 1); pq = push(pq, 5, 2); pq = push(pq, 6, 3); pq = push(pq, 7, 0); while (isEmpty(pq) == 0) { Console.Write('{0:D} ', kikk(pq)); pq = pop(pq); } } } // Denne koden er bidratt av 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) { start = start.neste; } // Enten i enden av listen // eller i ønsket posisjon temp.next = start.next; start.neste = temp; } returnere hodet; } // Funksjonen som skal sjekkes om listen er tom funksjonen isEmpty(head) { return head == null ? 1:0; } // Driverkode // Opprett en prioritert kø // 7.4.5.6 var pq = newNode(4, 1); pq = push(pq, 5, 2); pq = push(pq, 6, 3); pq = push(pq, 7, 0); while (isEmpty(pq) == 0) { console.log(peek(pq),' '); pq = pop(pq); } // Denne koden er bidratt av ishankhandelwals.> |
>
>Produksjon
6 5 4 7>
Se denne artikkelen for mer informasjon.
Merk: Vi kan også bruke Linked List, tidskompleksiteten til alle operasjoner med koblet liste forblir den samme som array. Fordelen med lenket liste er slettHighestPriority() kan være mer effektivt siden vi ikke trenger å flytte varer.
3) Implementer prioritert kø ved å bruke heaps:
Binary Heap er generelt foretrukket for implementering av prioritert kø fordi heaps gir bedre ytelse sammenlignet med arrays eller LinkedList. Med tanke på egenskapene til en haug, er oppføringen med den største nøkkelen på toppen og kan fjernes umiddelbart. Det vil imidlertid ta tid O(log n) å gjenopprette heap-egenskapen for de gjenværende nøklene. Men hvis en annen oppføring skal settes inn umiddelbart, kan noe av denne tiden kombineres med O(log n)-tiden som trengs for å sette inn den nye oppføringen. Representasjonen av en prioritert kø som en haug viser seg således fordelaktig for stor n, siden den er representert effektivt i sammenhengende lagring og garantert krever kun logaritmisk tid for både innsettinger og slettinger. Operasjoner på Binary Heap er som følger:
- insert(p): Setter inn et nytt element med prioritet p. extractMax(): Trekker ut et element med maksimal prioritet. remove(i): Fjerner et element pekt av en iterator i. getMax(): Returnerer et element med maksimal prioritet. changePriority(i, p): Endrer prioriteten til et element pekt av i til s .
| Binær haug | sett inn() | fjerne() | kikke() |
|---|---|---|---|
| Tidskompleksitet | O(log n) | O(log n) | O(1) |
Se denne artikkelen for kodeimplementering.
4) Implementer prioritert kø ved å bruke binært søketre:
Et selvbalanserende binært søketre som AVL-tre, rød-svart tre, etc. kan også brukes til å implementere en prioritert kø. Operasjoner som peek(), insert() og delete() kan utføres ved å bruke BST.
| Binært søketre | kikke() | sett inn() | slett() |
|---|---|---|---|
| Tidskompleksitet | O(1) | O(log n) | O(log n) |
Søknader av prioritert kø:
- CPU-planlegging
- Grafalgoritmer som Dijkstras korteste vei-algoritme, Prim's Minimum Spanning Tree, etc.
- Stackimplementering
- Alle applikasjoner med prioritert kø
- Prioritetskø i C++
- Prioritetskø i Java
- Prioritetskø i Python
- Prioritetskø i JavaScript
- Nylige artikler om Priority Queue!