Struttura dei dati heap: cos'è l'heap? Heap minimo e massimo (esempio)
Cos'è un mucchio?
L'heap è una struttura dati ad albero specializzata. L'heap comprende il nodo più in alto chiamato radice (padre). Il suo secondo figlio è il figlio sinistro della radice, mentre il terzo nodo è il figlio destro della radice. I nodi successivi vengono riempiti da sinistra a destra. La chiave del nodo padre viene confrontata con quella della sua prole e si verifica una disposizione appropriata. L'albero è facile da visualizzare dove ogni entità è chiamata nodo. Il nodo ha chiavi univoche per l'identificazione.
Perché hai bisogno della struttura dei dati heap?
Ecco i motivi principali per utilizzare la struttura dei dati heap:
- La struttura dei dati heap consente la cancellazione e l'inserimento in tempo logaritmico – O(log2N).
- I dati nell'albero sono disposti in un ordine particolare. Oltre ad aggiornare o interrogare elementi come il massimo o il minimo, il programmatore può trovare relazioni tra il genitore e il figlio.
- Puoi applicare il concetto di Modello oggetto documento per aiutarti a comprendere la struttura dei dati dell'heap.
Tipi di cumuli
La struttura dei dati heap ha vari algoritmi per gestire gli inserimenti e la rimozione di elementi in una struttura dei dati heap, inclusi Priority-Queue, Binary-Heap, Binomial Heap e Heap-Ordinamento.
- Coda prioritaria: È una struttura dati astratta contenente oggetti con priorità. Ogni oggetto o articolo ha una priorità prestabilita per esso. Pertanto, l'oggetto o l'articolo a cui è stata assegnata la priorità più alta riceve il servizio prima degli altri.
- Heap binario: Gli heap binari sono adatti per operazioni heap semplici come eliminazioni e inserimenti.
- Heap binomiale: Un heap binomiale è costituito da una serie di raccolte di alberi binomiali che compongono l'heap. L'albero dell'heap binomiale non è un albero ordinario poiché è rigorosamente definito. Il numero totale di elementi in un albero binomiale possiede sempre 2n i nodi.
- Heap-Ordinamento: A differenza della maggior parte degli algoritmi di ordinamento, heap-sort utilizza lo spazio O(1) per le sue operazioni di ordinamento. È un algoritmo di ordinamento basato sul confronto in cui l'ordinamento avviene in ordine crescente trasformandolo prima in un heap massimo. Puoi considerare Heapsort come un albero di ricerca binario di qualità aggiornata.
In genere, una struttura di dati heap utilizza due strategie. Per gli ingressi 12 – 8 – 4 – 2 e 1
- Min Heap: valore minimo in alto
- Max Heap: valore più alto in alto
Mucchio minimo
Nella struttura Min Heap, il nodo radice ha un valore uguale o inferiore ai figli su quel nodo. Questo nodo heap di un Min Heap contiene il valore minimo. Tutto sommato, la sua struttura min-heap è completa albero binario.
Una volta che hai un heap Min in un albero, tutte le foglie sono candidate valide. Tuttavia, è necessario esaminare ciascuna foglia per ottenere l'esatto valore Max-heap.
Esempio di heap minimo
Nei diagrammi sopra puoi notare una sequenza chiara dalla radice al nodo più basso.
Supponiamo di memorizzare gli elementi in Array Array_N[12,2,8,1,4]. Come puoi vedere dall'array, l'elemento radice viola la priorità Min Heap. Per mantenere la proprietà Min heap, devi eseguire le operazioni min-heapify per scambiare gli elementi finché non vengono soddisfatte le proprietà Min heap.
Mucchio massimo
Nella struttura di Max Heap, il nodo genitore o radice ha un valore uguale o maggiore dei suoi figli nel nodo. Questo nodo contiene il valore massimo. Inoltre, è un albero binario completo, quindi puoi creare un heap massimo da una raccolta di valori ed eseguirlo in tempo O(n).
Ecco alcuni metodi per implementare un heap Java Max
- Aggiungere (): posiziona un nuovo elemento in un heap. Se si utilizza un array, gli oggetti vengono aggiunti alla fine dell'array, mentre nell'albero binario gli oggetti vengono aggiunti dall'alto verso il basso e poi da sinistra a destra.
- Rimuovi (): Questo metodo consente di rimuovere il primo elemento dall'elenco dell'array. Poiché l'elemento appena aggiunto non è più il più grande, il metodo Sift-Down lo spinge sempre nella sua nuova posizione.
- Setacciare (): Questo metodo confronta un oggetto radice con il suo figlio e poi spinge il nodo appena aggiunto nella sua posizione corretta.
- Setacciare (): se si utilizza il metodo array per aggiungere un elemento appena inserito a un array, il metodo Sift-Up aiuta il nodo appena aggiunto a riposizionarsi nella sua nuova posizione. L'elemento appena inserito viene prima confrontato con quello genitore simulando la struttura dati dell'albero.
Applica la formula Parent_Index=Child_Index/2. Continua a farlo finché l'elemento massimo non si trova nella parte anteriore dell'array.
Heap di base Operazioni
Per trovare i valori più alti e più bassi in un insieme di dati, sono necessarie molte operazioni heap di base come trovare, eliminare e inserire. Poiché gli elementi vanno e vengono costantemente, devi:
- Trovate – Cerca un oggetto in un mucchio.
- inserire – Aggiungi un nuovo figlio nell'heap.
- Elimina – Elimina un nodo da un heap.
Crea cumuli
Il processo di costruzione degli heap è noto come creazione di heap. Dato un elenco di chiavi, il programmatore crea un heap vuoto e quindi inserisce le altre chiavi una alla volta utilizzando le operazioni heap di base.
Quindi iniziamo a costruire un Min-heap utilizzando il metodo di Willaim inserendo i valori 12,2,8,1 e 4 in un heap. Puoi costruire l'heap con n elementi iniziando con un heap vuoto e poi riempiendolo successivamente con altri elementi usando il tempo O (nlogn).
- Heapify: nell'algoritmo di inserimento, che aiuta a inserire elementi in un heap. Controlla se la struttura dati dell'heap delle proprietà evidenziata è seguita.
Ad esempio, un max heapify verificherebbe se il valore del genitore è maggiore del suo figlio. Gli elementi possono quindi essere ordinati usando metodi come lo swapping.
- Unisci: considerando che hai due heap da combinare in uno solo, usa unisci heap per riunire i valori dei due heap. Tuttavia, i cumuli originali sono ancora conservati.
Ispeziona gli heap
L'ispezione degli heap si riferisce al controllo del numero di elementi nella struttura dei dati dell'heap e alla verifica se l'heap è vuoto.
È importante ispezionare gli heap come ordinamento o messa in coda di elementi. È importante controllare se hai elementi da elaborare usando Is-Empty(). La dimensione dell'heap aiuterà a individuare il max-heap o il min-heap. Quindi, devi conoscere gli elementi che seguono la proprietà heap.
- Taglia – restituisce la grandezza o la lunghezza dell'heap. Puoi dire quanti elementi sono in ordine.
- È vuoto – se l'heap è NULL, restituisce TRUE altrimenti restituisce FALSE.
Qui stai stampando tutti gli elementi nel file prioritàQ loop e quindi controllando che prioritàQ non sia vuota.
//print head the head values While (!priorityQ.isEmpty()) { System.out.print(priorityQ.poll()+" ");
Usi della struttura dei dati heap
La struttura dei dati heap è utile in molte applicazioni di programmazione nella vita reale come:
- Aiuta nel filtraggio dello spam.
- Implementazione di algoritmi grafici.
- Operating il bilanciamento del carico del sistema e la compressione dei dati.
- Trova l'ordine nelle statistiche.
- Implementa le code prioritarie in cui puoi cercare elementi in un elenco in tempo logaritmico.
- La struttura dei dati heap viene utilizzata anche per l'ordinamento.
- Simulare i clienti su una linea.
- Gestione delle interruzioni in Operasistema di ting.
- Nella codifica di Huffman per la compressione dei dati.
Proprietà della coda con priorità heap
- Negli heap di priorità, gli elementi di dati nell'elenco vengono confrontati tra loro per determinare l'elemento più piccolo.
- Un elemento viene messo in coda e poi rimosso.
- Ogni singolo elemento della Coda di Priorità ha un numero univoco ad esso correlato identificato come prioritario.
- All'uscita da una coda prioritaria, l'elemento con priorità più alta esce per primo.
Passaggi per l'implementazione della coda di priorità dell'heap in Java
Ordinamento heap in JAVA con esempio di codice
import java.util.Arrays; public class HeapSort { public static void main(String[] args) { int[] arr = {5, 9, 3, 1, 8, 6}; // Sort the array using heap sort heapSort(arr); // Print the sorted array System.out.println(Arrays.toString(arr)); } public static void heapSort(int[] arr) { // Convert the array into a heap for (int i = arr.length / 2 - 1; i >= 0; i--) { heapify(arr, arr.length, i); } // Extract the maximum element from the heap and place it at the end of the array for (int i = arr.length - 1; i >= 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } } public static void heapify(int[] arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; // Find the largest element among the root, left child, and right child if (left < n && arr[left] > arr[largest]) { largest = left; } if (right < n && arr[right] > arr[largest]) { largest = right; } // If the largest element is not the root, swap the root and the largest element and heapify the sub-tree if (largest != i) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapify(arr, n, largest); } } }
Uscita
Original Array: 5 9 3 1 8 6 Heap after insertion: 9 8 6 1 5 3 Heap after sorting: 1 3 5 6 8 9
Ordinamento heap Python con esempio di codice
def heap_sort(arr): """ Sorts an array in ascending order using heap sort algorithm. Parameters: arr (list): The array to be sorted. Returns: list: The sorted array. """ n = len(arr) # Build a max heap from the array for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) # Extract elements from the heap one by one for i in range(n - 1, 0, -1): arr[0], arr[i] = arr[i], arr[0] # swap the root with the last element heapify(arr, i, 0) # heapify the reduced heap return arr def heapify(arr, n, i): """ Heapifies a subtree with the root at index i in the given array. Parameters: arr (list): The array containing the subtree to be heapified. n (int): The size of the subtree. i (int): The root index of the subtree. """ largest = i # initialize largest as the root left = 2 * i + 1 # left child index right = 2 * i + 2 # right child index # If left child is larger than root if left < n and arr[left] > arr[largest]: largest = left # If right child is larger than largest so far if right < n and arr[right] > arr[largest]: largest = right # If largest is not root if largest != i: arr[i], arr[largest] = ( arr[largest], arr[i], ) # swap the root with the largest element heapify(arr, n, largest) # recursively heapify the affected subtree arr = [4, 1, 3, 9, 7] sorted_arr = heap_sort(arr) print(sorted_arr)
Uscita
[1, 3, 4, 7, 9]
Successivamente imparerai a conoscere Metodo della bisezione
Sommario
- L'heap è una struttura dati ad albero specializzata. Immaginiamo un albero genealogico con i suoi genitori e figli.
- La struttura dei dati heap in Java permette la cancellazione e l'inserimento in tempo logaritmico – O(log2N).
- Cumuli dentro Python ha vari algoritmi per la gestione degli inserimenti e la rimozione di elementi in una struttura di dati heap, inclusi Priority-Queue, Binary-Heap, Binomial Heap e Heapsort.
- Nella struttura Min Heap, il nodo radice ha un valore uguale o inferiore ai figli su quel nodo.
- Nella struttura di Max Heap, il nodo radice (genitore) ha un valore uguale o maggiore dei suoi figli nel nodo.
- L'ispezione degli heap si riferisce al controllo del numero di elementi nella struttura dei dati dell'heap e alla verifica se l'heap è vuoto.