A prioritný rad je typ frontu, ktorý usporiada prvky na základe ich hodnôt priority. Prvky s vyššou prioritou sa zvyčajne získavajú pred prvkami s nižšou prioritou.
V prioritnom fronte má každý prvok priradenú hodnotu priority. Keď pridáte prvok do frontu, vloží sa na pozíciu podľa hodnoty priority. Ak napríklad pridáte prvok s hodnotou s vysokou prioritou do frontu priority, môže byť vložený blízko prednej časti frontu, zatiaľ čo prvok s hodnotou s nízkou prioritou môže byť vložený blízko zadnej časti.
Existuje niekoľko spôsobov, ako implementovať prioritný front, vrátane použitia poľa, prepojeného zoznamu, haldy alebo binárneho vyhľadávacieho stromu. Každá metóda má svoje výhody a nevýhody a najlepšia voľba bude závisieť od konkrétnych potrieb vašej aplikácie.
Prioritné fronty sa často používajú v systémoch v reálnom čase, kde poradie, v ktorom sa prvky spracovávajú, môže mať významné dôsledky. Používajú sa aj v algoritmoch na zlepšenie ich účinnosti, ako napr Dijkstrov algoritmus na nájdenie najkratšej cesty v grafe a vyhľadávací algoritmus A* na hľadanie cesty.
Vlastnosti prioritného frontu
Takže prioritný front je rozšírením frontu s nasledujúcimi vlastnosťami.
- Každá položka má priradenú prioritu.
- Prvok s vysokou prioritou je vyradený pred prvok s nízkou prioritou.
- Ak majú dva prvky rovnakú prioritu, obslúžia sa podľa poradia vo fronte.
V nižšie uvedenom prioritnom rade bude mať prvok s maximálnou hodnotou ASCII najvyššiu prioritu. Prvky s vyššou prioritou sú obsluhované ako prvé.
Ako je priradená priorita prvkom v prioritnom fronte?
Vo fronte priority sa vo všeobecnosti berie do úvahy hodnota prvku pri priraďovaní priority.
Napríklad prvok s najvyššou hodnotou má priradenú najvyššiu prioritu a prvok s najnižšou hodnotou má priradenú najnižšiu prioritu. Je možné použiť aj opačný prípad, t. j. prvku s najnižšou hodnotou možno priradiť najvyššiu prioritu. Prioritu je tiež možné priradiť podľa našich potrieb.
Operácie prioritného frontu:
Typický prioritný front podporuje nasledujúce operácie:
1) Vloženie do prioritného frontu
Keď je nový prvok vložený do prioritného frontu, presunie sa do prázdneho slotu zhora nadol a zľava doprava. Ak však prvok nie je na správnom mieste, porovná sa s nadradeným uzlom. Ak prvok nie je v správnom poradí, prvky sa vymenia. Proces výmeny pokračuje, kým nie sú všetky prvky umiestnené v správnej polohe.
2) Vymazanie v prioritnom rade
Ako viete, v maximálnej hromade je maximálnym prvkom koreňový uzol. A najskôr odstráni prvok, ktorý má maximálnu prioritu. Takto odstránite koreňový uzol z frontu. Týmto odstránením sa vytvorí prázdna štrbina, ktorá bude ďalej vyplnená novým vložením. Potom porovná novo vložený prvok so všetkými prvkami vo fronte, aby sa zachovala invariantnosť haldy.
3) Pozrite sa do prioritného frontu
Táto operácia pomáha vrátiť maximálny prvok z maximálnej haldy alebo minimálny prvok z minimálnej haldy bez vymazania uzla z prioritného frontu.
Typy prioritného frontu:
1) Priorita vzostupného poradia
Ako už názov napovedá, vo fronte priority vzostupného poradia má prvok s nižšou prioritou v zozname priorít vyššiu prioritu. Napríklad, ak máme nasledujúce prvky v prioritnom rade usporiadané vo vzostupnom poradí ako 4,6,8,9,10. Tu je 4 najmenšie číslo, preto dostane najvyššiu prioritu v prioritnom fronte, a tak keď vyradíme z tohto typu prioritného frontu, 4 odstráni z frontu a vyradenie vráti 4.
2) Zostupné poradie Prioritné fronty
Ako možno viete, koreňový uzol je maximálny prvok v maximálnej hromade. Najskôr tiež odstráni prvok s najvyššou prioritou. V dôsledku toho sa koreňový uzol odstráni z frontu. Toto vymazanie zanechá prázdne miesto, ktoré sa v budúcnosti zaplní novými vloženiami. Invariant haldy sa potom udržiava porovnaním novo vloženého prvku so všetkými ostatnými položkami vo fronte.
Typy prioritných frontov
Rozdiel medzi prioritným a normálnym frontom?
Nie je priradená priorita prvkom vo fronte, je implementované pravidlo first-in-first-out (FIFO), zatiaľ čo v prioritnom fronte majú prioritu prvky. Prvky s vyššou prioritou sú obsluhované ako prvé.
Ako implementovať prioritný front?
Prioritný front je možné implementovať pomocou nasledujúcich dátových štruktúr:
- Polia
- Prepojený zoznam
- Štruktúra údajov haldy
- Binárny vyhľadávací strom
Rozoberme si to všetko podrobne.
1) Implementujte prioritný front pomocou poľa:
Jednoduchá implementácia je použitie poľa nasledujúcej štruktúry.
struct item {
int položka;
priorita int;
}
- enqueue(): Táto funkcia sa používa na vloženie nových údajov do frontu. dequeue(): Táto funkcia odstráni prvok s najvyššou prioritou z frontu. peek()/top(): Táto funkcia sa používa na získanie prvku s najvyššou prioritou vo fronte bez jeho odstránenia z frontu.
| Polia | zaradiť () | podľa toho () | nahliadnuť () |
|---|---|---|---|
| Časová zložitosť | 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#
premenovať priečinok linux
// 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> |
>
>Výkon
16 14 12>
Poznámka: Čítať tento článok pre viac detailov.
2) Implementujte prioritný zoznam pomocou prepojeného zoznamu:
V implementácii LinkedList sú položky zoradené v zostupnom poradí na základe ich priority. Prvok s najvyššou prioritou sa vždy pridá na začiatok frontu priority, ktorý je vytvorený pomocou prepojených zoznamov. Funkcie ako TAM() , pop() , a nahliadnuť () sa používajú na implementáciu prioritného frontu pomocou prepojeného zoznamu a sú vysvetlené nasledovne:
- push(): Táto funkcia sa používa na vloženie nových údajov do frontu. pop(): Táto funkcia odstráni prvok s najvyššou prioritou z frontu. peek() / top(): Táto funkcia sa používa na získanie prvku s najvyššou prioritou vo fronte bez jeho odstránenia z frontu.
| Prepojený zoznam | TAM() | pop() | nahliadnuť () |
|---|---|---|---|
| Časová zložitosť | O(n) | 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->údaje = d;> >temp->priorita = p;> >temp->dalsi = NULL;> >return> temp;> }> // Return the value at head> int> peek(Node** head) {>return> (*head)->údaje; }> // Removes the element with the> // highest priority form the list> void> pop(Node** head)> {> >Node* temp = *head;> >(*head) = (*head)->ďalej;> >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)->priorita // Vlozit novy uzol pred hlavu temp->next = *head; (*hlava) = teplota; } else { // Prejdite zoznam a nájdite // pozíciu na vloženie nového uzla while (začiatok->ďalší != NULL && začiatok->ďalší->priorita> p) { začiatok = začiatok->ďalší; } // Buď na konci zoznamu // alebo na požadovanej pozícii temp->next = start->next; štart->ďalší = teplota; } } // Funkcia na kontrolu je zoznam prazdny int isEmpty(Node** head) { return (*head) == NULL; } // Kód ovládača int main() { // Vytvorenie prioritného frontu // 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) { začiatok = začiatok.ďalší; } // Buď na konci zoznamu // alebo na požadovanej pozícii temp.next = start.next; start.next = teplota; } vrátiť hlavu; } // Funkcia, ktorá sa má skontrolovať, je zoznam prázdny static int isEmpty(Hlava uzla) { return ((hlava) == null)?1:0; } // Kód ovládača public static void main(String args[]) { // Vytvorenie prioritného frontu // 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); } } } // Do tohto kódu prispeli 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(hodnota, priorita) newNode.next = temp.next temp.next = newNode # Vrátenie 1 pre úspešné vykonanie return 1 # Metóda na odstránenie položky s vysokou prioritou # z the Priority Queue def pop(self): # Kontrola stavu pre kontrolu # Prioritná fronta je prázdna alebo nie, ak self.isEmpty() == True: return else: # Odstránenie uzla s vysokou prioritou z # prioritného frontu a aktualizácia predného # nasledujúcim node self.front = self.front.next return 1 # Metóda na vrátenie uzla s vysokou prioritou # hodnota Neodstráni sa def peek(self): # Kontrola stavu pre kontrolu priority # Front je prázdny alebo nie, ak self.isEmpty() == True: return else: return self.front.data # Metóda na prechod cez prioritu # Queue def traverse(self): # Kontrola stavu pre kontrolu priority # Front je prázdny alebo nie, ak self.isEmpty() == True: return ' Front je prázdny!' else: temp = self.front while temp: print(temp.data, end=' ') temp = temp.next # Kód ovládača if _name_ == '_main_': # Vytvorenie inštancia priority # Queue a pridanie hodnôt # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push(4, 1) pq.push(5, 2) pq.push(6, 3) pq .push(7, 0) # Prechádzanie cez prioritný front pq.traverse() # Odstránenie položky s najvyššou prioritou # pre prioritný front pq.pop()> |
zapuzdrenie java
>
>
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) { začiatok = začiatok.ďalší; } // Buď na konci zoznamu // alebo na požadovanej pozícii temp.next = start.next; start.next = teplota; } vrátiť hlavu; } // Funkcia na kontrolu, či je zoznam prázdny public static int isEmpty(Node head) { return ((head) == null) ? 1:0; } // Kód ovládača public static void Main(string[] args) { // Vytvorenie prioritného frontu // 7.4.5.6 Uzol 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); } } } // Tento kód prispel 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) { začiatok = začiatok.ďalší; } // Buď na konci zoznamu // alebo na požadovanej pozícii temp.next = start.next; start.next = teplota; } vrátiť hlavu; } // Funkcia na kontrolu je zoznam prázdny function isEmpty(head) { return head == null ? 1:0; } // Kód ovládača // Vytvorenie prioritného frontu // 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); } // Do tohto kódu prispeli ishankhandelwals.> |
>
>Výkon
6 5 4 7>
Ďalšie podrobnosti nájdete v tomto článku.
Poznámka: Môžeme použiť aj Linked List, časová náročnosť všetkých operácií s linkovaným zoznamom zostáva rovnaká ako pole. Výhodou prepojeného zoznamu je deleteHighestPriority() môže byť efektívnejší, pretože nemusíme presúvať položky.
3) Implementujte prioritný front pomocou hromady:
Binárna halda je vo všeobecnosti preferovaná pre implementáciu prioritného frontu, pretože haldy poskytujú lepší výkon v porovnaní s poliami alebo LinkedList. Vzhľadom na vlastnosti haldy je záznam s najväčším kľúčom navrchu a možno ho okamžite odstrániť. Obnovenie vlastnosti haldy pre zostávajúce kľúče však potrvá O(log n). Ak sa však má okamžite vložiť ďalší záznam, potom sa časť tohto času môže skombinovať s časom O(log n) potrebným na vloženie nového záznamu. Reprezentácia prioritného radu ako haldy sa teda ukazuje ako výhodná pre veľké n, pretože je efektívne reprezentovaná v súvislom ukladaní a je zaručené, že vyžaduje iba logaritmický čas na vkladanie aj vymazanie. Operácie na binárnej halde sú nasledovné:
- insert(p): Vloží nový prvok s prioritou p. extractMax(): Extrahuje prvok s maximálnou prioritou. remove(i): Odstráni prvok označený iterátorom i. getMax(): Vráti prvok s maximálnou prioritou. changePriority(i, p): Zmení prioritu prvku, na ktorý ukazuje ja k p .
| Binárna halda | vložiť() | odstrániť () | nahliadnuť () |
|---|---|---|---|
| Časová zložitosť | O (log n) | O (log n) | O(1) |
Implementáciu kódu nájdete v tomto článku.
4) Implementujte prioritný front pomocou binárneho vyhľadávacieho stromu:
Samovyvažovací binárny vyhľadávací strom ako AVL strom, Červeno-čierny strom atď. možno použiť aj na implementáciu prioritného frontu. Operácie ako peek(), insert() a delete() možno vykonávať pomocou BST.
| Binárny vyhľadávací strom | nahliadnuť () | vložiť() | vymazať () |
|---|---|---|---|
| Časová zložitosť | O(1) | O (log n) | O (log n) |
Aplikácie prioritného frontu:
- Plánovanie CPU
- Algoritmy grafov, ako je Dijkstrov algoritmus najkratšej cesty, Primov minimálny strom Spanning Tree atď.
- Implementácia zásobníka
- Všetky aplikácie prioritného frontu
- Prioritný front v C++
- Prioritný front v jazyku Java
- Prioritný front v Pythone
- Prioritný front v JavaScripte
- Najnovšie články o prioritnom rade!