А пріоритетна черга це тип черги, яка впорядковує елементи на основі їх пріоритетних значень. Елементи з вищими значеннями пріоритету зазвичай витягуються перед елементами з нижчими значеннями пріоритету.
У черзі пріоритету кожен елемент має значення пріоритету, пов’язане з ним. Коли ви додаєте елемент до черги, він вставляється в позицію на основі значення його пріоритету. Наприклад, якщо ви додаєте елемент із високим значенням пріоритету до черги пріоритету, його можна вставити ближче до початку черги, тоді як елемент із низьким значенням можна вставити ближче до кінця.
Існує кілька способів реалізації черги пріоритетів, включаючи використання масиву, зв’язаного списку, купи або бінарного дерева пошуку. Кожен метод має свої переваги та недоліки, і найкращий вибір залежатиме від конкретних потреб вашої програми.
Пріоритетні черги часто використовуються в системах реального часу, де порядок обробки елементів може мати значні наслідки. Вони також використовуються в алгоритмах для підвищення їх ефективності, наприклад Алгоритм Дейкстри для пошуку найкоротшого шляху в графі та алгоритм пошуку A* для пошуку шляху.
Властивості пріоритетної черги
Отже, пріоритетна черга є розширенням черга з такими властивостями.
- Кожен елемент має пов’язаний з ним пріоритет.
- Елемент з високим пріоритетом вилучається з черги перед елементом з низьким пріоритетом.
- Якщо два елементи мають однаковий пріоритет, вони обслуговуються відповідно до свого порядку в черзі.
У наведеній нижче черзі пріоритету елемент із максимальним значенням ASCII матиме найвищий пріоритет. Першими обслуговуються елементи з вищим пріоритетом.
Як призначається пріоритет елементам у черзі пріоритетів?
У пріоритетній черзі, як правило, для призначення пріоритету враховується значення елемента.
Наприклад, елементу з найвищим значенням призначається найвищий пріоритет, а елементу з найменшим значенням – найнижчий. Також можна використовувати зворотний випадок, тобто елементу з найнижчим значенням можна призначити найвищий пріоритет. Крім того, пріоритет може бути призначений відповідно до наших потреб.
Операції пріоритетної черги:
Типова пріоритетна черга підтримує такі операції:
1) Вставлення в пріоритетну чергу
Коли новий елемент вставляється в пріоритетну чергу, він переміщується в порожній слот зверху вниз і зліва направо. Однак, якщо елемент знаходиться не в правильному місці, його буде порівняно з батьківським вузлом. Якщо елемент не в правильному порядку, елементи міняються місцями. Процес заміни триває до тих пір, поки всі елементи не будуть розміщені в правильному положенні.
2) Видалення в пріоритетній черзі
Як ви знаєте, у максимальній купі максимальним елементом є кореневий вузол. І першим буде видалено елемент, який має максимальний пріоритет. Таким чином, ви видаляєте кореневий вузол із черги. Це видалення створює порожній слот, який буде заповнено новою вставкою. Потім він порівнює щойно вставлений елемент з усіма елементами всередині черги, щоб підтримувати незмінність купи.
3) Загляньте в пріоритетну чергу
Ця операція допомагає повернути максимальний елемент із Max Heap або мінімальний елемент із Min Heap без видалення вузла з черги пріоритетів.
Типи пріоритетної черги:
1) Черга пріоритету за зростанням
Як випливає з назви, у черзі за зростанням пріоритету елементу з нижчим значенням пріоритету надається вищий пріоритет у списку пріоритетів. Наприклад, якщо ми маємо наступні елементи в черзі пріоритетів, розташованих у порядку зростання, як 4,6,8,9,10. Тут 4 є найменшим числом, отже, воно отримає найвищий пріоритет у черзі пріоритету, тому, коли ми вилучаємо з черги цього типу пріоритету, 4 буде видалено з черги, а видалення з черги повертає 4.
2) Черга пріоритетів у порядку спадання
Кореневий вузол є максимальним елементом у максимальній купі, як ви, можливо, знаєте. Також спочатку буде видалено елемент із найвищим пріоритетом. У результаті кореневий вузол видаляється з черги. Це видалення залишає порожній простір, який у майбутньому буде заповнено новими вставками. Потім інваріант купи підтримується шляхом порівняння щойно вставленого елемента з усіма іншими записами в черзі.
оператор перемикання Java
Типи пріоритетних черг
Різниця між пріоритетною чергою та звичайною чергою?
Елементам у черзі не присвоєно пріоритету, реалізовано правило «першим прийшов – першим вийшов» (FIFO), тоді як у черзі пріоритету елементи мають пріоритет. Першими обслуговуються елементи з вищим пріоритетом.
Як реалізувати пріоритетну чергу?
Пріоритетну чергу можна реалізувати за допомогою таких структур даних:
- Масиви
- Зв'язаний список
- Структура даних купи
- Двійкове дерево пошуку
Давайте обговоримо все це детально.
1) Реалізуйте пріоритетну чергу за допомогою масиву:
Проста реалізація полягає у використанні масиву наступної структури.
struct item {
int елемент;
int пріоритет;
}
- enqueue(): Ця функція використовується для вставки нових даних у чергу. dequeue(): ця функція видаляє з черги елемент із найвищим пріоритетом. peek()/top(): Ця функція використовується для отримання елемента з найвищим пріоритетом у черзі без видалення його з черги.
| Масиви | поставити в чергу() | відповідно () | peek() |
|---|---|---|---|
| Часова складність | О(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> |
>
форматувати дату в java
>Вихід
16 14 12>
Примітка: Прочитайте Ця стаття для більш детальної інформації.
2) Реалізація черги пріоритетів за допомогою пов’язаного списку:
У реалізації LinkedList записи сортуються в порядку спадання на основі їх пріоритету. Елемент з найвищим пріоритетом завжди додається до початку черги пріоритетів, яка формується за допомогою пов’язаних списків. Такі функції, як push() , поп() , і peek() використовуються для реалізації пріоритетної черги за допомогою пов’язаного списку та пояснюються наступним чином:
- push(): Ця функція використовується для вставки нових даних у чергу. pop(): Ця функція видаляє з черги елемент із найвищим пріоритетом. peek() / top(): Ця функція використовується для отримання елемента з найвищим пріоритетом у черзі без видалення його з черги.
| Зв'язаний список | push() | поп() | peek() |
|---|---|---|---|
| Часова складність | O(n) | О(1) | О(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->дані = d;> >temp->пріоритет = p;> >temp->наступний = NULL;> >return> temp;> }> // Return the value at head> int> peek(Node** head) {>return> (*head)->дані; }> // Removes the element with the> // highest priority form the list> void> pop(Node** head)> {> >Node* temp = *head;> >(*head) = (*head)->далі;> >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)->пріоритет // Вставити новий вузол перед заголовком temp->next = *head; (*голова) = темп; } else { // Перейдіть по списку та знайдіть // позицію для вставки нового вузла while (start->next != NULL && start->next->priority> p) { start = start->next; } // Або в кінці списку // або в потрібній позиції temp->next = start->next; початок->наступний = temp; } } // Функція для перевірки, чи список порожній int isEmpty(Node** head) { return (*head) == NULL; } // Код драйвера int main() { // Створення черги пріоритетів // 7->4->5->6 Node* pq = newNode(4, 1); push(&pq, 5, 2); push(&pq, 6, 3); push(&pq, 7, 0); while (!isEmpty(&pq)) { cout<< ' ' << peek(&pq); pop(&pq); } return 0; }> |
>
>
Java
// Java code to implement Priority Queue> // using Linked List> import> java.util.* ;> class> Solution> {> // Node> static> class> Node {> >int> data;> > >// Lower values indicate higher priority> >int> priority;> >Node next;> > }> static> Node node =>new> Node();> > // Function to Create A New Node> static> Node newNode(>int> d,>int> p)> {> >Node temp =>new> Node();> >temp.data = d;> >temp.priority = p;> >temp.next =>null>;> > >return> temp;> }> > // Return the value at head> static> int> peek(Node head)> {> >return> (head).data;> }> > // Removes the element with the> // highest priority from the list> static> Node pop(Node head)> {> >Node temp = head;> >(head) = (head).next;> >return> head;> }> > // Function to push according to priority> static> Node push(Node head,>int> d,>int> p)> {> >Node start = (head);> > >// Create new Node> >Node temp = newNode(d, p);> > >// Special Case: The head of list has lesser> >// priority than new node. So insert new> >// node before head node and change head node.> >if> ((head).priority // Insert New Node before head temp.next = head; (head) = temp; } else { // Traverse the list and find a // position to insert new node while (start.next != null && start.next.priority>p) { start = start.next; } // Або в кінці списку // або в потрібній позиції temp.next = start.next; start.next = temp; } повернути голову; } // Функція для перевірки, чи список порожній static int isEmpty(Node head) { return ((head) == null)?1:0; } // Код драйвера public static void main(String args[]) { // Створення черги пріоритетів // 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=поп(pq); } } } // Цей код створено 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(значення, пріоритет) newNode.next = temp.next temp.next = newNode # Повернення 1 для успішного виконання return 1 # Метод видалення високопріоритетного елемента # з the Priority Queue def pop(self): # Перевірка умови для перевірки # Пріоритетна черга порожня чи ні, if self.isEmpty() == True: return else: # Видалення високопріоритетного вузла з # Пріоритетної черги та оновлення фронту # наступним node self.front = self.front.next return 1 # Метод повернення високопріоритетного вузла # значення Не видаляючи його def peek(self): # Перевірка умови для перевірки пріоритету # Черга порожня чи ні, якщо self.isEmpty() == True: return else: return self.front.data # Метод проходження через Priority # Queue def traverse(self): # Перевірка умови для перевірки Priority # Черга порожня чи ні, якщо self.isEmpty() == True: return ' Черга порожня!' else: temp = self.front while temp: print(temp.data, end=' ') temp = temp.next # Код драйвера if _name_ == '_main_': # Створення екземпляр Priority # Queue і додавання значень # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push(4, 1) pq.push(5, 2) pq.push(6, 3) pq .push(7, 0) # Перехід через пріоритетну чергу pq.traverse() # Видалення елемента з найвищим пріоритетом # для пріоритетної черги 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; } // Або в кінці списку // або в потрібній позиції temp.next = start.next; start.next = temp; } повернути голову; } // Функція для перевірки, чи список порожній public static int isEmpty(Node head) { return ((head) == null) ? 1 : 0; } // Код драйвера public static void Main(string[] args) { // Створення черги пріоритетів // 7.4.5.6 Node pq = newNode(4, 1); pq = push(pq, 5, 2); pq = push(pq, 6, 3); pq = push(pq, 7, 0); while (isEmpty(pq) == 0) { Console.Write('{0:D} ', peek(pq)); pq = pop(pq); } } } // Цей код створено ishankhandelwals.> |
>
>
Javascript
// JavaScript code to implement Priority Queue> // using Linked List> // Node> class Node {> >// Lower values indicate> >// higher priority> >constructor() {> >this>.data = 0;> >this>.priority = 0;> >this>.next =>null>;> >}> }> var> node =>new> Node();> // Function to Create A New Node> function> newNode(d, p) {> >var> temp =>new> Node();> >temp.data = d;> >temp.priority = p;> >temp.next =>null>;> >return> temp;> }> // Return the value at head> function> peek(head) {> >return> head.data;> }> // Removes the element with the> // highest priority from the list> function> pop(head) {> >var> temp = head;> >head = head.next;> >return> head;> }> // Function to push according to priority> function> push(head, d, p) {> >var> start = head;> >// Create new Node> >var> temp = newNode(d, p);> >// Special Case: The head of list> >// has lesser priority than new node.> >// So insert new node before head node> >// and change head node.> >if> (head.priority // Insert New Node before head temp.next = head; head = temp; } else { // Traverse the list and find a // position to insert new node while (start.next != null && start.next.priority>p) { start = start.next; } // Або в кінці списку // або в потрібній позиції temp.next = start.next; start.next = temp; } повернути голову; } // Функція для перевірки, чи список порожній function isEmpty(head) { return head == null ? 1 : 0; } // Код драйвера // Створення черги пріоритетів // 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); } // Цей код створено ishankhandelwals.> |
>
>Вихід
6 5 4 7>
Щоб дізнатися більше, зверніться до цієї статті.
Примітка: Ми також можемо використовувати пов’язаний список, часова складність усіх операцій зі зв’язаним списком залишається такою ж, як і в масиві. Перевага зв’язаного списку полягає в тому deleteHighestPriority() може бути ефективнішим, оскільки нам не потрібно переміщати предмети.
3) Реалізація черги пріоритетів за допомогою купи:
Двійкова купа зазвичай є кращою для реалізації пріоритетної черги, оскільки купи забезпечують кращу продуктивність порівняно з масивами або LinkedList. Беручи до уваги властивості купи, запис із найбільшим ключем знаходиться вгорі та може бути негайно видалений. Однак для відновлення властивості купи для решти ключів знадобиться час O(log n). Однак, якщо необхідно негайно вставити інший запис, то частину цього часу можна об’єднати з O(log n), необхідним для вставлення нового запису. Таким чином, представлення пріоритетної черги як купи виявляється вигідним для великих n, оскільки вона ефективно представлена в безперервному сховищі та гарантовано вимагає лише логарифмічного часу як для вставок, так і для видалень. Операції з бінарною купою такі:
кругла математика java
- insert(p): вставляє новий елемент із пріоритетом p. extractMax(): витягує елемент із максимальним пріоритетом. remove(i): видаляє елемент, на який вказує ітератор i. getMax(): повертає елемент із максимальним пріоритетом. changePriority(i, p): змінює пріоритет елемента, на який вказує я до стор .
| Бінарна купа | вставити() | видалити() | peek() |
|---|---|---|---|
| Часова складність | O(log n) | O(log n) | О(1) |
Зверніться до цієї статті для реалізації коду.
4) Реалізація черги пріоритетів за допомогою бінарного дерева пошуку:
Для реалізації пріоритетної черги також можна використовувати самобалансуюче бінарне дерево пошуку, таке як AVL Tree, Red-Black Tree тощо. Такі операції як peek(), insert() і delete() можна виконувати за допомогою BST.
| Двійкове дерево пошуку | peek() | вставити() | видалити() |
|---|---|---|---|
| Часова складність | О(1) | O(log n) | O(log n) |
Застосування пріоритетної черги:
- Планування ЦП
- Графічні алгоритми, такі як алгоритм найкоротшого шляху Дейкстри, Мінімальне остовне дерево Прима тощо.
- Реалізація стека
- Усі програми пріоритетної черги
- Пріоритетна черга в C++
- Пріоритетна черга в Java
- Пріоритетна черга в Python
- Пріоритетна черга в JavaScript
- Останні статті про пріоритетну чергу!