Lezione del 12/5/2010

Esercizi: riparazione dello Heap dopo la modifica del peso di un suo nodo (codice della funzione al termine del post); confronto tra stringhe.

Codice della funzione heapModify proposto dallo studente Fabio Durastante.

/*La funzione prende in input l'Heap H, 
il numero del nodo da modificare 
e il suo nuovo peso. */
Heap heapModify(Heap H, int u, int e){
 if(u>H.n||u==0) return H;
 /* si porta il nodo verso la radice */
 if(H.v[u]>e){ 
  H.v[u]=e; 
  while( u>1 && H.v[u]<H.v[u/2]){ 
   swap(&(H.v[u]),&(H.v[u/2]));
   u=u/2;
  }
  return H;
 }
 if(H.v[u]<e){
  /* ... altrimenti si porta il nodo
  verso le fogli */
  H.v[u]=e; 
  while(2*u+1<=H.n &&(H.v[u]>H.v[2*u]||H.v[u]>H.v[2*u+1])){ 
   if(H.v[2*u]<H.v[2*u+1]){
    swap(&(H.v[u]),&(H.v[2*u]));
    u=2*u;
   } else{
    swap(&(H.v[u]),&(H.v[2*u+1]));
    u=2*u+1;
   }
  }
  if(2*u<H.n && H.v[u]>H.v[2*u])
   swap(&(H.v[u]),&(H.v[2*u]));
  return H;
 }
 /* ... non occorre nessuna modifica. */
 H.v[u]=e;
 return H;
}