Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: Daréios89 on 01-05-2011, 11:04:28



Title: Dubbio HeapifyR
Post by: Daréios89 on 01-05-2011, 11:04:28
Il codice dice:

Code:
HeapifyR(S,j)
            while j>1 && A[floor(j/2)]<A[j]
                     t=A[floor(j/2)]
                         A[floor(j/2)]=A[j]
                           A[j]=t
               j=floor(j/2)

Non capisco come faccia a funzionare, alcuni elementi non vengono saltati?
Forse costruisco male io la coda, ma dovrei avere una cosa come questa:

9,8,7,6,5,4

Se aumentassi la priorità del penultimo avrei:

9,8,7,6,10,4

Quindi scambio 8 e 10:

9,10,7,6,8,4

A questo punto j diventerebbe quel 10 e ripetendo la procedura avrei:

10,9,7,6,8,4

Ma così non mi rimane il penultimo elemento che non la verifica?


Title: Re:Dubbio HeapifyR
Post by: Zaibach on 06-06-2011, 01:46:19
Il procedimento è tutto corretto e nonostante il penultimo elemento ancora la coda di priorità è integra..

Ricordati che la coda di max-priorità è implementata con un max-heap.. non è mica un normale array ordinato in maniera decrescente!

Prova a disegnare un max-heap con quei valori e vedrai che è tutto apposto, infatti il penultimo elemento e l'ultimo non sono padre uno dell'altro (non sono neanche fratelli!).

Saluti!


Title: Re:Dubbio HeapifyR
Post by: Daréios89 on 28-07-2011, 11:01:46
Hai ragione, sto rivedendo le cose adesso e disegnando la Max-Heap tutto quadra. Ti ringrazio.