V tomto kurzu se dozvíte, co je prioritní fronta. Také se dozvíte o jeho implementacích v Pythonu, Javě, C a C ++.
Fronta priority je speciální typ fronty, ve které je každý prvek spojen s prioritou a je obsluhován podle jeho priority. Pokud se vyskytnou prvky se stejnou prioritou, jsou obsluhovány podle jejich pořadí ve frontě.
Obecně se pro přiřazení priority zohledňuje hodnota samotného prvku.
Například prvek s nejvyšší hodnotou je považován za prvek s nejvyšší prioritou. V ostatních případech však můžeme jako prvek s nejvyšší prioritou předpokládat prvek s nejnižší hodnotou. V ostatních případech můžeme stanovit priority podle našich potřeb.
Odebrání prvku s nejvyšší prioritou
Rozdíl mezi prioritní frontou a normální frontou
Ve frontě je implementováno pravidlo first-in-first-out, zatímco ve prioritní frontě jsou hodnoty odstraněny na základě priority . Nejprve se odstraní prvek s nejvyšší prioritou.
Implementace prioritní fronty
Prioritní frontu lze implementovat pomocí pole, propojeného seznamu, datové struktury haldy nebo binárního vyhledávacího stromu. Mezi těmito datovými strukturami poskytuje halda datová struktura efektivní implementaci prioritních front.
Proto budeme v tomto kurzu používat datovou strukturu haldy k implementaci prioritní fronty. Maximální hromada je implementována v následujících operacích. Pokud se o tom chcete dozvědět více, navštivte stránky max-heap a mean-heap.
Níže je uvedena srovnávací analýza různých implementací prioritní fronty.
| Operace | nahlédnout | vložit | vymazat |
|---|---|---|---|
| Spojový seznam | O(1) | O(n) | O(1) |
| Binární halda | O(1) | O(log n) | O(log n) |
| Binární vyhledávací strom | O(1) | O(log n) | O(log n) |
Prioritní operace fronty
Základní operace prioritní fronty jsou vkládání, odebírání a prohlížení prvků.
Před prostudováním prioritní fronty si přečtěte strukturu dat haldy, abyste lépe porozuměli binární haldě, protože se používá k implementaci prioritní fronty v tomto článku.
1. Vložení prvku do prioritní fronty
Vložení prvku do prioritní fronty (max-heap) se provádí podle následujících kroků.
- Vložte nový prvek na konec stromu.
Vložte prvek na konec fronty - Heapify strom.
Po vložení heapify
Algoritmus pro vložení prvku do prioritní fronty (max. Halda)
Pokud neexistuje žádný uzel, vytvořte nový uzel. else (uzel je již přítomen) vložte novýNode na konec (poslední uzel zleva doprava) heapify pole
U Min Heap je výše uvedený algoritmus upraven tak, aby parentNodebyl vždy menší než newNode.
2. Odstranění prvku z prioritní fronty
Odstranění prvku z prioritní fronty (max-heap) se provádí následovně:
- Vyberte prvek, který chcete odstranit.
Vyberte prvek, který chcete odstranit - Zaměňte jej za poslední prvek.
Zaměňte s posledním prvkem uzlu listu - Odeberte poslední prvek.
Odstraňte poslední list prvku - Heapify strom.
Heapify prioritní frontu
Algoritmus pro odstranění prvku v prioritní frontě (max. Halda)
Pokud nodeToBeDeleted je leafNode odebrat uzel Else swap nodeToBeDeleted s lastLeafNode odebrat noteToBeDeleted heapify pole
U Min Heap je výše uvedený algoritmus upraven tak, aby oba childNodesbyly menší než currentNode.
3. Prohlížení z prioritní fronty (Najít max / min)
Peek operace vrátí maximální prvek z Max Heap nebo minimální prvek z Min Heap bez odstranění uzlu.
Pro haldy Max i Min Haldy
vrátit rootNode
4. Extrahujte - Max / Min z prioritní fronty
Extract-Max vrátí uzel s maximální hodnotou po odebrání z Max Heap, zatímco Extract-Min vrátí uzel s minimální hodnotou po odebrání z Min Heap.
Implementace prioritních front v Pythonu, Javě, C a 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); )
Aplikace prioritní fronty
Některé z aplikací prioritní fronty jsou:
- Dijkstrův algoritmus
- pro implementaci zásobníku
- pro vyrovnávání zatížení a zpracování přerušení v operačním systému
- pro kompresi dat v Huffmanově kódu
