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 (http://www.hwupgrade.it/forum/showthread.php?t=1321413).

[pietro84]

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]

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/Benerecetti/Modulo-I-2006-2007/4-heapsort-2.pdf

cmq ora chiedo nell'altro thread che mi avete consigliato

grazie

[pietro84]

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/Benerecetti/Modulo-I-2006-2007/4-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).