Pages: [1]   Go Down
Print
Author Topic: dubbio codice Max-Heapify??  (Read 1857 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Giovi89
Apprendista Forumista
**
Offline Offline

Posts: 273


« on: 09-11-2009, 18:47:21 »

Salve ragazzi,
nel codice seguente nn riesco a capire come mai nel controllo del'if mette l ≤ heap-size[A], che cosa rappresenta questa variabile heap-size[A]?

Code:
MAX-HEAPIFY(A, i)
1 l ← LEFT(i)
2 r ← RIGHT(i)
3 if l ≤ heap-size[A] and A[l] > A[i]
4 then massimo ← l
5 else massimo ← i
6 if r ≤ heap-size[A] and A[r] > A[massimo]
7 then massimo ← r
8 if massimo != i
9 then scambia A[i] ↔ A[massimo]
10 MAX-HEAPIFY(A, massimo)

ed inoltre come ricaviamo la seguente equazione di ricorrenza?

T(n) ≤ T(2n/3) + Θ(1)

Grazie per vostre eventuali risposte.

Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #1 on: 12-11-2009, 01:13:08 »

che cosa rappresenta questa variabile heap-size[A]?
heap-size[A] rappresenta la dimensione dell'heap che e' diversa dalla  length[A] (A=array su cui e' costruito l'heap)
ed inoltre come ricaviamo la seguente equazione di ricorrenza?

T(n) ≤ T(2n/3) + Θ(1)
per ricavare questa equazione di ricorrenza basta mettersi nel caso peggiore (cioe' un heap con l'ultimo lvl pieno a meta'), e osservare che i nodi presenti nel sotto-albero di sx sono 2/3 del num di nodi totali, mentre nel sotto albero di dx sono presenti 1/3 dei nodi totali. Quindi nel caso peggiore heapyfy scendera' per il sotto-albero sx che contiene 2/3n nodi ed ad ogni passo impieghera' tempo costante per effettuare le sue operazioni.
Logged
Pages: [1]   Go Up
Print
Jump to: