EN prioriteret kø er en type kø, der arrangerer elementer baseret på deres prioritetsværdier. Elementer med højere prioritetsværdier hentes typisk før elementer med lavere prioritetsværdier.
I en prioritetskø har hvert element en prioritetsværdi tilknyttet. Når du tilføjer et element til køen, indsættes det i en position baseret på dets prioritetsværdi. Hvis du f.eks. tilføjer et element med en høj prioritetsværdi til en prioritetskø, kan det indsættes tæt foran køen, mens et element med en lav prioritetsværdi kan indsættes tæt på bagsiden.
Der er flere måder at implementere en prioritetskø på, herunder at bruge et array, linket liste, heap eller binært søgetræ. Hver metode har sine egne fordele og ulemper, og det bedste valg vil afhænge af de specifikke behov for din applikation.
Prioritetskøer bruges ofte i realtidssystemer, hvor rækkefølgen, som elementer behandles i, kan have betydelige konsekvenser. De bruges også i algoritmer til at forbedre deres effektivitet, som f.eks Dijkstras algoritme til at finde den korteste vej i en graf og A*-søgealgoritmen til at finde vej.
Egenskaber for prioriteret kø
Så en prioriteret kø er en forlængelse af kø med følgende egenskaber.
- Hvert element har en prioritet forbundet med det.
- Et element med høj prioritet sættes ud af kø før et element med lav prioritet.
- Hvis to elementer har samme prioritet, serveres de i henhold til deres rækkefølge i køen.
I nedenstående prioritetskø vil et element med en maksimal ASCII-værdi have den højeste prioritet. Elementerne med højere prioritet serveres først.
Hvordan tildeles prioritet til elementerne i en prioritetskø?
I en prioritetskø bliver værdien af et element generelt taget i betragtning ved tildeling af prioritet.
For eksempel tildeles elementet med den højeste værdi den højeste prioritet, og elementet med den laveste værdi tildeles den laveste prioritet. Det omvendte tilfælde kan også bruges, dvs. elementet med den laveste værdi kan tildeles den højeste prioritet. Prioriteten kan også tildeles efter vores behov.
Funktioner af en prioriteret kø:
En typisk prioritetskø understøtter følgende handlinger:
1) Indsættelse i en prioriteret kø
Når et nyt element indsættes i en prioritetskø, flyttes det til den tomme plads fra top til bund og venstre mod højre. Men hvis elementet ikke er på det rigtige sted, vil det blive sammenlignet med det overordnede node. Hvis elementet ikke er i den rigtige rækkefølge, byttes elementerne. Udskiftningsprocessen fortsætter, indtil alle elementer er placeret i den korrekte position.
2) Sletning i en prioriteret kø
Som du ved, at i en max heap er det maksimale element rodnoden. Og det vil fjerne det element, der har maksimal prioritet først. Således fjerner du rodnoden fra køen. Denne fjernelse skaber en tom spalte, som vil blive yderligere fyldt med ny indsættelse. Derefter sammenligner den det nyligt indsatte element med alle elementerne inde i køen for at bevare heap-invarianten.
3) Kig ind i en prioriteret kø
Denne operation hjælper med at returnere det maksimale element fra Max Heap eller minimumselementet fra Min Heap uden at slette noden fra prioritetskøen.
Typer af prioriteret kø:
1) Prioritetskø i stigende rækkefølge
Som navnet antyder, i stigende prioritetskø, får elementet med en lavere prioritetsværdi en højere prioritet i prioritetslisten. For eksempel, hvis vi har følgende elementer i en prioritetskø arrangeret i stigende rækkefølge som 4,6,8,9,10. Her er 4 det mindste tal, derfor vil det få den højeste prioritet i en prioritetskø, og så når vi dekøer fra denne type prioritetskø, vil 4 fjernes fra køen og dequeue returnerer 4.
2) Prioritetskø i faldende rækkefølge
Rodnoden er det maksimale element i en max heap, som du måske ved. Det vil også fjerne elementet med den højeste prioritet først. Som et resultat fjernes rodnoden fra køen. Denne sletning efterlader et tomt rum, som vil blive fyldt med nye indsættelser i fremtiden. Heap-invarianten vedligeholdes derefter ved at sammenligne det nyligt indsatte element med alle andre poster i køen.
print fra java
Typer af prioriterede køer
Forskellen mellem Priority Queue og Normal Queue?
Der er ingen prioritet knyttet til elementer i en kø, reglen om først-ind-først-ud (FIFO) er implementeret, hvorimod elementerne i en prioritetskø har en prioritet. Elementerne med højere prioritet serveres først.
Hvordan implementerer man Priority Queue?
Prioritetskø kan implementeres ved hjælp af følgende datastrukturer:
- Arrays
- Linket liste
- Heap datastruktur
- Binært søgetræ
Lad os diskutere alle disse i detaljer.
1) Implementer Priority Queue ved hjælp af Array:
En simpel implementering er at bruge en række af følgende struktur.
struct element {
int vare;
int prioritet;
}
- enqueue(): Denne funktion bruges til at indsætte nye data i køen. dequeue(): Denne funktion fjerner elementet med den højeste prioritet fra køen. peek()/top(): Denne funktion bruges til at få det højeste prioritetselement i køen uden at fjerne det fra køen.
| Arrays | kø() | derfor () | kig() |
|---|---|---|---|
| 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> |
hvordan man konverterer streng til heltal java
>
>
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> |
>
rekha alder
>Produktion
16 14 12>
Bemærk: Læs denne artikel for flere detaljer.
2) Implementer prioritetskø ved hjælp af linket liste:
I en LinkedList-implementering sorteres posterne i faldende rækkefølge baseret på deres prioritet. Det højeste prioritetselement tilføjes altid forrest i prioritetskøen, som dannes ved hjælp af linkede lister. Funktionerne som skubbe() , pop() , og kig() bruges til at implementere en prioritetskø ved hjælp af en sammenkædet liste og forklares som følger:
- push(): Denne funktion bruges til at indsætte nye data i køen. pop(): Denne funktion fjerner elementet med den højeste prioritet fra køen. peek() / top(): Denne funktion bruges til at få det højeste prioritetselement i køen uden at fjerne det fra køen.
| Linket liste | skubbe() | pop() | kig() |
|---|---|---|---|
| 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->næste = 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)->næste;> >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 // Indsæt ny node før hoved temp->næste = *hoved; (*hoved) = temp; } else { // Gå gennem listen og find en //-position for at indsætte ny node, mens (start->næste != NULL && start->næste->prioritet> p) { start = start->næste; } // Enten i slutningen af listen // eller på den ønskede position temp->next = start->next; start->næste = temp; } } // Funktion, der skal kontrolleres, om listen er tom int isEmpty(Node** hoved) { return (*hoved) == NULL; } // Driverkode int main() { // Create a Priority Queue // 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.next; } // Enten i slutningen af listen // eller på den ønskede position temp.next = start.next; start.next = temp; } returnere hovedet; } // Funktion, der skal kontrolleres, om listen er tom statisk int isEmpty(Knudehoved) { return ((hoved) == 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 ', kig(pq)); pq=pop(pq); } } } // Denne kode er bidraget af 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(værdi, prioritet) newNode.next = temp.next temp.next = newNode # Returnerer 1 for vellykket udførelse return 1 # Metode til at fjerne højprioritet element # fra Prioritetskøen def pop(selv): # Betingelsestjek for kontrol # Prioritetskø er tom eller ej, hvis self.isEmpty() == True: return else: # Fjerner node med høj prioritet fra # Prioritetskø og opdaterer front # med næste node self.front = self.front.next return 1 # Metode til at returnere node med høj prioritet # værdi Fjerner den ikke def peek(self): # Betingelsestjek for kontrol af Prioritet # Køen er tom eller ej, hvis self.isEmpty() == True: return else: return self.front.data # Metode til at gå gennem prioritet # Kø def travers(selv): # Betingelsestjek til kontrol af prioritet # Kø er tom eller ej, hvis self.isEmpty() == True: return ' Køen er tom!' andet: temp = self.front mens temp: print(temp.data, end=' ') temp = temp.next # Driverkode hvis _name_ == '_main_': # Oprettelse af en forekomst af Priority # Queue, og tilføjelse af værdier # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push(4, 1) pq.push(5, 2) pq.push(6, 3) pq .push(7, 0) # Gennemgang gennem prioritetskø pq.traverse() # Fjerner element med højeste prioritet # for prioritetskø pq.pop()> |
>
>
C#
java konverter streng til heltal
// 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.next; } // Enten i slutningen af listen // eller på den ønskede position temp.next = start.next; start.next = temp; } returnere hovedet; } // Funktion, der skal kontrolleres, om listen er tom offentlig statisk int isEmpty(Node head) { 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} ', kig(pq)); pq = pop(pq); } } } // Denne kode er bidraget af 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.next; } // Enten i slutningen af listen // eller på den ønskede position temp.next = start.next; start.next = temp; } returnere hovedet; } // Funktion, der skal kontrolleres, om listen er tom funktion isEmpty(head) { return head == null ? 1:0; } // Driverkode // Opret en prioritetskø // 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 kode er bidraget af ishankhandelwals.> |
>
>Produktion
6 5 4 7>
Se denne artikel for flere detaljer.
Bemærk: Vi kan også bruge linket liste, tidskompleksiteten af alle operationer med linket liste forbliver den samme som matrix. Fordelen med linket liste er sletHighestPriority() kan være mere effektivt, da vi ikke skal flytte varer.
3) Implementer prioritetskø ved hjælp af heaps:
Binary Heap foretrækkes generelt til prioritetskøimplementering, fordi heaps giver bedre ydeevne sammenlignet med arrays eller LinkedList. I betragtning af egenskaberne af en bunke, er indgangen med den største nøgle øverst og kan fjernes med det samme. Det vil dog tage tid O(log n) at gendanne heap-egenskaben for de resterende nøgler. Men hvis en anden post skal indsættes med det samme, så kan noget af denne tid kombineres med den O(log n) tid, der er nødvendig for at indsætte den nye post. Repræsentationen af en prioritetskø som en heap viser sig således at være fordelagtig for store n, da den er repræsenteret effektivt i sammenhængende lagring og garanteret kun kræver logaritmisk tid for både indsættelser og sletninger. Operationer på Binary Heap er som følger:
- insert(p): Indsætter et nyt element med prioritet p. extractMax(): Udtrækker et element med maksimal prioritet. remove(i): Fjerner et element, der peges af en iterator i. getMax(): Returnerer et element med maksimal prioritet. changePriority(i, p): Ændrer prioriteten af et element, der peges af i til s .
| Binær bunke | indsæt() | fjerne() | kig() |
|---|---|---|---|
| Tidskompleksitet | O(log n) | O(log n) | O(1) |
Se denne artikel for kodeimplementering.
4) Implementer prioritetskø ved hjælp af binært søgetræ:
Et selvbalancerende binært søgetræ som AVL-træ, rød-sort træ osv. kan også bruges til at implementere en prioriteret kø. Operationer som peek(), insert() og delete() kan udføres ved hjælp af BST.
| Binært søgetræ | kig() | indsæt() | slet() |
|---|---|---|---|
| Tidskompleksitet | O(1) | O(log n) | O(log n) |
Ansøgninger om prioriteret kø:
- CPU-planlægning
- Grafalgoritmer som Dijkstras korteste vejalgoritme, Prim's Minimum Spanning Tree osv.
- Stakimplementering
- Alle applikationer med prioriteret kø
- Prioritetskø i C++
- Prioritetskø i Java
- Prioritetskø i Python
- Prioritetskø i JavaScript
- Seneste artikler om Priority Queue!