Tag: Heapsort

Heapsort – costo computazionale

su da frippin Algoritmi, Heapsort, Informatica, Matematica, Ordinamento12 commenti

Per dimostrare che il costo computazionale dello heapsort è O(n \log n) occorre prima dimostrare alcune proprietà dello heap.

Proprietà 1

Uno heap con n nodi ha altezza \Theta(\log n)

Dimostrazione:

Sia h il numero di livello dello heap. I primi (h-1) livelli sono tutti completi, e il numero di nodi in esso contenuti è pari a \sum_{i=0}^{h-1}2^{i}=2^{h}-1.

In maniera analoga, il numero di nodi in h livelli è \leq 2^{h+1}-1.

Da questo concludiamo che 2^{h}-1 \leq n \leq 2^{h+1}-1.

Prendendo il logaritmo di ambo i membri otteniamo che h=\Theta(\log n)
Continua a leggere “Heapsort – costo computazionale” →

Heapsort – implementazione

su da frippin Algoritmi, C, Heapsort, Informatica, Ordinamento, ProgrammazioneLascia un commento

L’heapsort è un efficiente metodo di ordinamento caratterizzato da un costo computazionale nel caso peggiore pari a O(n \log n). Lo heapsort rientra nella classe degli algoritmi di ordinamento basati sui confronti e ha la particolarità di sfruttare una particolare struttura dati, lo heap binario.

Ecco la definizione formale di heap binario:
Continua a leggere “Heapsort – implementazione” →