In questo tutorial imparerai cos'è la coda di priorità. Inoltre, imparerai le sue implementazioni in Python, Java, C e C ++.
Una coda con priorità è un tipo speciale di coda in cui ogni elemento è associato a una priorità ed è servito in base alla sua priorità. Se si verificano elementi con la stessa priorità, vengono serviti in base al loro ordine nella coda.
Generalmente, il valore dell'elemento stesso viene considerato per l'assegnazione della priorità.
Ad esempio, l'elemento con il valore più alto è considerato l'elemento con la priorità più alta. Tuttavia, in altri casi, possiamo assumere l'elemento con il valore più basso come elemento con la priorità più alta. In altri casi, possiamo stabilire le priorità in base alle nostre esigenze.
Rimozione dell'elemento di priorità più alta
Differenza tra coda prioritaria e coda normale
In una coda viene implementata la regola first-in-first-out mentre, in una coda prioritaria, i valori vengono rimossi in base alla priorità . L'elemento con la priorità più alta viene rimosso per primo.
Implementazione della coda prioritaria
La coda prioritaria può essere implementata utilizzando un array, un elenco collegato, una struttura dati heap o un albero di ricerca binario. Tra queste strutture di dati, la struttura di dati di heap fornisce un'implementazione efficiente delle code di priorità.
Quindi, utilizzeremo la struttura dei dati dell'heap per implementare la coda di priorità in questo tutorial. Un max-heap è implementato nelle seguenti operazioni. Se vuoi saperne di più, visita max-heap e mean-heap.
Di seguito viene fornita un'analisi comparativa delle diverse implementazioni della coda di priorità.
| Operazioni | sbirciare | inserire | Elimina |
|---|---|---|---|
| Lista collegata | O(1) | O(n) | O(1) |
| Heap binario | O(1) | O(log n) | O(log n) |
| Albero di ricerca binario | O(1) | O(log n) | O(log n) |
Priorità delle operazioni in coda
Le operazioni di base di una coda prioritaria sono l'inserimento, la rimozione e la visualizzazione di elementi.
Prima di studiare la coda di priorità, fare riferimento alla struttura dei dati dell'heap per una migliore comprensione dell'heap binario così come viene utilizzato per implementare la coda di priorità in questo articolo.
1. Inserimento di un elemento nella coda prioritaria
L'inserimento di un elemento in una coda di priorità (max-heap) viene eseguito tramite i passaggi seguenti.
- Inserisci il nuovo elemento alla fine dell'albero.
Inserisci un elemento alla fine della coda - Riempi l'albero.
Heapify dopo l'inserimento
Algoritmo per l'inserimento di un elemento nella coda di priorità (max-heap)
Se non è presente alcun nodo, creare un newNode. altrimenti (un nodo è già presente) inserire il newNode alla fine (l'ultimo nodo da sinistra a destra). heapify l'array
Per Min Heap, l'algoritmo precedente viene modificato in modo che parentNodesia sempre inferiore a newNode.
2. Eliminazione di un elemento dalla coda prioritaria
L'eliminazione di un elemento da una coda di priorità (max-heap) viene eseguita come segue:
- Seleziona l'elemento da eliminare.
Seleziona l'elemento da eliminare - Scambialo con l'ultimo elemento.
Scambia con l'ultimo elemento del nodo foglia - Rimuovi l'ultimo elemento.
Rimuovere l'ultimo elemento foglia - Riempi l'albero.
Heapify la coda di priorità
Algoritmo per la cancellazione di un elemento nella coda di priorità (max-heap)
Se nodeToBeDeleted è il leafNode rimuovi il nodo Else scambia nodeToBeDeleted con lastLeafNode rimuovi noteToBeDeleted heapify l'array
Per Min Heap, l'algoritmo precedente viene modificato in modo che entrambi childNodessiano più piccoli di currentNode.
3. Sbirciare dalla coda prioritaria (trova max / min)
L'operazione Peek restituisce l'elemento massimo da Heap massimo o l'elemento minimo da Heap minimo senza eliminare il nodo.
Sia per Max heap che per Min Heap
restituisce rootNode
4. Estrai-Max / Min dalla coda di priorità
Extract-Max restituisce il nodo con il valore massimo dopo averlo rimosso da un Heap Max mentre Extract-Min restituisce il nodo con il valore minimo dopo averlo rimosso da Min Heap.
Implementazioni di code prioritarie in Python, Java, C e 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); )
Applicazioni in coda prioritaria
Alcune delle applicazioni di una coda prioritaria sono:
- Algoritmo di Dijkstra
- per implementare lo stack
- per il bilanciamento del carico e la gestione degli interrupt in un sistema operativo
- per la compressione dei dati nel codice Huffman
