Структура данных очереди приоритетов

Содержание

Реализация очереди приоритетов
Приоритетные операции с очередью
Реализации очереди приоритетов в Python, Java, C и C ++
Приложения с приоритетной очередью

В этом руководстве вы узнаете, что такое приоритетная очередь. Кроме того, вы узнаете о его реализациях на Python, Java, C и C ++.

Очередь с приоритетом - это особый тип очереди, в которой каждый элемент связан с приоритетом и обслуживается в соответствии с его приоритетом. Если встречаются элементы с одинаковым приоритетом, они обслуживаются в соответствии с их порядком в очереди.

Как правило, значение самого элемента учитывается для определения приоритета.

Например, элемент с наивысшим значением считается элементом с наивысшим приоритетом. Однако в других случаях мы можем принять элемент с самым низким значением как элемент с наивысшим приоритетом. В других случаях мы можем расставить приоритеты в соответствии с нашими потребностями.

Удаление элемента с наивысшим приоритетом

Разница между приоритетной очередью и нормальной очередью

В очереди реализуется правило «первым пришел - первым обслужен», тогда как в очереди с приоритетом значения удаляются на основе приоритета . Первым удаляется элемент с наивысшим приоритетом.

Реализация очереди приоритетов

Очередь приоритета может быть реализована с использованием массива, связанного списка, структуры данных кучи или двоичного дерева поиска. Среди этих структур данных структура данных кучи обеспечивает эффективную реализацию очередей приоритетов.

Следовательно, мы будем использовать структуру данных кучи для реализации очереди приоритетов в этом руководстве. Максимальная куча реализуется в следующих операциях. Если вы хотите узнать об этом больше, посетите 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) выполняется следующими шагами.

Вставьте новый элемент в конец дерева. Вставить элемент в конец очереди
Насыпьте дерево. Heapify после вставки

Алгоритм вставки элемента в приоритетную очередь (max-heap)

Если узла нет, создайте новый узел. else (узел уже присутствует) вставьте новый узел в конец (последний узел слева направо).

Для Min Heap приведенный выше алгоритм изменен так, что parentNodeон всегда меньше, чем newNode.

2. Удаление элемента из очереди приоритета

Удаление элемента из очереди с приоритетом (max-heap) выполняется следующим образом:

Выберите элемент, который нужно удалить. Выберите элемент для удаления
Замените его последним элементом. Поменять местами последний элемент листового узла
Удалите последний элемент. Удаляем последний элемент листа
Насыпьте дерево в кучу. Заполните очередь приоритетов

Алгоритм удаления элемента в приоритетной очереди (max-heap)

 Если nodeToBeDeleted является листовым узлом, удалите узел. Иначе замените nodeToBeDeleted на lastLeafNode. Удалите noteToBeDeleted.

Для Min Heap приведенный выше алгоритм изменен так, чтобы оба childNodesбыли меньше, чем currentNode.

3. Просмотр из приоритетной очереди (определение макс. / Мин.)

Операция Peek возвращает максимальный элемент из 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); )