У цьому посібнику ви дізнаєтесь, що таке пріоритетна черга. Крім того, ви дізнаєтесь про його реалізації в 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)
Якщо вузла немає, створіть новий. інакше (вузол вже присутній) вставте newNode в кінець (останній вузол зліва направо.) heapify масив
Для Min Heap вищезазначений алгоритм модифікований таким чином, що parentNodeзавжди менше, ніж newNode.
2. Видалення елемента з черги пріоритетів
Видалення елемента з черги пріоритетів (max-heap) виконується наступним чином:
- Виберіть елемент, який потрібно видалити.
Виберіть елемент, який потрібно видалити - Поміняйте його місцями з останнім елементом.
Поміняти місцями з останнім елементом вузла листа - Видаліть останній елемент.
Зніміть останній елемент елемента - Посилити дерево.
Посилення черги пріоритетів
Алгоритм видалення елемента в черзі пріоритетів (max-heap)
Якщо nodeToBeDeleted є leafNode, видаліть вузол Інакше підмініть nodeToBeDeleted з lastLeafNode видаліть noteToBeDeleted, купірує масив
Для Min Heap вищезазначений алгоритм модифікований таким чином, що обидва childNodesвони менше, ніж currentNode.
3. Вигляд із черги пріоритетів (Знайти максимум / хв)
Операція Peek повертає максимальний елемент із Max Heap або мінімальний елемент з Min Heap без видалення вузла.
І для Max Heap, і для Min Heap
повернути rootNode
4. Витяг макс. / Хв. З черги пріоритетів
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); )
Програми пріоритетної черги
Деякі програми черги пріоритетів:
- Алгоритм Дейкстри
- для реалізації стека
- для балансування навантаження та обробки переривань в операційній системі
- для стиснення даних у коді Хаффмана
