A prioritní fronta je typ fronty, která uspořádává prvky na základě jejich prioritních hodnot. Prvky s vyšší prioritou jsou obvykle načteny před prvky s nižší prioritou.
V prioritní frontě má každý prvek přiřazenou hodnotu priority. Když přidáte prvek do fronty, vloží se na pozici podle hodnoty priority. Pokud například přidáte prvek s hodnotou s vysokou prioritou do fronty priority, může být vložen blízko přední části fronty, zatímco prvek s hodnotou s nízkou prioritou může být vložen poblíž zadní části.
Existuje několik způsobů, jak implementovat prioritní frontu, včetně použití pole, propojeného seznamu, haldy nebo binárního vyhledávacího stromu. Každá metoda má své výhody a nevýhody a nejlepší volba bude záviset na konkrétních potřebách vaší aplikace.
Prioritní fronty se často používají v systémech v reálném čase, kde pořadí, ve kterém jsou prvky zpracovávány, může mít významné důsledky. Používají se také v algoritmech ke zlepšení jejich účinnosti, jako např Dijkstrův algoritmus pro nalezení nejkratší cesty v grafu a A* vyhledávací algoritmus pro hledání cesty.
Vlastnosti prioritní fronty
Prioritní fronta je tedy rozšířením fronta s následujícími vlastnostmi.
- Každá položka má přiřazenou prioritu.
- Prvek s vysokou prioritou je vyřazen z fronty před prvkem s nízkou prioritou.
- Pokud mají dva prvky stejnou prioritu, jsou obsluhovány podle pořadí ve frontě.
Ve frontě s prioritou níže bude mít prvek s maximální hodnotou ASCII nejvyšší prioritu. Prvky s vyšší prioritou jsou obsluhovány jako první.
Jak je přiřazena priorita prvkům v prioritní frontě?
V prioritní frontě se obecně bere v úvahu hodnota prvku pro přiřazení priority.
Například prvku s nejvyšší hodnotou je přiřazena nejvyšší priorita a prvku s nejnižší hodnotou je přiřazena nejnižší priorita. Lze použít i obrácený případ, tj. prvku s nejnižší hodnotou lze přiřadit nejvyšší prioritu. Prioritu lze také přiřadit podle našich potřeb.
Operace prioritní fronty:
Typická prioritní fronta podporuje následující operace:
1) Vložení do prioritní fronty
Když je nový prvek vložen do prioritní fronty, přesune se do prázdného slotu shora dolů a zleva doprava. Pokud však prvek není na správném místě, bude porovnán s nadřazeným uzlem. Pokud prvek není ve správném pořadí, prvky se zamění. Proces výměny pokračuje, dokud nejsou všechny prvky umístěny ve správné poloze.
2) Smazání v prioritní frontě
Jak víte, že v maximální hromadě je maximálním prvkem kořenový uzel. A nejprve odstraní prvek, který má maximální prioritu. Tímto způsobem odstraníte kořenový uzel z fronty. Toto odstranění vytvoří prázdnou štěrbinu, která bude dále vyplněna novým vložením. Poté porovná nově vložený prvek se všemi prvky ve frontě, aby byla zachována invariantnost haldy.
3) Podívejte se do prioritní fronty
Tato operace pomáhá vrátit maximální prvek z maximální haldy nebo minimální prvek z minimální haldy bez odstranění uzlu z prioritní fronty.
Typy prioritní fronty:
1) Fronta priority vzestupného pořadí
Jak název napovídá, ve frontě priority vzestupného pořadí má prvek s nižší prioritou v seznamu priorit vyšší prioritu. Pokud máme například následující prvky ve frontě s prioritou uspořádané vzestupně jako 4,6,8,9,10. Zde je 4 nejmenší číslo, proto bude mít nejvyšší prioritu ve frontě s prioritou, a tak když vyřazujeme frontu z tohoto typu prioritní fronty, 4 odebere z fronty a vyřazení vrátí 4.
2) Prioritní fronta sestupného pořadí
Kořenový uzel je maximální prvek v maximální hromadě, jak možná víte. Nejprve také odstraní prvek s nejvyšší prioritou. V důsledku toho je kořenový uzel odstraněn z fronty. Toto smazání zanechá prázdné místo, které bude v budoucnu vyplněno novými vloženími. Invariant haldy je pak udržován porovnáním nově vloženého prvku se všemi ostatními položkami ve frontě.
Typy prioritních front
Rozdíl mezi prioritní frontou a normální frontou?
Prvky ve frontě nemají žádnou prioritu, je implementováno pravidlo first-in-first-out (FIFO), zatímco v prioritní frontě mají prvky prioritu. Prvky s vyšší prioritou jsou obsluhovány jako první.
Jak implementovat prioritní frontu?
Prioritní frontu lze implementovat pomocí následujících datových struktur:
- Pole
- Spojový seznam
- Struktura dat haldy
- Binární vyhledávací strom
Proberme to všechno podrobně.
1) Implementujte prioritní frontu pomocí pole:
Jednoduchou implementací je použití pole následující struktury.
struct item {
int položka;
priorita int;
}
- enqueue(): Tato funkce se používá k vložení nových dat do fronty. dequeue(): Tato funkce odstraní prvek s nejvyšší prioritou z fronty. peek()/top(): Tato funkce se používá k získání prvku s nejvyšší prioritou ve frontě bez jeho odstranění z fronty.
| Pole | zařadit do fronty() | podle toho () | nahlédnout () |
|---|---|---|---|
| Časová složitost | O(1) | Na) | Na) |
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; }> |
>
>
Jáva
// 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> |
>
>Výstup
16 14 12>
Poznámka: Číst tento článek Více podrobností.
2) Implementujte prioritní frontu pomocí propojeného seznamu:
V implementaci LinkedList jsou položky seřazeny v sestupném pořadí na základě jejich priority. Prvek s nejvyšší prioritou je vždy přidán na začátek fronty s prioritou, která je tvořena pomocí propojených seznamů. Funkce jako TAM() , pop() , a nahlédnout () se používají k implementaci prioritní fronty pomocí propojeného seznamu a jsou vysvětleny následovně:
- push(): Tato funkce se používá k vložení nových dat do fronty. pop(): Tato funkce odstraní prvek s nejvyšší prioritou z fronty. peek() / top(): Tato funkce se používá k získání prvku s nejvyšší prioritou ve frontě bez jeho odstranění z fronty.
| Spojový seznam | TAM() | pop() | nahlédnout () |
|---|---|---|---|
| Časová složitost | Na) | 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->priorita = p;> >temp->další = 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)->další;> >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 // Vložit nový uzel před hlavu temp->next = *head; (*hlava) = teplota; } else { // Projděte seznam a najděte // pozici pro vložení nového uzlu while (start->další != NULL && start->další->priorita> p) { start = start->další; } // Buď na koncích seznamu // nebo na požadované pozici temp->next = start->next; start->další = teplota; } } // Funkce ke kontrole je seznam prázdný int isEmpty(Node** head) { return (*head) == NULL; } // Kód ovladače int main() { // Vytvoření prioritní fronty // 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; }> |
>
>
Jáva
// 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.další; } // Buď na koncích seznamu // nebo na požadované pozici temp.next = start.next; start.dalsi = teplota; } vrátit hlavu; } // Funkce ke kontrole je seznam je prázdný static int isEmpty(Node head) { return ((head) == null)?1:0; } // Kód ovladače public static void main(String args[]) { // Vytvoření prioritní fronty // 7.4.5.6 Uzel 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); } } } // Tento kód přispěl ishankhandelwals.> |
>
>
Krajta
# 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ácení 1 pro úspěšné provedení return 1 # Metoda pro odstranění položky s vysokou prioritou # z fronta priority def pop(self): # Kontrola stavu pro kontrolu # Prioritní fronta je prázdná nebo není, pokud self.isEmpty() == True: return else: # Odebrání uzlu s vysokou prioritou z # prioritní fronty a aktualizace předního # dalším uzel self.front = self.front.next return 1 # Metoda pro vrácení uzlu s vysokou prioritou # hodnota Neodstranění def peek(self): # Kontrola stavu pro kontrolu priority # Fronta je prázdná nebo není, pokud self.isEmpty() == True: return else: return self.front.data # Metoda pro přechod přes prioritu # Fronta def traverse(self): # Kontrola stavu pro kontrolu priority # Fronta je prázdná nebo není, pokud self.isEmpty() == True: return ' Fronta je prázdná!' else: temp = self.front while temp: print(temp.data, end=' ') temp = temp.next # Kód ovladače if _name_ == '_main_': # Vytvoření instance Priority # Queue a přidání hodnot # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push(4, 1) pq.push(5, 2) pq.push(6, 3) pq .push(7, 0) # Procházení prioritní frontou pq.traverse() # Odebírání položky s nejvyšší prioritou # pro prioritní frontu pq.pop()> |
>
char na celé číslo 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) { start = start.další; } // Buď na koncích seznamu // nebo na požadované pozici temp.next = start.next; start.dalsi = teplota; } vrátit hlavu; } // Funkce ke kontrole je, že seznam je prázdný public static int isEmpty(Node head) { return ((head) == null) ? 1:0; } // Kód ovladače public static void Main(string[] args) { // Vytvoření fronty priority // 7.4.5.6 Uzel 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 přispěl 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.další; } // Buď na koncích seznamu // nebo na požadované pozici temp.next = start.next; start.dalsi = teplota; } vrátit hlavu; } // Funkce ke kontrole je seznam prázdný function isEmpty(head) { return head == null ? 1:0; } // Kód ovladače // Vytvoření prioritní fronty // 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); } // Tento kód přispěl ishankhandelwals.> |
>
>Výstup
6 5 4 7>
Další podrobnosti naleznete v tomto článku.
Poznámka: Můžeme použít i Linked List, časová náročnost všech operací s linkovaným seznamem zůstává stejná jako pole. Výhodou propojeného seznamu je deleteHighestPriority() může být efektivnější, protože nemusíme položky přesouvat.
3) Implementujte prioritní frontu pomocí hald:
Binární halda je obecně preferována pro implementaci prioritní fronty, protože haldy poskytují lepší výkon ve srovnání s poli nebo LinkedList. S ohledem na vlastnosti haldy je záznam s největším klíčem nahoře a lze jej okamžitě odstranit. Obnovení vlastnosti haldy pro zbývající klíče však zabere čas O(log n). Pokud však má být okamžitě vložen další záznam, pak může být část tohoto času kombinována s časem O(log n) potřebným k vložení nového záznamu. Reprezentace prioritní fronty jako hromady se tedy ukazuje jako výhodná pro velké n, protože je efektivně reprezentována v souvislém úložišti a je zaručeno, že vyžaduje pouze logaritmický čas pro vkládání i mazání. Operace na binární haldě jsou následující:
- insert(p): Vloží nový prvek s prioritou p. extractMax(): Extrahuje prvek s maximální prioritou. remove(i): Odebere prvek, na který ukazuje iterátor i. getMax(): Vrací prvek s maximální prioritou. changePriority(i, p): Změní prioritu prvku, na který ukazuje já k p .
| Binární halda | vložit() | odstranit() | nahlédnout () |
|---|---|---|---|
| Časová složitost | O(log n) | O(log n) | O(1) |
Implementaci kódu naleznete v tomto článku.
4) Implementujte frontu priority pomocí stromu binárního vyhledávání:
K implementaci prioritní fronty lze také použít samovyvažovací binární vyhledávací strom jako AVL strom, Červeno-černý strom atd. Operace jako peek(), insert() a delete() lze provádět pomocí BST.
| Binární vyhledávací strom | nahlédnout () | vložit() | vymazat() |
|---|---|---|---|
| Časová složitost | O(1) | O(log n) | O(log n) |
Aplikace prioritní fronty:
- Plánování CPU
- Algoritmy grafů, jako je Dijkstrův algoritmus nejkratší cesty, Primův minimální Spanning Tree atd.
- Implementace zásobníku
- Všechny aplikace prioritní fronty
- Prioritní fronta v C++
- Prioritní fronta v Javě
- Prioritní fronta v Pythonu
- Prioritní fronta v JavaScriptu
- Nedávné články o Prioritní frontě!