W tym samouczku dowiesz się, czym jest kolejka priorytetowa. Dowiesz się również o jego implementacjach w Pythonie, Javie, C i C ++.
Kolejka priorytetowa to specjalny rodzaj kolejki, w której każdy element ma przypisany priorytet i jest obsługiwany zgodnie z jego priorytetem. Jeśli wystąpią elementy o tym samym priorytecie, są obsługiwane zgodnie z ich kolejnością w kolejce.
Ogólnie rzecz biorąc, do przypisania priorytetu brana jest pod uwagę wartość samego elementu.
Na przykład element o najwyższej wartości jest uważany za element o najwyższym priorytecie. Jednak w innych przypadkach możemy przyjąć element o najniższej wartości jako element o najwyższym priorytecie. W innych przypadkach możemy ustawić priorytety zgodnie z naszymi potrzebami.
Usuwanie elementu o najwyższym priorytecie
Różnica między kolejką priorytetową a kolejką normalną
W kolejce zaimplementowana jest reguła pierwszy na wejściu, pierwszy na wyjściu, natomiast w kolejce priorytetowej wartości są usuwane na podstawie priorytetu . Element o najwyższym priorytecie jest usuwany jako pierwszy.
Wdrożenie kolejki priorytetowej
Kolejkę priorytetową można zaimplementować za pomocą tablicy, połączonej listy, struktury danych sterty lub binarnego drzewa wyszukiwania. Wśród tych struktur danych struktura danych sterty zapewnia wydajną implementację kolejek priorytetowych.
W związku z tym będziemy używać struktury danych sterty do implementacji kolejki priorytetów w tym samouczku. Maksymalna sterta jest implementowana w następujących operacjach. Jeśli chcesz dowiedzieć się więcej na ten temat, odwiedź strony max-heap i mean-heap.
Poniżej przedstawiono analizę porównawczą różnych implementacji kolejki priorytetowej.
| Operacje | zerkać | wstawić | usunąć |
|---|---|---|---|
| Połączona lista | O(1) | O(n) | O(1) |
| Binary Heap | O(1) | O(log n) | O(log n) |
| Drzewo wyszukiwania binarnego | O(1) | O(log n) | O(log n) |
Operacje na kolejkach priorytetowych
Podstawowe operacje kolejki priorytetowej to wstawianie, usuwanie i podglądanie elementów.
Przed przestudiowaniem kolejki priorytetowej zapoznaj się ze strukturą danych sterty, aby lepiej zrozumieć stertę binarną, która jest używana do implementacji kolejki priorytetów w tym artykule.
1. Wstawianie elementu do kolejki priorytetowej
Wstawienie elementu do kolejki priorytetowej (max-heap) odbywa się w następujący sposób.
- Wstaw nowy element na końcu drzewka.
Wstaw element na końcu kolejki - Ułóż drzewo.
Heapify po wstawieniu
Algorytm wstawiania elementu do kolejki priorytetowej (max-heap)
Jeśli nie ma węzła, utwórz newNode. w przeciwnym razie (węzeł już istnieje) wstaw nowy węzeł na końcu (ostatni węzeł od lewej do prawej).
W przypadku sterty minimalnej powyższy algorytm jest modyfikowany tak, aby parentNodebył zawsze mniejszy niż newNode.
2. Usuwanie elementu z kolejki priorytetowej
Usunięcie elementu z kolejki priorytetowej (max-heap) odbywa się w następujący sposób:
- Wybierz element do usunięcia.
Wybierz element do usunięcia - Zamień go z ostatnim elementem.
Zamień z ostatnim elementem węzła liścia - Usuń ostatni element.
Usuń ostatni liść elementu - Ułóż drzewo.
Przygotuj kolejkę priorytetową
Algorytm usuwania elementu w kolejce priorytetowej (max-heap)
Jeśli nodeToBeDeleted jest leafNode usuń węzeł Inaczej zamień węzeł nodeToBeDeleted z lastLeafNode usuń noteToBeDeleted heapify the array
W przypadku sterty Min, powyższy algorytm jest modyfikowany tak, że oba childNodessą mniejsze niż currentNode.
3. Zerkanie z kolejki priorytetowej (znajdź maks./min)
Operacja Peek zwraca maksymalny element z Max Heap lub minimalny element z Min Heap bez usuwania węzła.
Zarówno dla sterty Max, jak i sterty min
zwraca rootNode
4. Wyodrębnij-Max / Min z kolejki priorytetowej
Extract-Max zwraca węzeł z maksymalną wartością po usunięciu go z Max Heap, natomiast Extract-Min zwraca węzeł z minimalną wartością po usunięciu go z Min Heap.
Implementacje kolejki priorytetowej w językach Python, Java, C i 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); )
Aplikacje kolejki priorytetowej
Oto niektóre zastosowania kolejki priorytetowej:
- Algorytm Dijkstry
- do implementacji stosu
- do równoważenia obciążenia i obsługi przerwań w systemie operacyjnym
- do kompresji danych w kodzie Huffmana
