L'università è facile…

studia finché non lo diventa…

Come costruire gli Heaps binari

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:

image

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.

image

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.

image

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:

image

Dopo i calcoli ci rendiamo conto che il costo di Build-Heap è O(n).

Basta per oggi,Spero che hai imparato qualcosa leggendo questo articolo. Se hai dei dubbi o suggerimenti,lasca un commento qui sotto.

avatar firma

Annunci

3 commenti su “Come costruire gli Heaps binari

  1. rob
    10/10/2012

    non mi è ancora chiaro perchè nella funzoine di BUILD si divide il lenght a metà!!!

  2. Cristian
    13/09/2012

    molto utile e molto interessante! grazie

  3. Pingback: Le strutture dati di base in programmazione « L'università è facile…

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

Informazione

Questa voce è stata pubblicata il 17/06/2010 da in Algoritmi e strutture dati con tag , , , .
%d blogger hanno fatto clic su Mi Piace per questo: