A kolejka priorytetowa to rodzaj kolejki porządkującej elementy na podstawie ich wartości priorytetu. Elementy o wyższych wartościach priorytetów są zwykle pobierane przed elementami o niższych wartościach priorytetów.
W kolejce priorytetowej każdy element ma przypisaną wartość priorytetu. Kiedy dodajesz element do kolejki, jest on wstawiany w pozycji opartej na jego wartości priorytetu. Na przykład, jeśli dodasz element o wysokim priorytecie do kolejki priorytetowej, może on zostać wstawiony z przodu kolejki, natomiast element o niskim priorytecie może zostać wstawiony z tyłu.
Istnieje kilka sposobów implementacji kolejki priorytetowej, w tym użycie tablicy, listy połączonej, sterty lub drzewa wyszukiwania binarnego. Każda metoda ma swoje zalety i wady, a najlepszy wybór będzie zależał od konkretnych potrzeb Twojej aplikacji.
Kolejki priorytetowe często wykorzystywane są w systemach czasu rzeczywistego, gdzie kolejność przetwarzania elementów może mieć istotne konsekwencje. Wykorzystuje się je również w algorytmach w celu poprawy ich wydajności, np Algorytm Dijkstry do znajdowania najkrótszej ścieżki na grafie i algorytmu wyszukiwania A* do znajdowania ścieżki.
Właściwości kolejki priorytetowej
Zatem kolejka priorytetowa jest rozszerzeniem kolejka z następującymi właściwościami.
- Z każdym elementem jest powiązany priorytet.
- Element o wysokim priorytecie jest usuwany z kolejki przed elementem o niskim priorytecie.
- Jeżeli dwa elementy mają ten sam priorytet, są obsługiwane zgodnie z kolejnością w kolejce.
W poniższej kolejce priorytetów najwyższy priorytet będzie miał element o maksymalnej wartości ASCII. W pierwszej kolejności obsługiwane są elementy o wyższym priorytecie.
W jaki sposób przypisuje się priorytet elementom w kolejce priorytetów?
Ogólnie rzecz biorąc, w kolejce priorytetowej przy przypisywaniu priorytetu uwzględniana jest wartość elementu.
Na przykład element o najwyższej wartości ma przypisany najwyższy priorytet, a element o najniższej wartości ma przypisany najniższy priorytet. Można zastosować także odwrotną sytuację, tzn. elementowi o najniższej wartości można nadać najwyższy priorytet. Priorytet możemy także przypisać według naszych potrzeb.
Operacje kolejki priorytetowej:
Typowa kolejka priorytetowa obsługuje następujące operacje:
1) Umieszczenie w kolejce priorytetowej
Kiedy nowy element jest wstawiany do kolejki priorytetowej, przesuwa się on do pustego miejsca od góry do dołu i od lewej do prawej. Jeśli jednak element nie znajduje się we właściwym miejscu, zostanie porównany z węzłem nadrzędnym. Jeśli element nie jest we właściwej kolejności, następuje zamiana elementów. Proces wymiany trwa do momentu umieszczenia wszystkich elementów we właściwej pozycji.
2) Usunięcie z kolejki priorytetowej
Jak wiadomo, w maksymalnej stercie maksymalnym elementem jest węzeł główny. I najpierw usunie element, który ma maksymalny priorytet. W ten sposób usuwasz węzeł główny z kolejki. To usunięcie tworzy puste miejsce, które będzie dalej wypełniane nowym wstawieniem. Następnie porównuje nowo wstawiony element ze wszystkimi elementami w kolejce, aby zachować niezmiennik sterty.
3) Zajrzyj do kolejki priorytetowej
Ta operacja pomaga zwrócić maksymalny element ze sterty Max Heap lub element minimalny ze sterty Min bez usuwania węzła z kolejki priorytetowej.
Rodzaje kolejek priorytetowych:
1) Kolejka priorytetów zamówień rosnących
Jak sama nazwa wskazuje, w kolejce priorytetów w porządku rosnącym element o niższej wartości priorytetu otrzymuje wyższy priorytet na liście priorytetów. Na przykład, jeśli w kolejce priorytetowej mamy następujące elementy ułożone w kolejności rosnącej, np. 4,6,8,9,10. Tutaj 4 jest najmniejszą liczbą, dlatego otrzyma najwyższy priorytet w kolejce priorytetowej, więc kiedy usuniemy z kolejki tego typu, 4 zostanie usunięte z kolejki, a usunięcie z kolejki zwróci 4.
2) Kolejność priorytetowa w kolejności malejącej
Jak zapewne wiesz, węzeł główny jest maksymalnym elementem na maksymalnej stercie. Najpierw usunie także element o najwyższym priorytecie. W efekcie węzeł główny zostaje usunięty z kolejki. To usunięcie pozostawia pustą przestrzeń, która w przyszłości zostanie wypełniona nowymi wstawkami. Następnie utrzymuje się niezmiennik sterty, porównując nowo wstawiony element ze wszystkimi innymi wpisami w kolejce.
Rodzaje kolejek priorytetowych
Różnica między kolejką priorytetową a kolejką normalną?
Elementom w kolejce nie jest przypisany priorytet, stosowana jest zasada „pierwszy na wejściu, pierwszy na wyjściu” (FIFO), podczas gdy w kolejce priorytetowej elementy mają priorytet. W pierwszej kolejności obsługiwane są elementy o wyższym priorytecie.
Jak wdrożyć kolejkę priorytetową?
Kolejkę priorytetową można zaimplementować przy użyciu następujących struktur danych:
- Tablice
- Połączona lista
- Struktura danych sterty
- Drzewo wyszukiwania binarnego
Omówmy to wszystko szczegółowo.
1) Zaimplementuj kolejkę priorytetową za pomocą tablicy:
Prostą implementacją jest użycie tablicy o następującej strukturze.
element struktury {
element int;
priorytet int;
}
- enqueue(): Ta funkcja służy do wstawiania nowych danych do kolejki. dequeue(): Ta funkcja usuwa z kolejki element o najwyższym priorytecie. peek()/top(): Ta funkcja służy do pobrania elementu o najwyższym priorytecie w kolejce bez usuwania go z kolejki.
| Tablice | kolejkować() | odpowiednio () | zerkać() |
|---|---|---|---|
| Złożoność czasu | O(1) | NA) rozmiar tekstu, lateks | 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; }> |
>
>
Jawa
// 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> |
>
>Wyjście
16 14 12>
Notatka: Czytać Ten artykuł po więcej szczegółów.
2) Zaimplementuj kolejkę priorytetową za pomocą listy połączonej:
W implementacji LinkedList wpisy są sortowane w kolejności malejącej na podstawie ich priorytetu. Element o najwyższym priorytecie jest zawsze dodawany na początek kolejki priorytetowej utworzonej przy użyciu list połączonych. Funkcje takie jak naciskać() , Muzyka pop() , I zerkać() służą do implementacji kolejki priorytetowej przy użyciu listy połączonej i są wyjaśnione w następujący sposób:
- push(): Ta funkcja służy do wstawiania nowych danych do kolejki. pop(): Ta funkcja usuwa z kolejki element o najwyższym priorytecie. peek() / top(): Ta funkcja służy do pobrania elementu o najwyższym priorytecie w kolejce bez usuwania go z kolejki.
| Połączona lista svm | naciskać() | Muzyka pop() | zerkać() |
|---|---|---|---|
| Złożoność czasu | 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->dane = d;> >temp->priorytet = p;> >temp->następny = NULL;> >return> temp;> }> // Return the value at head> int> peek(Node** head) {>return> (*head)->dane; }> // Removes the element with the> // highest priority form the list> void> pop(Node** head)> {> >Node* temp = *head;> >(*head) = (*head)->następny;> >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)->priorytet // Wstaw nowy węzeł przed head temp->next = *head; (*głowa) = temperatura; } else { // Przejrzyj listę i znajdź // pozycję, w której chcesz wstawić nowy węzeł, while (start->next != NULL && start->next->priority> p) { start = start->next; } // Albo na końcu listy // albo w wymaganej pozycji temp->next = start->next; start->dalej = temp; } } // Funkcja sprawdzająca, czy lista jest pusta int isEmpty(Node** head) { return (*head) == NULL; } // Kod sterownika int main() { // Utwórz kolejkę priorytetową // 7->4->5->6 Węzeł* pq = newNode(4, 1); naciśnij(&pq, 5, 2); naciśnij(&pq, 6, 3); naciśnij(&pq, 7, 0); while (!isEmpty(&pq)) { cout<< ' ' << peek(&pq); pop(&pq); } return 0; }> |
>
>
Jawa
// 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 = początek.następny; } // Albo na końcu listy //, albo na wymaganej pozycji temp.next = start.next; początek. następny = temp; } powrót głowy; } // Funkcja sprawdzająca, czy lista jest pusta static int isEmpty(głowa węzła) { return ((głowa) == null)?1:0; } // Kod sterownika public static void main(String args[]) { // Utwórz kolejkę priorytetową // 7.4.5.6 Węzeł pq = newNode(4, 1); pq = naciśnięcie (pq, 5, 2); pq =push(pq, 6, 3); pq = naciśnięcie (pq, 7, 0); while (isEmpty(pq)==0) { System.out.printf('%d ', peek(pq)); pq=pop(pq); } } } // Ten kod został napisany przez ishankhandelwals.> |
>
>
Pyton
# 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: przerwa temp = temp.next newNode = PriorityQueueNode(wartość, priorytet) newNode.next = temp.next temp.next = newNode # Zwracanie 1 w przypadku pomyślnego wykonania return 1 # Metoda usuwania elementu o wysokim priorytecie # z kolejka priorytetowa def pop(self): # Sprawdzanie warunku w celu sprawdzenia # Kolejka priorytetowa jest pusta czy nie, jeśli self.isEmpty() == True: return else: # Usuwanie węzła o wysokim priorytecie z # Kolejki priorytetowej i aktualizacja frontu # następnym węzeł self.front = self.front.next return 1 # Metoda zwracająca wartość węzła o wysokim priorytecie # Nie usuwam def peek(self): # Sprawdzanie warunków w celu sprawdzenia Priorytet # Kolejka jest pusta lub nie, jeśli self.isEmpty() == Prawda: return else: return self.front.data # Metoda przejścia przez priorytet # Queue def traverse(self): # Sprawdzanie warunku w celu sprawdzenia priorytetu # Kolejka jest pusta lub nie, jeśli self.isEmpty() == True: return ' Kolejka jest pusta!' else: temp = self.front while temp: print(temp.data, end=' ') temp = temp.next # Kod sterownika if _name_ == '_main_': # Tworzenie instancja Priority # Queue i dodanie wartości # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push(4, 1) pq.push(5, 2) pq.push(6, 3) pq .push(7, 0) # Przechodzenie przez kolejkę priorytetową pq.traverse() # Usuwanie elementu o najwyższym priorytecie # z kolejki priorytetowej 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 = początek.następny; } // Albo na końcu listy //, albo na wymaganej pozycji temp.next = start.next; początek. następny = temp; } powrót głowy; } // Funkcja sprawdzająca, czy lista jest pusta public static int isEmpty(głowa węzła) { return ((głowa) == null) ? 1: 0; } // Kod sterownika public static void Main(string[] args) { // Utwórz kolejkę priorytetową // 7.4.5.6 Węzeł 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); } } } // Ten kod został napisany przez 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 = początek.następny; } // Albo na końcu listy //, albo na wymaganej pozycji temp.next = start.next; początek. następny = temp; } powrót głowy; } // Funkcja sprawdzająca, czy lista jest pusta funkcja isEmpty(head) { return head == null ? 1: 0; } // Kod sterownika // Utwórz kolejkę priorytetową // 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); } // Ten kod został napisany przez ishankhandelwals.> |
>
>Wyjście
6 5 4 7>
Więcej szczegółów znajdziesz w tym artykule.
Notatka: Możemy również użyć listy połączonej, złożoność czasowa wszystkich operacji na liście połączonej pozostaje taka sama jak w przypadku tablicy. Zaletą listy połączonej jest usuńNajwyższyPriorytet() może być bardziej wydajne, ponieważ nie musimy przenosić przedmiotów.
3) Zaimplementuj kolejkę priorytetową za pomocą stert:
Do implementacji kolejek priorytetowych ogólnie preferowana jest sterta binarna, ponieważ sterty zapewniają lepszą wydajność w porównaniu z tablicami lub listą LinkedList. Biorąc pod uwagę właściwości sterty, wpis z największym kluczem znajduje się na górze i można go natychmiast usunąć. Przywrócenie właściwości sterty dla pozostałych kluczy zajmie jednak trochę czasu O(log n). Jeżeli jednak natychmiast ma zostać wstawiony inny wpis, część tego czasu można połączyć z czasem O(log n) potrzebnym do wstawienia nowego wpisu. Zatem reprezentacja kolejki priorytetowej jako sterty okazuje się korzystna w przypadku dużego n, ponieważ jest ona skutecznie reprezentowana w ciągłej pamięci i gwarantuje, że zarówno wstawianie, jak i usuwanie wymaga jedynie czasu logarytmicznego. Operacje na stercie binarnej są następujące:
- wstaw(p): Wstawia nowy element z priorytetem p. ekstraktMax(): Wyodrębnia element o maksymalnym priorytecie. usuń(i): Usuwa element wskazany przez iterator, tj. getMax(): Zwraca element z maksymalnym priorytetem. changePriority(i, p): Zmienia priorytet elementu wskazywanego przez ja do str .
| Kopia binarna | wstawić() | usunąć() | zerkać() |
|---|---|---|---|
| Złożoność czasu | O(log n) | O(log n) | O(1) |
Aby zapoznać się z implementacją kodu, zapoznaj się z tym artykułem.
4) Zaimplementuj kolejkę priorytetową za pomocą drzewa wyszukiwania binarnego:
Samobalansujące się drzewo wyszukiwania binarnego, takie jak drzewo AVL, drzewo czerwono-czarne itp., może być również użyte do zaimplementowania kolejki priorytetowej. Operacje takie jak peek(), Insert() i Delete() można wykonywać przy użyciu BST.
| Drzewo wyszukiwania binarnego | zerkać() | wstawić() | usuwać() |
|---|---|---|---|
| Złożoność czasu | O(1) | O(log n) | O(log n) |
Zastosowania kolejki priorytetowej:
- Harmonogramowanie procesora
- Algorytmy graficzne, takie jak algorytm najkrótszej ścieżki Dijkstry, minimalne drzewo rozpinające Prima itp.
- Implementacja stosu
- Wszystkie zastosowania kolejki priorytetowej
- Kolejka priorytetowa w C++
- Kolejka priorytetowa w Javie
- Kolejka priorytetowa w Pythonie
- Kolejka priorytetowa w JavaScript
- Najnowsze artykuły na temat kolejki priorytetowej!