Come costruire gli Heaps binari ~ L'università è facile

Salve a tutti oggi si parla di heaps binari. Cosa sono e come vano creati.

Un heap è un array che può essere visualizzato come un albero binario quasi completo .

Quasi completo significa che tutti i livelli ,tranne l'ultimo,sono completi:possono mancare alcune foglie consecutive a partire dall'ultima foglia a destra

Esempio in immagine :

Un array che rappresenta un heap binario è un oggetto con
due attributi:
length[A] `e il numero di elementi (la dimensione) dell’array
heap-size[A] `e il numero di elementi dell’heap memorizzati
nell’array

Ci sono 2 cose fondamentali da sapere sugli heaps :

1. La radice dell’albero è A[1] (si trova in posizione 1)

2. Le operazioni per ricavare il padre Padre[i] ,il figlio destro destro[i] e il figlio sinistro sinistro[i] di un nodo i sono:

Padre[i]

return parte intera(i/2)

sinistro[i]

return 2i

destro[i]

return 2i+1

Ecco un esempio di heap binario con la sua visualizzazione in albero binario:

Esistono due tipi di heap binari: max-heap e min-heap
In entrambi i tipi di heap binario, i valori dei nodi soddisfano
una proprietà le cui caratteristiche dipendono dal tipo di heap

Proprietà del max-heap: in un max-heap ogni nodo i diverso
dalla radice `e tale che A[padre[i ]] >= A[i ]

Questa regola ha 2 conseguenze:

1: l’elemento più grande di un max-heap viene memorizzato nella
radice

2: un sottoalbero di un nodo u contiene nodi il cui valore non `e
mai maggiore del valore del nodo u

Il min-heap si comporta in modo duale ,quindi da ora in poi,parlando di heap,mi riferisco a max-heap.

Come costruire un heaps binario ?

Per costruire un heaps abbiamo bisogno di dell’algoritmo HEAPIFY.

Questo algoritmo ha per obbiettivo di mantenere la proprietà del heaps cioè

A[padre[i]] >=A[i]. Quindi come input abbiamo un array in un certo ordine e alla fine in output questo array sarà un heaps binario.

Principio dell’algoritmo:

Prima si cerca il massimo fra il nodo i e i suoi figli ,poi si sostituisce il nodo i con il massimo trovato e si richiama ricorsivamente l’algoritmo per il figlio che ha appena scambiato valore con i. Praticamente si va verso il basso.

largest è la variabile che rappresenta il massimo fra i due figli.

Costo dell’algoritmo.

Il costo di Heapify in un (sotto)albero di dimensione n è pari:
al tempo costante c necessario per stabilire il massimo fra gli
elementi A[i ], A[sinistro(i )] e A[destro(i )]
più il tempo per eseguire Heapify in un sottoalbero con radice
uno dei figli di i
La dimensione di ciascun sottoalbero non supera 2n/3 perché siamo in un albero quasi completo.
Il tempo di esecuzione di Heapify può essere espresso dalla
seguente ricorrenza
T(n)<= T(2n/3) + c
Per il teorema master, la soluzione di questa ricorrenza e O(log2 n)

Per la costruzione del heap utilizziamo Heapify su tutti i nodi fra

1 e parte intera(n/2). Perché?

Visto che tutte le foglie possono essere considerate heaps di dimensione 1,basta sistemare con Heapify tutti i nodi che non sono foglie in ordine decrescente.

Costo di Build-Heap :

Ogni chiamata costa O(log2n) ci sono O(n) chiamate quindi siamo a O(nlog2n)

Possiamo fare di meglio osservando che il tempo di esecuzione
di Heapify varia al variare dell’altezza del nodo nell’heap.

Un’analisi più rigorosa si basa sulle seguenti informazioni:
-uno heap di n elementi ha un’altezza di log2n
per ogni k = 0, . . . , log2n ci sono al più n/2k+1 nodi di
altezza k
-una chiamata di Heapify su un nodo di altezza k e O(k)
Il costo T(n) di Build-Heap e limitato da: