A prednostna čakalna vrsta je vrsta čakalne vrste, ki razporeja elemente glede na njihove prioritetne vrednosti. Elementi z višjimi prednostnimi vrednostmi so običajno pridobljeni pred elementi z nižjimi prednostnimi vrednostmi.
V prednostni čakalni vrsti ima vsak element povezano prednostno vrednost. Ko dodate element v čakalno vrsto, se vstavi na položaj glede na njegovo prednostno vrednost. Na primer, če v prednostno čakalno vrsto dodate element z visoko prednostno vrednostjo, bo morda vstavljen v sprednji del čakalne vrste, medtem ko bo element z nizko prednostno vrednostjo lahko vstavljen blizu zadnjega dela.
Obstaja več načinov za implementacijo prednostne čakalne vrste, vključno z uporabo matrike, povezanega seznama, kopice ali binarnega iskalnega drevesa. Vsaka metoda ima svoje prednosti in slabosti, najboljša izbira pa bo odvisna od posebnih potreb vaše aplikacije.
pretvorba java niza v celo število
Prednostne čakalne vrste se pogosto uporabljajo v sistemih v realnem času, kjer ima lahko vrstni red obdelave elementov pomembne posledice. Uporabljajo se tudi v algoritmih za izboljšanje njihove učinkovitosti, kot npr Dijkstrajev algoritem za iskanje najkrajše poti v grafu in iskalni algoritem A* za iskanje poti.
Lastnosti prednostne čakalne vrste
Torej je prednostna čakalna vrsta razširitev čakalna vrsta z naslednjimi lastnostmi.
- Vsak element ima z njim povezano prednost.
- Element z visoko prioriteto je izključen iz čakalne vrste pred elementom z nizko prioriteto.
- Če imata dva elementa enako prioriteto, se strežeta glede na njihov vrstni red v čakalni vrsti.
V spodnji prednostni čakalni vrsti bo imel najvišjo prednost element z najvišjo vrednostjo ASCII. Prvi so postreženi elementi z višjo prioriteto.
Kako je prioriteta dodeljena elementom v prednostni čakalni vrsti?
V prednostni čakalni vrsti se na splošno pri dodeljevanju prioritete upošteva vrednost elementa.
Na primer, elementu z najvišjo vrednostjo je dodeljena najvišja prednost, elementu z najnižjo vrednostjo pa najnižja prednost. Lahko se uporabi tudi obratni primer, tj. elementu z najnižjo vrednostjo se lahko dodeli najvišja prioriteta. Prav tako se lahko dodeli prednost glede na naše potrebe.
Operacije prednostne čakalne vrste:
Tipična prednostna čakalna vrsta podpira naslednje operacije:
1) Vstavljanje v prednostno čakalno vrsto
Ko je nov element vstavljen v prednostno čakalno vrsto, se premakne v prazno režo od zgoraj navzdol in od leve proti desni. Če pa element ni na pravem mestu, bo primerjan z nadrejenim vozliščem. Če element ni v pravilnem vrstnem redu, se elementi zamenjajo. Postopek zamenjave se nadaljuje, dokler niso vsi elementi nameščeni v pravilnem položaju.
2) Brisanje v prednostni čakalni vrsti
Kot veste, je v največji kopici največji element korensko vozlišče. In prvi bo odstranil element, ki ima največjo prednost. Tako odstranite korensko vozlišče iz čakalne vrste. Ta odstranitev ustvari prazno režo, ki bo dodatno zapolnjena z novim vstavkom. Nato primerja na novo vstavljeni element z vsemi elementi znotraj čakalne vrste, da ohrani nespremenljivost kopice.
3) Pokukajte v prednostno čakalno vrsto
Ta operacija pomaga vrniti največji element iz Max Heap ali najmanjši element iz Min Heap, ne da bi izbrisali vozlišče iz prednostne čakalne vrste.
Vrste prednostne čakalne vrste:
1) Čakalna vrsta s prednostjo v naraščajočem vrstnem redu
Kot že ime pove, ima v naraščajočem prednostnem vrstnem redu element z nižjo prednostno vrednostjo na prednostnem seznamu višjo prednost. Na primer, če imamo naslednje elemente v prednostni čakalni vrsti, razvrščene v naraščajočem vrstnem redu, kot so 4,6,8,9,10. Tukaj je 4 najmanjše število, zato bo dobilo najvišjo prioriteto v prednostni čakalni vrsti in tako, ko izstopimo iz te vrste prednostne čakalne vrste, bo 4 odstranjeno iz čakalne vrste in dequeue vrne 4.
2) Prednostna čakalna vrsta v padajočem vrstnem redu
Kot morda veste, je korensko vozlišče največji element v največjem kupu. Prav tako bo najprej odstranil element z najvišjo prioriteto. Posledično je korensko vozlišče odstranjeno iz čakalne vrste. Ta izbris pusti prazen prostor, ki bo v prihodnosti zapolnjen z novimi vstavki. Invariant kopice se nato vzdržuje s primerjavo na novo vstavljenega elementa z vsemi drugimi vnosi v čakalni vrsti.
Vrste prednostnih čakalnih vrst
Razlika med prednostno čakalno vrsto in običajno čakalno vrsto?
Elementom v čakalni vrsti ni dodeljene nobene prioritete, izvaja se pravilo prvi vstopi, prvi ven (FIFO), medtem ko imajo v prednostni čakalni vrsti elementi prednost. Prvi so postreženi elementi z višjo prioriteto.
Kako implementirati prednostno čakalno vrsto?
Prednostno čakalno vrsto je mogoče implementirati z uporabo naslednjih podatkovnih struktur:
- Nizi
- Povezan seznam
- Struktura podatkov kopice
- Binarno iskalno drevo
Razpravljajmo o vsem tem podrobno.
1) Izvedite prednostno čakalno vrsto z uporabo polja:
Preprosta izvedba je uporaba niza naslednje strukture.
struct item {
int element;
int prioriteta;
}
- enqueue(): Ta funkcija se uporablja za vstavljanje novih podatkov v čakalno vrsto. dequeue(): Ta funkcija iz čakalne vrste odstrani element z najvišjo prioriteto. peek()/top(): Ta funkcija se uporablja za pridobivanje elementa z najvišjo prioriteto v čakalni vrsti, ne da bi ga odstranili iz čakalne vrste.
| Nizi | v čakalno vrsto () | temu primerno () | pokukati() |
|---|---|---|---|
| Časovna zapletenost | O(1) | O(n) | O(n) |
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> |
c++ razdeli niz
>
>Izhod
16 14 12>
Opomba: Preberi Ta članek za več podrobnosti.
2) Izvedite prednostno čakalno vrsto z uporabo povezanega seznama:
V izvedbi LinkedList so vnosi razvrščeni v padajočem vrstnem redu glede na njihovo prioriteto. Element z najvišjo prioriteto je vedno dodan na začetek prednostne čakalne vrste, ki je oblikovana s pomočjo povezanih seznamov. Funkcije, kot so potisni() , pop() , in pokukati() se uporabljajo za implementacijo prednostne čakalne vrste z uporabo povezanega seznama in so razloženi na naslednji način:
- push(): Ta funkcija se uporablja za vstavljanje novih podatkov v čakalno vrsto. pop(): Ta funkcija odstrani element z najvišjo prioriteto iz čakalne vrste. peek() / top(): Ta funkcija se uporablja za pridobivanje elementa z najvišjo prednostjo v čakalni vrsti, ne da bi ga odstranili iz čakalne vrste.
| Povezan seznam | potisni() | pop() | pokukati() |
|---|---|---|---|
| Časovna zapletenost | O(n) | O(1) | O(1) |
C++
vicky kaushal starost
// 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->podatki = d;> >temp->prioriteta = p;> >temp->naslednji = NULL;> >return> temp;> }> // Return the value at head> int> peek(Node** head) {>return> (*head)->podatki; }> // Removes the element with the> // highest priority form the list> void> pop(Node** head)> {> >Node* temp = *head;> >(*head) = (*head)->naslednji;> >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)->prioriteta // Vstavi novo vozlišče pred glavo temp->next = *head; (*glava) = temp; } else { // Preletite seznam in poiščite // položaj za vstavljanje novega vozlišča while (start->next != NULL && start->next->priority> p) { start = start->next; } // Bodisi na koncu seznama // bodisi na zahtevanem položaju temp->next = start->next; začetek->naslednji = temp; } } // Funkcija za preverjanje, ali je seznam prazen int isEmpty(Node** head) { return (*head) == NULL; } // Koda gonilnika int main() { // Ustvari prednostno čakalno vrsto // 7->4->5->6 Node* pq = newNode(4, 1); potisni(&pq, 5, 2); potisni(&pq, 6, 3); potisni(&pq, 7, 0); medtem ko (!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; } // Bodisi na koncu seznama // bodisi na zahtevanem položaju temp.next = start.next; start.next = temp; } vrni glavo; } // Funkcija za preverjanje, ali je seznam prazen static int isEmpty(Node head) { return ((head) == null)?1:0; } // Koda gonilnika public static void main(String args[]) { // Ustvari prednostno čakalno vrsto // 7.4.5.6 Vozlišče pq = newNode(4, 1); pq = potisni (pq, 5, 2); pq = potisni (pq, 6, 3); pq = potisni (pq, 7, 0); medtem ko (isEmpty(pq)==0) { System.out.printf('%d ', peek(pq)); pq=pop(pq); } } } // To kodo je prispeval ishankhandelwals.> |
>
>
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(value, priority) newNode.next = temp.next temp.next = newNode # Vrnitev 1 za uspešno izvedbo return 1 # Metoda za odstranitev elementa visoke prioritete # iz the Priority Queue def pop(self): # Preverjanje pogoja za preverjanje # Priority Queue je prazna ali ne, če self.isEmpty() == True: return else: # Odstranjevanje vozlišča visoke prioritete iz # Priority Queue in posodabljanje front # z next vozlišče self.front = self.front.next return 1 # Metoda za vrnitev vozlišča visoke prioritete # vrednost Ne odstrani ga def peek(self): # Preverjanje pogoja za preverjanje Priority # Čakalna vrsta je prazna ali ne, če self.isEmpty() == True: return else: return self.front.data # Metoda za prehod skozi Priority # Queue def traverse(self): # Preverjanje pogoja za preverjanje Priority # Čakalna vrsta je prazna ali ne, če self.isEmpty() == True: return ' Čakalna vrsta je prazna!' else: temp = self.front while temp: print(temp.data, end=' ') temp = temp.next # Koda gonilnika if _name_ == '_main_': # Ustvarjanje primerek Priority # Queue in dodajanje vrednosti # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push(4, 1) pq.push(5, 2) pq.push(6, 3) pq .push(7, 0) # Prehod skozi prednostno čakalno vrsto pq.traverse() # Odstranjevanje elementa z najvišjo prednostjo # za prednostno čakalno vrsto 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; } // Bodisi na koncu seznama // bodisi na zahtevanem položaju temp.next = start.next; start.next = temp; } vrni glavo; } // Funkcija za preverjanje, ali je seznam prazen public static int isEmpty(Node head) { return ((head) == null)? 1 : 0; } // Koda gonilnika public static void Main(string[] args) { // Ustvari prednostno čakalno vrsto // 7.4.5.6 Vozlišče pq = newNode(4, 1); pq = potisni (pq, 5, 2); pq = potisni (pq, 6, 3); pq = potisni (pq, 7, 0); medtem ko (isEmpty(pq) == 0) { Console.Write('{0:D} ', peek(pq)); pq = pop(pq); } } } // To kodo je prispeval ishankhandelwals.> |
>
>
Javascript
.06 kot ulomek
// 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; } // Bodisi na koncu seznama // bodisi na zahtevanem položaju temp.next = start.next; start.next = temp; } vrni glavo; } // Funkcija za preverjanje, ali je seznam prazen function isEmpty(head) { return head == null? 1 : 0; } // Koda gonilnika // Ustvari prednostno čakalno vrsto // 7.4.5.6 var pq = newNode(4, 1); pq = potisni (pq, 5, 2); pq = potisni (pq, 6, 3); pq = potisni (pq, 7, 0); medtem ko (isEmpty(pq) == 0) { console.log(peek(pq),' '); pq = pop(pq); } // To kodo je prispeval ishankhandelwals.> |
>
>Izhod
6 5 4 7>
Za več podrobnosti glejte ta članek.
Opomba: Uporabimo lahko tudi Linked List, časovna kompleksnost vseh operacij s povezanim seznamom ostane enaka kot pri matriki. Prednost povezanega seznama je deleteHighestPriority() je lahko bolj učinkovito, saj nam ni treba premikati predmetov.
3) Izvedite prednostno čakalno vrsto z uporabo kopic:
Binarna kopica je na splošno prednostna za implementacijo prednostne čakalne vrste, ker kopice zagotavljajo boljšo zmogljivost v primerjavi z nizi ali LinkedList. Glede na lastnosti kopice je vnos z največjim ključem na vrhu in ga je mogoče takoj odstraniti. Za obnovitev lastnosti kopice za preostale ključe pa bo potreben čas O(log n). Če pa je treba takoj vstaviti drug vnos, se lahko del tega časa združi s časom O(log n), potrebnim za vstavljanje novega vnosa. Tako se predstavitev prednostne čakalne vrste kot kopice izkaže za prednostno za veliko n, saj je učinkovito predstavljena v neprekinjenem pomnilniku in je zagotovljeno, da zahteva samo logaritemski čas za vstavljanje in brisanje. Operacije na binarni kopici so naslednje:
- insert(p): Vstavi nov element s prednostjo p. extractMax(): ekstrahira element z največjo prednostjo. remove(i): Odstrani element, na katerega kaže iterator i. getMax(): vrne element z največjo prednostjo. changePriority(i, p): spremeni prioriteto elementa, na katerega kaže i do str .
| Binarna kopica | vstavi() | Odstrani() | pokukati() |
|---|---|---|---|
| Časovna zapletenost | O(log n) | O(log n) | O(1) |
Glejte ta članek za implementacijo kode.
4) Implementirajte prednostno čakalno vrsto z binarnim iskalnim drevesom:
Za implementacijo prednostne čakalne vrste je mogoče uporabiti tudi samouravnoteženo binarno iskalno drevo, kot je drevo AVL, rdeče-črno drevo itd. Operacije, kot so peek(), insert() in delete(), se lahko izvedejo z BST.
| Binarno iskalno drevo | pokukati() | vstavi() | izbrisati() |
|---|---|---|---|
| Časovna zapletenost | O(1) | O(log n) | O(log n) |
Aplikacije prednostne čakalne vrste:
- Razporejanje procesorja
- Grafirajte algoritme, kot je Dijkstrajev algoritem najkrajše poti, Primovo minimalno vpeto drevo itd.
- Implementacija sklada
- Vse aplikacije prednostne čakalne vrste
- Prednostna čakalna vrsta v C++
- Prednostna čakalna vrsta v Javi
- Prednostna čakalna vrsta v Pythonu
- Prednostna čakalna vrsta v JavaScriptu
- Nedavni članki o prednostni čakalni vrsti!