Pages: [1]   Go Down
Print
Author Topic: Dubbio HeapifyR  (Read 733 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« 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?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Zaibach
Matricola
*
Offline Offline

Posts: 72


« Reply #1 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!
« Last Edit: 06-06-2011, 01:50:30 by Zaibach » Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #2 on: 28-07-2011, 11:01:46 »

Hai ragione, sto rivedendo le cose adesso e disegnando la Max-Heap tutto quadra. Ti ringrazio.
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Pages: [1]   Go Up
Print
Jump to: