Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: Giovi89 on 09-11-2009, 18:47:21



Title: dubbio codice Max-Heapify??
Post by: Giovi89 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. .ciaociao



Title: Re:dubbio codice Max-Heapify??
Post by: shiny 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.