A prioriterad kö är en typ av kö som ordnar element baserat på deras prioritetsvärden. Element med högre prioritetsvärden hämtas vanligtvis före element med lägre prioritetsvärden.
I en prioritetskö har varje element ett prioritetsvärde kopplat till sig. När du lägger till ett element i kön infogas det i en position baserat på dess prioritetsvärde. Till exempel, om du lägger till ett element med ett högt prioritetsvärde till en prioritetskö, kan det infogas nära framsidan av kön, medan ett element med ett lågt prioritetsvärde kan infogas nära baksidan.
Det finns flera sätt att implementera en prioritetskö, inklusive att använda en array, länkad lista, heap eller binärt sökträd. Varje metod har sina egna fördelar och nackdelar, och det bästa valet beror på de specifika behoven för din applikation.
Prioriterade köer används ofta i realtidssystem, där ordningsföljden i vilka element bearbetas kan få betydande konsekvenser. De används också i algoritmer för att förbättra deras effektivitet, som t.ex Dijkstras algoritm för att hitta den kortaste vägen i en graf och A*-sökalgoritmen för sökväg.
Egenskaper för prioriterad kö
Så en prioriterad kö är en förlängning av kö med följande egenskaper.
- Varje objekt har en prioritet kopplad till sig.
- Ett element med hög prioritet tas ur kö före ett element med låg prioritet.
- Om två element har samma prioritet serveras de enligt deras ordning i kön.
I prioritetskön nedan kommer ett element med ett maximalt ASCII-värde att ha högsta prioritet. Elementen med högre prioritet serveras först.
Hur tilldelas prioritet till elementen i en prioritetskö?
I en prioritetskö övervägs i allmänhet värdet av ett element för att tilldela prioritet.
Till exempel tilldelas elementet med det högsta värdet högst prioritet och elementet med det lägsta värdet tilldelas lägst prioritet. Det omvända fallet kan också användas, dvs elementet med det lägsta värdet kan tilldelas högsta prioritet. Prioriteten kan också tilldelas efter våra behov.
Funktioner för en prioriterad kö:
En typisk prioritetskö stöder följande operationer:
1) Infoga i en prioriterad kö
När ett nytt element infogas i en prioritetskö flyttas det till den tomma luckan uppifrån och ned och från vänster till höger. Men om elementet inte är på rätt plats kommer det att jämföras med den överordnade noden. Om elementet inte är i rätt ordning byts elementen. Bytesprocessen fortsätter tills alla element är placerade i rätt position.
2) Radering i en prioriterad kö
Som du vet är det maximala elementet rotnoden i en maxhög. Och det kommer att ta bort elementet som har maximal prioritet först. Således tar du bort rotnoden från kön. Denna borttagning skapar en tom plats, som kommer att fyllas ytterligare med ny infogning. Sedan jämför den det nyligen infogade elementet med alla element i kön för att bibehålla högen invariant.
3) Kika i en prioriterad kö
Denna operation hjälper till att returnera maxelementet från Max Heap eller minimumelementet från Min Heap utan att ta bort noden från prioritetskön.
Typer av prioriterade köer:
1) Prioritetskö i stigande ordning
Som namnet antyder, i stigande prioritetskö, får elementet med ett lägre prioritetsvärde högre prioritet i prioritetslistan. Till exempel, om vi har följande element i en prioritetskö ordnade i stigande ordning som 4,6,8,9,10. Här är 4 det minsta antalet, därför kommer det att få högsta prioritet i en prioritetskö och så när vi tar ur kö från den här typen av prioritetskö, kommer 4 att tas bort från kön och dequeue returnerar 4.
2) Prioritetskö i fallande ordning
Rotnoden är det maximala elementet i en maxhög, som du kanske vet. Det kommer också att ta bort elementet med högst prioritet först. Som ett resultat tas rotnoden bort från kön. Denna radering lämnar ett tomt utrymme, som kommer att fyllas med nya infogningar i framtiden. Höginvarianten upprätthålls sedan genom att jämföra det nyligen infogade elementet med alla andra poster i kön.
Typer av prioriterade köer
Skillnad mellan Priority Queue och Normal Queue?
Det finns ingen prioritet kopplad till element i en kö, regeln först-in-först-ut (FIFO) implementeras medan elementen i en prioritetskö har prioritet. Elementen med högre prioritet serveras först.
Hur implementerar man Priority Queue?
Prioritetskö kan implementeras med hjälp av följande datastrukturer:
- Arrayer
- Länkad lista
- Hög datastruktur
- Binärt sökträd
Låt oss diskutera alla dessa i detalj.
1) Implementera Priority Queue med Array:
En enkel implementering är att använda en array med följande struktur.
struct item {
int objekt;
int prioritet;
}
- enqueue(): Denna funktion används för att infoga ny data i kön. dequeue(): Denna funktion tar bort elementet med högst prioritet från kön. peek()/top(): Denna funktion används för att få det högsta prioritetselementet i kön utan att ta bort det från kön.
| Arrayer | enqueue() | följaktligen () | titt() |
|---|---|---|---|
| Tidskomplexitet | 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> |
>
>
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> |
>
>Produktion
16 14 12>
Notera: Läsa Denna artikel för mer detaljer.
2) Implementera prioriterad kö med länkad lista:
I en LinkedList-implementering sorteras posterna i fallande ordning baserat på deras prioritet. Det högsta prioritetselementet läggs alltid till längst fram i prioritetskön, som bildas med hjälp av länkade listor. Funktionerna som skjuta på() , pop() , och titt() används för att implementera en prioritetskö med hjälp av en länkad lista och förklaras enligt följande:
- push(): Denna funktion används för att infoga ny data i kön. pop(): Denna funktion tar bort elementet med högst prioritet från kön. peek() / top(): Denna funktion används för att få det högsta prioritetselementet i kön utan att ta bort det från kön.
| Länkad lista | skjuta på() | pop() | titt() |
|---|---|---|---|
| Tidskomplexitet | 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ästa = 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ästa;> >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)->priority // Infoga ny nod före head temp->next = *head; (*huvud) = temp; } else { // Gå igenom listan och hitta en //-position för att infoga ny nod medan (start->nästa != NULL && start->nästa->prioritet> p) { start = start->nästa; } // Antingen i slutet av listan // eller vid önskad position temp->next = start->next; start->nästa = temp; } } // Funktionen att kontrollera om listan är tom int isEmpty(Node** huvud) { return (*huvud) == NULL; } // Driver code int main() { // Skapa en prioriterad 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.next; } // Antingen i slutet av listan // eller vid önskad position temp.next = start.next; start.next = temp; } returnera huvudet; } // Funktionen att kontrollera att listan är tom statisk int isEmpty(Nodhuvud) { return ((huvud) == 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 ', peek(pq)); pq=pop(pq); } } } // Denna kod är bidragit från ishankhandelwals.> |
>
>
Pytonorm
# 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ärde, prioritet) newNode.next = temp.next temp.next = newNode # Returnerar 1 för framgångsrik exekvering return 1 # Metod för att ta bort högprioritet objekt # från Prioritetskön def pop(self): # Villkorskontroll för kontroll # Prioritetskö är tom eller inte om self.isEmpty() == True: return else: # Tar bort nod med hög prioritet från # Priority Queue och uppdaterar front # med nästa nod self.front = self.front.next return 1 # Metod för att returnera nod med hög prioritet # värde Tar inte bort den def peek(self): # Tillståndskontroll för kontroll av Prioritet # Kön är tom eller inte om self.isEmpty() == True: return else: return self.front.data # Metod för att gå igenom prioritet # Queue def travverse(self): # Villkorskontroll för kontroll av prioritet # Kön är tom eller inte om self.isEmpty() == True: return ' Kön är tom!' else: temp = self.front while temp: print(temp.data, end=' ') temp = temp.next # Driver code if _name_ == '_main_': # Skapar en instans av Priority # Queue, och lägga till värden # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push(4, 1) pq.push(5, 2) pq.push(6, 3) pq .push(7, 0) # Går igenom prioritetskön pq.traverse() # Tar bort objekt med högsta prioritet # för prioritetskön 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) { start = start.next; } // Antingen i slutet av listan // eller vid önskad position temp.next = start.next; start.next = temp; } returnera huvudet; } // Funktionen att kontrollera är att listan är tom offentlig statisk int isEmpty(Nodhuvud) { return ((huvud) == 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} ', peek(pq)); pq = pop(pq); } } } // Denna kod är bidragit från 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; } // Antingen i slutet av listan // eller vid önskad position temp.next = start.next; start.next = temp; } returnera huvudet; } // Funktionen att kontrollera att listan är tom funktion isEmpty(head) { return head == null ? 1:0; } // Drivrutinskod // Skapa en prioriterad 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); } // Denna kod är bidragit från ishankhandelwals.> |
alfa beta beskärning
>
>Produktion
6 5 4 7>
Se den här artikeln för mer information.
Notera: Vi kan också använda länkad lista, tidskomplexiteten för alla operationer med länkad lista förblir densamma som array. Fördelen med länkad lista är deleteHighestPriority() kan vara effektivare eftersom vi inte behöver flytta föremål.
3) Implementera prioriterad kö med hjälp av heaps:
Binary Heap är i allmänhet att föredra för implementering av prioriterad kö eftersom heaps ger bättre prestanda jämfört med arrayer eller LinkedList. Med tanke på egenskaperna hos en hög, är posten med den största nyckeln på toppen och kan tas bort omedelbart. Det kommer dock att ta tid O(log n) att återställa heap-egenskapen för de återstående nycklarna. Men om en annan post ska infogas omedelbart, kan en del av denna tid kombineras med O(log n)-tiden som behövs för att infoga den nya posten. Sålunda visar sig representationen av en prioritetskö som en heap vara fördelaktig för stora n, eftersom den representeras effektivt i angränsande lagring och garanterat kräver endast logaritmisk tid för både infogningar och borttagningar. Operationer på Binary Heap är som följer:
- infoga(p): Infogar ett nytt element med prioritet p. extractMax(): Extraherar ett element med maximal prioritet. remove(i): Tar bort ett element som pekas av en iterator i. getMax(): Returnerar ett element med maximal prioritet. changePriority(i, p): Ändrar prioriteten för ett element som pekas av i till sid .
| Binär hög | Föra in() | avlägsna() | titt() |
|---|---|---|---|
| Tidskomplexitet | O(log n) | O(log n) | O(1) |
Se den här artikeln för kodimplementering.
4) Implementera prioriterad kö med binärt sökträd:
Ett självbalanserande binärt sökträd som AVL-träd, röd-svart träd, etc. kan också användas för att implementera en prioritetskö. Operationer som peek(), insert() och delete() kan utföras med BST.
| Binärt sökträd | titt() | Föra in() | radera() |
|---|---|---|---|
| Tidskomplexitet | O(1) | O(log n) | O(log n) |
Applikationer av Priority Queue:
- CPU-schemaläggning
- Grafalgoritmer som Dijkstras algoritm för kortaste väg, Prim's Minimum Spanning Tree, etc.
- Stackimplementering
- Alla applikationer av Priority Queue
- Prioritetskö i C++
- Prioritetskö i Java
- Prioritetskö i Python
- Prioritetskö i JavaScript
- Nya artiklar om Priority Queue!