В този урок ще научите какво е опашката с приоритет. Също така ще научите за неговите внедрения в Python, Java, C и C ++.
Приоритетна опашка е специален вид опашка, при която всеки елемент е свързан с приоритет и се обслужва според неговия приоритет. Ако се появят елементи със същия приоритет, те се обслужват според реда им в опашката.
Като цяло стойността на самия елемент се взема предвид за присвояване на приоритет.
Например, Елементът с най-висока стойност се счита за елемент с най-висок приоритет. В други случаи обаче можем да приемем елемента с най-ниска стойност като елемент с най-висок приоритет. В други случаи можем да определяме приоритети според нашите нужди.
Премахване на елемент с най-висок приоритет
Разлика между приоритетна и нормална опашка
В опашката се прилага правило „ първо в първото излизане“, докато в опашка с приоритет стойностите се премахват въз основа на приоритет . Първо се премахва елементът с най-висок приоритет.
Прилагане на приоритетна опашка
Опашката за приоритет може да бъде реализирана с помощта на масив, свързан списък, структура на данни от купчина или двоично дърво за търсене. Сред тези структури от данни структурата на купчината данни осигурява ефективно изпълнение на приоритетни опашки.
Следователно ще използваме структурата от данни за купчина, за да реализираме приоритетната опашка в този урок. Прилагането на max-heap е в следните операции. Ако искате да научите повече за това, моля, посетете max-heap и mean-heap.
Сравнителен анализ на различни изпълнения на приоритетна опашка е даден по-долу.
| Операции | надникнете | вмъкване | Изтрий |
|---|---|---|---|
| Свързан списък | O(1) | O(n) | O(1) |
| Двоична купчина | O(1) | O(log n) | O(log n) |
| Двоично дърво за търсене | O(1) | O(log n) | O(log n) |
Операции с приоритетна опашка
Основните операции на приоритетна опашка са вмъкване, премахване и надникване на елементи.
Преди да проучите приоритетната опашка, моля, обърнете се към структурата на данните за купчина за по-добро разбиране на двоичната купчина, тъй като тя се използва за изпълнение на приоритетната опашка в тази статия.
1. Вмъкване на елемент в приоритетната опашка
Вмъкването на елемент в приоритетна опашка (max-heap) се извършва чрез следните стъпки.
- Поставете новия елемент в края на дървото.
Поставете елемент в края на опашката - Утежнете дървото.
Засилва се след вмъкване
Алгоритъм за вмъкване на елемент в опашка с приоритет (max-heap)
Ако няма възел, създайте новNode. в противен случай (възел вече е наличен) вмъкнете newNode в края (последния възел отляво надясно.) heapify масива
За Min Heap горният алгоритъм е модифициран, така че parentNodeвинаги да е по-малък от newNode.
2. Изтриване на елемент от приоритетната опашка
Изтриването на елемент от приоритетна опашка (max-heap) се извършва, както следва:
- Изберете елемента за изтриване.
Изберете елемента за изтриване - Разменете го с последния елемент.
Разменете с последния елемент на възел на листа - Премахнете последния елемент.
Отстранете последния лист на елемента - Утежнете дървото.
Увеличете опашката за приоритет
Алгоритъм за изтриване на елемент в опашката с приоритет (max-heap)
Ако nodeToBeDeleted е leafNode, премахнете възела Else swap nodeToBeDeleted с lastLeafNode премахнете noteToBeDeleted hepify масива
За Min Heap горният алгоритъм е модифициран, така че и двата да childNodesса по-малки от currentNode.
3. Надникване от приоритетната опашка (Намерете макс. / Мин.)
Операцията Peek връща максималния елемент от Max Heap или минималния елемент от Min Heap, без да изтрива възела.
Както за Max Heap, така и за Min Heap
връщане rootNode
4. Извличане-Max / Min от приоритетната опашка
Extract-Max връща възела с максимална стойност, след като го премахне от Max Heap, докато Extract-Min връща възела с минимална стойност, след като го премахне от Min Heap.
Реализации на приоритетна опашка в Python, Java, C и C ++
Python Java C C ++ # Priority Queue implementation in Python # Function to heapify the tree def heapify(arr, n, i): # Find the largest among root, left child and right child largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr(i) < arr(l): largest = l if r < n and arr(largest) < arr(r): largest = r # Swap and continue heapifying if root is not largest if largest != i: arr(i), arr(largest) = arr(largest), arr(i) heapify(arr, n, largest) # Function to insert an element into the tree def insert(array, newNum): size = len(array) if size == 0: array.append(newNum) else: array.append(newNum) for i in range((size // 2) - 1, -1, -1): heapify(array, size, i) # Function to delete an element from the tree def deleteNode(array, num): size = len(array) i = 0 for i in range(0, size): if num == array(i): break array(i), array(size - 1) = array(size - 1), array(i) array.remove(size - 1) for i in range((len(array) // 2) - 1, -1, -1): heapify(array, len(array), i) arr = () insert(arr, 3) insert(arr, 4) insert(arr, 9) insert(arr, 5) insert(arr, 2) print ("Max-Heap array: " + str(arr)) deleteNode(arr, 4) print("After deleting an element: " + str(arr))
// Priority Queue implementation in Java import java.util.ArrayList; class Heap ( // Function to heapify the tree void heapify(ArrayList hT, int i) ( int size = hT.size(); // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (r hT.get(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); ) ) // Function to insert an element into the tree void insert(ArrayList hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.add(newNum); ) else ( hT.add(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) // Function to delete an element from the tree void deleteNode(ArrayList hT, int num) ( int size = hT.size(); int i; for (i = 0; i = 0; j--) ( heapify(hT, j); ) ) // Print the tree void printArray(ArrayList array, int size) ( for (Integer i : array) ( System.out.print(i + " "); ) System.out.println(); ) // Driver code public static void main(String args()) ( ArrayList array = new ArrayList(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println("Max-Heap array: "); h.printArray(array, size); h.deleteNode(array, 4); System.out.println("After deleting an element: "); h.printArray(array, size); ) )
// Priority Queue implementation in C #include int size = 0; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) // Function to heapify the tree void heapify(int array(), int size, int i) ( if (size == 1) ( printf("Single element in the heap"); ) else ( // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l array(largest)) largest = l; if (r array(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&array(i), &array(largest)); heapify(array, size, largest); ) ) ) // Function to insert an element into the tree void insert(int array(), int newNum) ( if (size == 0) ( array(0) = newNum; size += 1; ) else ( array(size) = newNum; size += 1; for (int i = size / 2 - 1; i>= 0; i--) ( heapify(array, size, i); ) ) ) // Function to delete an element from the tree void deleteRoot(int array(), int num) ( int i; for (i = 0; i = 0; i--) ( heapify(array, size, i); ) ) // Print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) printf("%d ", array(i)); printf(""); ) // Driver code int main() ( int array(10); insert(array, 3); insert(array, 4); insert(array, 9); insert(array, 5); insert(array, 2); printf("Max-Heap array: "); printArray(array, size); deleteRoot(array, 4); printf("After deleting an element: "); printArray(array, size); )
// Priority Queue implementation in C++ #include #include using namespace std; // Function to swap position of two elements void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) // Function to heapify the tree void heapify(vector &hT, int i) ( int size = hT.size(); // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT(largest)) largest = l; if (r hT(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&hT(i), &hT(largest)); heapify(hT, largest); ) ) // Function to insert an element into the tree void insert(vector &hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.push_back(newNum); ) else ( hT.push_back(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) // Function to delete an element from the tree void deleteNode(vector &hT, int num) ( int size = hT.size(); int i; for (i = 0; i = 0; i--) ( heapify(hT, i); ) ) // Print the tree void printArray(vector &hT) ( for (int i = 0; i < hT.size(); ++i) cout << hT(i) << " "; cout << ""; ) // Driver code int main() ( vector heapTree; insert(heapTree, 3); insert(heapTree, 4); insert(heapTree, 9); insert(heapTree, 5); insert(heapTree, 2); cout << "Max-Heap array: "; printArray(heapTree); deleteNode(heapTree, 4); cout << "After deleting an element: "; printArray(heapTree); )
Приоритетни приложения на опашката
Някои от приложенията на приоритетна опашка са:
- Алгоритъм на Дейкстра
- за внедряване на стека
- за балансиране на натоварването и обработка на прекъсвания в операционна система
- за компресиране на данни в код на Хафман
