Heap: cos’è, proprietà e come si costruisce

Che cos’è un heap?

Un heap (binario) è un albero binario quasi completo organizzato su un array. Per albero binario quasi completo si intente un albero binario addossato a sinistra, ovvero che

• ha tutte le foglie a profondità h o h-1, con h = altezza dell’albero
• tutti i nodi interni hanno due figli, eccetto al più uno
• il nodo con un solo figlio, se esiste, ha un solo figlio sinistro e si trova a profondità h-1, inoltre i nodi alla sua destra, se esistono, sono foglie

In realtà se analizziamo bene tali proprietà, notiamo che anche un albero binario completamente bilanciato può essere rappresentato su un heap.

Come è fatto l’array

Come anticipato questa struttura viene implementata su un array. Questo array viene descritto distinguendo la dimensione dell’heap, ovvero il numero di elementi che lo cosituiscono, e la dimensione stessa dell’array, che chiameremo rispettivamente A heapsize e A length.
Tra di essi vale sempre la seguente relazione:
A heapsize ≤ A length

Per identificare la posizione degli elementi dell’heap nell’array basti sapere che sono ordinati per profondità dell’albero a partire dalla radice, quindi alla posizione A[0] troveremo la radice, in A[1] troveremo suo figlio sinistro, in A[2] suo figlio destro, in A[3] troveremo il figlio sinistro del nodo in A[1] e così via.

Generalizzando possiamo dire che dato un nodo u[i]:

• l’indice di suo padre equivale a ⌊i/2​⌋ (parte intera inferiore)
• quello di suo figlio sinistro vale 2i
• mentre l’indice di suo figlio destro vale 2i+1​.

Precisiamo che nell’esempio proposto in precedenza abbiamo utilizzato gli indici a partire da i=0 per fare un confronto diretto con la numerazione nei linguaggi di programmazione, infatti in questo caso è necessario considerare tali regole generali aggiungendo +1 al valore ottenuto.

Proprietà di un heap

1) Un heap di n elementi ha altezza equivalente a circa O(log n), o se volessimo essere più precisi ⌊log n⌋.
2) Un heap di n nodi contiene ⌈n/2⌉ foglie.
3) In un heap di n nodi ci sono al massimo ⌈n / 2ⁿ⁺¹⌉ nodi di altezza h, oppure, se si tratta di un albero binario completo, esso ha esattamente ⌈n / 2ⁿ⁺¹⌉ nodi di altezza h.

Queste proprietà garantiscono che le operazioni fondamentali sugli heap impiegano tempo O(log n), quindi proporzionali all’altezza dello stesso heap.

Essendo un albero binario, anche di un heap possiamo specificare la sua dimensione, la sua altezza, l’altezza di ogni suo nodo e la profondità di ogni suo nodo, che vengono spiegati in questo articolo sugli alberi binari.

Tipologie di heap

Ne esistono due: max-heap e min-heap.
Il max-heap è organizzato in modo tale che, dato un nodo, il valore del nodo padre sia maggiore o uguale a tale nodo, ovvero che
A[PARENT(i)] ≥ A[i].
Il min-heap invece è il contrario del max-heap, ovvero che dato un nodo, il valore del nodo padre sia minore o uguale a tale nodo, quindi
A[PARENT(i)] ≤ A[i].

Noteremo allora che la radice di un albero contiene il valore più piccolo nel caso di un min-heap oppure il valore più grande nel caso di un max-heap.

Per mantenere queste proprietà è necessario utilizzare un algoritmo che si occupi di controllare ed eventualmente scambiare le posizioni dei valori nei vari indici, l’algoritmo in questione si chiama Max-Heapify (o Min-Heapify). Vediamo lo pseudo-codice di questa procedura ispirata dal libro Introduzione agli Algoritmi.

Max-Heapify(A, i)

    l = left(i)
    r = right(i)

    if (l ≤ A.heapsize and A[l] > A[i])
        largest = l
    else largest = i

    if (r ≤ A.heapsize and A[r] > A[largest])
        largest = r

    if (largest != i)
        exchange A[i] with A[largest]
        Max-Heapify(A, largest)

L’algoritmo prende in paramentro l’array e l’indice del nodo fuori posizione ed opera ricorsivamente finché non si verificano le condizioni richieste.
In particolare Max-Heapify opera secondo i seguenti passaggi:
1) assegna in l l’indice del figlio sinistro del nodo da riposizionare e in r l’indice del figlio destro;
2) nel primo controllo si verifica che l’indice l rientri effettivamente nella dimensione dell’heap e si controlla inoltre se il valore in A[l] è maggiore di A[i], ovvero il nodo preso in esame. In caso affermativo si memorizza nella variabile largest, altrimenti assegnamo a quest’ultima l’indice del nodo i;
3) nel secondo controllo si verifica che l’indice r rientri effettivamente nella dimensione dell’heap e si controlla inoltre se il valore in A[r] è maggiore di A[largest]. In caso affermativo si memorizza nella variabile largest il nuovo valore (A[r]).
4) l’ultimo controllo serve per verificare se è necessario scambiare i valori degli indici ed eventualmente effettuare la chiamata ricorsiva per effettuare i controlli sui livelli rimanenti, altrimenti la funzione termina.

Complessità: O(log n), facilmente dimostrabile con il Teorema dell’Esperto.

Costruire un heap

Possiamo utilizzare l’algoritmo appena descritto per creare un heap in un array, andando a riorganizzare gli elementi esistenti in esso.
L’algoritmo che esegue questa operazione si chiama Build Max-Heap (o Build Min-Heap) e integra al suo interno la procedura heapify.

Come funziona? Imponiamo prima la seguente condizione:
A heapsize = A length.
L’array viene “diviso” in due parti suppondendo che la parte sinistra abbia gli elementi da ordinare e la parte destra sia formata dalle foglie dell’albero.
L’algoritmo Build Max-Heap è abbastanza semplice: è costituito da un ciclo con al suo interno Max-Heapify che chiama gli elementi della parte destra dell’array a partire dalla fine. In questo modo riposiziona gli elementi dell’array partendo dalle foglie. Vediamo a breve in dettaglio come fa.
Scriviamo prima lo pseudocodice sempre preso dal libro Introduzione agli Algoritmi

Build-Max-Heap(A, i)

    A.heapsize = A.length
    for (i = ⌊A.length/2⌋ downto 1)
        Max-Heapify(A, i)

Funzionamento di Build Max-Heap

Supponiamo di avere un array A: 4, 1, 3, 2, 17, 9, 10, 14, 8, 7.
La seguente è una serie di immagini che rappresentano tutti i vari passaggi che vengono fatti dall’algoritmo per modificare tale array.

Build Max-Heap individua l’indice di mezzo distinguendo le due metà di cui abbiamo parlato, poi chiama Max-Heapify con il primo elemento, ovvero quello in posizione 5. In questa prima chiamata non fa niente, perché il sottoalbero formato dagli elementi 17 e 7 rispetta già le condizioni richieste.

Nella seconda chiamata, abbiamo che il valore nell’indice 4 non rispetta le regole di un heap e quindi i valori vengono scambiati con il figlio di valore maggiore.

Continua così fino a riposizionare il valore 4 inizialmente alla radice che attraversa poi tutto l’albero fino a diventare una foglia.

Complessità: O(n logn)

Heapsort?

Nel caso vi dovesse interessare qua abbiamo anche un articolo sull’heapsort!