PDA

Visualizza la versione completa : [C++] Dubbi su implementazione di un heap


hopeway
13-01-2018, 16:08
Salve, sto implementando come esercizio un heap. Nell'istruzione left, right e parent il prof scrive:

intleft(int i) { return i<<1; }
int right(int i) { return (i<<1)|1; }
int parent(int i) { return i>>1; }
Qualcuno potrebbe spiegarmi le varie istruzioni?

scimmiaparlante
14-01-2018, 11:33
In left(...) fa lo shift a sinistra di un bit dell'intero in ingresso, che equivale a moltiplicare per 2 il valore in ingresso
(es: 42<<1: 101010 -> 1010100 = 84 in base 10)
In right(...) fa lo shift a sinistra di un bit dell'intero in ingresso e pone la cifra meno significativa a 1, che equivale a moltiplicare per 2 il valore in ingresso e ad aggiungere 1
(es: (42<<1)|1: (101010<<1)|0000001 = 1010100|0000001 = 1010101 = 85 in base 10)
In parent(...) fa lo shift a destra di un bit dell'intero in ingresso, che equivale a dividere per 2 il valore in ingresso, scartando il resto
(es: 42>>1: 101010 -> 10101 = 21 in base 10)

In uno heap implementato con un array, se si parte a contare da 1, il modo per recuperare l'indice dei figli (sx e dx) e del padre di un nodo

hopeway
14-01-2018, 14:52
Perfetto, grazie mille! :)

Loading