Costruzione di un heapsort
Mi potete dare una mano a capire come si costruisce un heapsort?
Sulle dispense è riportato questo vettore da ordinare con heapsort
$5,13,2,25,7,17,20,8,4$
i passi dell'ordinamento che descrive sono:
$5,13$
$13,5,20$
$13,5,2,25$
$25,13,2,5,7$
$25,13,2,5,7,17$
$25,13,17,5,7,2,20$
$25,13,20,5,7,2,17,8$
$25,13,20,8,7,2,17,5,4$
$25,13,20,8,7,2,17,5,4$
ma non ho minimamente capito come si costruisce l'heap.
Quello che ho capito è che si fanno m operazioni di insert per costruire l'heap, e poi m operazioni di remove per ordinare il vettore, e durante il remove bisogna ripristinare la condizione di heap...ma non ho capito i passaggi...
Sulle dispense è riportato questo vettore da ordinare con heapsort
$5,13,2,25,7,17,20,8,4$
i passi dell'ordinamento che descrive sono:
$5,13$
$13,5,20$
$13,5,2,25$
$25,13,2,5,7$
$25,13,2,5,7,17$
$25,13,17,5,7,2,20$
$25,13,20,5,7,2,17,8$
$25,13,20,8,7,2,17,5,4$
$25,13,20,8,7,2,17,5,4$
ma non ho minimamente capito come si costruisce l'heap.
Quello che ho capito è che si fanno m operazioni di insert per costruire l'heap, e poi m operazioni di remove per ordinare il vettore, e durante il remove bisogna ripristinare la condizione di heap...ma non ho capito i passaggi...
Risposte
Ciao,
prima di capire come funziona l'algortimo, prova a costrurti l'albero binario quasi-completo corrispondente al vettore heap...
prima di capire come funziona l'algortimo, prova a costrurti l'albero binario quasi-completo corrispondente al vettore heap...
"hamming_burst":
Ciao,
prima di capire come funziona l'algortimo, prova a costrurti l'albero binario quasi-completo corrispondente al vettore heap...
Ciao scusami il ritardo con cui ti rispondo, ma l albero binario del vettore intendi questo?
Ciao,
rimpicciolisci l'immagine è troppo grande...
cmq quello non è un albero heap (albero quasi-completo) quello è un semplice albero binario di ricerca.
Un albero binario quasi-completo che rappresenta un heap è questo:
per qualche definizione vedi: post549206.html#p549206
una volta che hai capito cosa sia, discutiamo il tuo problema.
rimpicciolisci l'immagine è troppo grande...
cmq quello non è un albero heap (albero quasi-completo) quello è un semplice albero binario di ricerca.
Un albero binario quasi-completo che rappresenta un heap è questo:
per qualche definizione vedi: post549206.html#p549206
una volta che hai capito cosa sia, discutiamo il tuo problema.
ciao, mi sono confuso prima, dovrebbe essere questo l'albero giusto?
ok questa volta ci siamo 
Ora prova a ragionare con l'algoritmo heapsort() tramite la struttura ad albero. Le insert e remove sono degli swap foglia-radice, prova a simularlo su carta.
Una descrizione se vuoi è in questo post: post549447.html#p549447 e vedi se ti da un'idea.
PS: ok hai ridimensionato l'immagine, ma hai lasciato quelle enorme
clicca su Modifica ed eliminala (lasciando solo quella ridotta).
Ora prova a ragionare con l'algoritmo heapsort() tramite la struttura ad albero. Le insert e remove sono degli swap foglia-radice, prova a simularlo su carta.
Una descrizione se vuoi è in questo post: post549447.html#p549447 e vedi se ti da un'idea.
PS: ok hai ridimensionato l'immagine, ma hai lasciato quelle enorme
clicca su Modifica ed eliminala (lasciando solo quella ridotta).
non ho mica tanto capito sai...
prima cosa, sai almeno come funziona l'algoritmo heapsort?
non ho molta voglia di descrivere i vari passaggi, perciò un'immagine forse ti aiuta a capire cosa accade, ne disutiamo se non comprendi qualcosa.
"antonio12":
non ho mica tanto capito sai...
non ho molta voglia di descrivere i vari passaggi, perciò un'immagine forse ti aiuta a capire cosa accade, ne disutiamo se non comprendi qualcosa.
Ciao!
Scusate se non ho più riscritto su questo 3d, ma avevo bisogno di un po' di teoria prima di affrontare l'esercizio
.
Grazie hamming per l'aiuto, è stato molto prezioso.
Adesso ho capito come si ordina mediante heap e come si ripristina la condizione di heap. Stasera scannerizzo tutti i passaggi che ho fatto e li posto, almeno può essere di aiuto anche per altri.
Grazie ancora!
Scusate se non ho più riscritto su questo 3d, ma avevo bisogno di un po' di teoria prima di affrontare l'esercizio
.Grazie hamming per l'aiuto, è stato molto prezioso.
Adesso ho capito come si ordina mediante heap e come si ripristina la condizione di heap. Stasera scannerizzo tutti i passaggi che ho fatto e li posto, almeno può essere di aiuto anche per altri.
Grazie ancora!
Adesso però non riesco a capire come ordinare lo stesso vettore con la procedura bottom-up e la procedura top-down...
"antonio12":
Adesso però non riesco a capire come ordinare lo stesso vettore con la procedura bottom-up e la procedura top-down...
cosa intendi con top-down e bottom-up riferito agli heapsort mi giunge nuova sta terminlogia o forse non la ricordo...
Fose ti riferisci al tipo di iterazione o all'ordine in cui viene costrutito o controllato se è ancora un max-min heap?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo