Struttura dati Heap: cos'è l'heap?

Che cos'è una struttura dati heap?

Un heap è una struttura dati ad albero specializzata. La struttura dati heap è composta da un nodo superiore chiamato radice (genitore). Il suo secondo nodo è 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 genitore viene confrontata con quella del suo figlio in modo da garantire un ordinamento corretto. L'albero è facile da visualizzare: ogni entità è chiamata nodo e ogni nodo ha una chiave univoca per l'identificazione.

In termini semplici, un heap è un albero binario completo che soddisfa la proprietà heap: ogni nodo padre è ordinato in modo coerente rispetto ai suoi figli, il che lo rende ideale per code di priorità e per l'algoritmo di ordinamento heap.

Perché hai bisogno della struttura dei dati heap?

Ecco i motivi principali per utilizzare un Heap:

• La struttura dati Heap consente la cancellazione e l'inserimento in tempo logaritmico – O(log₂N).
• I dati nella struttura ad albero sono organizzati secondo un ordine specifico. Oltre ad aggiornare o interrogare valori come il massimo o il minimo, il programmatore può individuare le relazioni tra il nodo padre e i nodi figli.
• Puoi applicare il concetto di Modello oggetto documento per aiutarti a comprendere visivamente la struttura dati dell'heap.
• Gli heap supportano operazioni efficienti sulle code di priorità, fondamentali per algoritmi sui grafi come l'algoritmo di Dijkstra per il percorso più breve e l'algoritmo di Prim per l'albero di copertura minimo.

Tipi di cumuli

La struttura dati Heap ha vari algoritmi per gestire inserimenti e rimozione di elementi, tra cui coda di priorità, heap binario, heap binomiale e Ordinamento heap.

• Coda prioritaria: È un assolutotracStruttura dati contenente oggetti prioritari. A ciascun oggetto o elemento è assegnata una priorità predefinita. Pertanto, l'oggetto o l'elemento a cui è stata assegnata la priorità più alta riceve il servizio prima degli altri.
• Heap binario: Gli heap binari sono adatti per operazioni semplici come cancellazioni e inserimenti. Sono l'implementazione predefinita alla base della maggior parte delle code di priorità della libreria standard.
• Heap binomiale: Un heap binomiale è costituito da una serie di collezioni di alberi binomiali che formano l'heap. Un albero di heap binomiale non è un albero ordinario in quanto è definito rigorosamente. Il numero totale di elementi in un albero binomiale è sempre uguale a 2.ⁿ i nodi.
• Ordinamento a heap: A differenza della maggior parte degli algoritmi di ordinamento, l'Heap Sort utilizza uno spazio O(1) per la sua operazione di ordinamento. Si tratta di un algoritmo di ordinamento basato sul confronto, in cui l'ordinamento avviene in ordine crescente, trasformando prima l'input in un Max-Heap. È possibile considerare l'Heap Sort come una versione migliorata dell'albero di ricerca binario.

In genere, una struttura dati Heap impiega due strategie. Per l'input 12 – 8 – 4 – 2 e 1:

• Min-Heap – il valore più basso si trova in alto
• Max Heap – il valore più alto in alto

Min-Heap

Nella struttura Min-Heap, il nodo radice ha un valore uguale o inferiore a quello dei suoi figli. La radice di un Min-Heap contiene quindi il valore minimo. Il Min-Heap è anche un albero binario completo.

Una volta ottenuto un Min-Heap in un albero, tutte le foglie sono candidate valide per il valore massimo. Tuttavia, è necessario esaminare ogni foglia per ottenere il valore esatto del Max-Heap.

Esempio di Min-Heap

Nel diagramma qui sopra, si può notare una chiara sequenza dalla radice al nodo più basso.

Supponiamo di memorizzare gli elementi nell'array Array_N[12, 2, 8, 1, 4]. Come si può vedere dall'array, l'elemento radice viola la priorità Min-Heap. Per mantenere la proprietà Min-Heap, è necessario eseguire operazioni di min-heapify per scambiare gli elementi fino a quando le regole Min-Heap non vengono rispettate.

Max Heap

Nella struttura Max-Heap, il nodo padre o radice ha un valore uguale o maggiore di quello dei suoi figli. Questo nodo contiene il valore massimo. Si tratta di un albero binario completo, quindi è possibile costruire un Max-Heap a partire da una collezione di valori in tempo O(n).

Ecco alcuni metodi comunemente utilizzati durante l'implementazione di un Java Max-Heap:

• Aggiungere (): Inserisce 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 promosso non è più il più grande, il metodo Sift-Down lo sposta sempre nella sua nuova posizione.
• Setacciare (): Questo metodo confronta un oggetto radice con i suoi figli e quindi sposta il nodo riposizionato 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 posizione corretta. Il nuovo elemento viene prima confrontato con il suo elemento padre simulando la struttura dati ad albero.

  Applica la formula Parent_Index = Child_Index / 2. Continua a farlo finché l'elemento massimo non si trova all'inizio dell'array.

Heap di base Operazioni

Per trovare i valori più alti e più bassi in un insieme di dati, sono necessarie alcune operazioni di base sull'heap, come find, insert ed delete. Poiché gli elementi entrano ed escono continuamente, è importante sapere come:

• 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. Data una lista di chiavi, il programmatore crea un heap vuoto e poi inserisce le altre chiavi una alla volta utilizzando le operazioni di base sugli heap.

Iniziamo quindi a costruire un Min-Heap utilizzando il metodo di William, inserendo i valori 12, 2, 8, 1 e 4. È possibile costruire l'heap con n elementi partendo da un heap vuoto e riempiendolo successivamente con altri elementi in un tempo O(n log n).

• Heapify: Una routine di inserimento che consente di inserire elementi in un heap preservandone le proprietà.

  Ad esempio, un'operazione max-heapify verifica che il valore del genitore sia maggiore di quello del figlio. Gli elementi possono quindi essere ordinati utilizzando metodi come lo scambio.ping.

• Merge: Quando si devono combinare due heap in uno solo, si utilizza l'operazione di unione per unire i valori dei due heap. Gli heap originali vengono comunque preservati.

Ispeziona gli heap

L'ispezione degli heap consiste nel verificare il numero di elementi nella struttura dati heap e nel convalidare se l'heap è vuoto.

È importante ispezionare gli heap durante l'ordinamento o l'accodamento degli elementi. Verificare la presenza di elementi da elaborare tramite il metodo Is-Empty() è fondamentale. La dimensione dell'heap aiuta a individuare le radici di Max-Heap o Min-Heap, quindi è necessario sapere quanti elementi seguono la proprietà heap.

• Taglia – restituisce la grandezza o la lunghezza dell'heap. Indica quanti elementi sono memorizzati in ordine ordinato.
• È vuoto – restituisce TRUE se l'heap è nullo, 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 dati heap è utile in molte applicazioni di programmazione nella vita reale, come ad esempio:

• Aiuta a filtrare lo spam.
• Implementazione di algoritmi sui grafi come Dijkstra e Prim.
• Operabilanciamento del carico del sistema e compressione dei dati.
• Calcolo delle statistiche d'ordine, come ad esempio il k-esimo elemento più piccolo.
• Implementazione di code di priorità che consentono di cercare elementi in un elenco in tempo logaritmico.
• La struttura dati Heap viene utilizzata anche per l'ordinamento tramite l'algoritmo Heap Sort.
• Simulazione di clienti in coda.
• Gestione delle interruzioni nel Operasistema di ting.
• Nella codifica di Huffman per la compressione dei dati.
• Potenziare la ricerca best-first e l'euristica A* nella pianificazione dei percorsi tramite intelligenza artificiale.

Proprietà della coda con priorità heap

Le seguenti proprietà descrivono il comportamento della coda di priorità costruita su un heap:

• Negli heap di priorità, gli elementi di dati nell'elenco vengono confrontati tra loro per determinare l'elemento più piccolo o più grande.
• Un elemento viene inserito in una coda e successivamente rimosso in ordine di priorità.
• Ogni singolo elemento nella coda di priorità ha un numero univoco ad esso associato, che ne identifica la priorità.
• Quando si esce da una coda di priorità, l'elemento con la priorità più alta esce per primo.

Passaggi per implementare la coda di priorità dell'heap in Java

La sezione successiva si sposta in cemento Java implementazione che trasforma queste regole in codice funzionante.

Ordinamento heap Java con Code Esempio

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 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 Code Esempio

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.

DOMANDE FREQUENTI