heapify complessità

[gepeppe]

salve a tutti, potreste spiegarmi perchè la complessità dell'heapify è O(log n)??? non capisco come si arriva a questo risultato, anche leggendo più slide su internet...

grazie

[Ziosilvio]

Prova a chiedere QUI.

[pietro84]

Originariamente inviato da gepeppe

salve a tutti, potreste spiegarmi perchè la complessità dell'heapify è O(log n)??? non capisco come si arriva a questo risultato, anche leggendo più slide su internet...

grazie

se per heapify intendi la procedura che costruisce un heap a partire da un generico array di n elementi, allora la complessita e` O(n).
La complessita` della procedura che trova e cancella il massimo in un heap e` invece O(logn), penso che tu abbia confuso le due cose....

[gepeppe]

Originariamente inviato da pietro84

se per heapify intendi la procedura che costruisce un heap a partire da un generico array di n elementi, allora la complessita e` O(n).
La complessita` della procedura che trova e cancella il massimo in un heap e` invece O(logn), penso che tu abbia confuso le due cose....

heapify è la procedura che ripristina lo heap, quella che dici tu è costruisci-heap...ecco qui è descritta la complessità di heapify: http://people.na.infn.it/~bene/ASD/B...heapsort-2.pdf

cmq ora chiedo nell'altro thread che mi avete consigliato

grazie

[pietro84]

Originariamente inviato da gepeppe

heapify è la procedura che ripristina lo heap, quella che dici tu è costruisci-heap...ecco qui è descritta la complessità di heapify: http://people.na.infn.it/~bene/ASD/B...heapsort-2.pdf

cmq ora chiedo nell'altro thread che mi avete consigliato

grazie

ah, allora forse intendi la procedura che io ad algoritmi chiamavo "fixHeap" ?!
ricordo che la complessità è O(logn) perchè il numero di confronti richiesti è pari all'altezza dell'albero, che è O(logn).