Implementare un 4-heap usando un array
Domanda
Che tipo di matematica usi per attraversare il 4-heap quando usi un array per memorizzare tutti gli elementi? In particolare, come si trova l'indice di un nodo padre su una foglia specifica?
Diciamo che ho il seguente array:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ... ecc.
con l'heap quindi costruito da quello con 1 come radice, 2..5 i suoi figli, 6..9 i figli di 2 ecc.
Qual è esattamente la matematica di cui ho bisogno se devo trovare (ad esempio) il genitore di 6?
Soluzione
Per trovare il genitore di qualsiasi figlio (diverso da 1, che non ha un genitore):
parent = int((child + 2) / 4)
Per trovare il primo e l'ultimo figlio di un genitore:
child_first = parent * 4 - 2
child_last = parent * 4 + 1
Puoi vederlo in funzione poiché, ad ogni livello, aggiungi quattro volte più elementi rispetto al livello precedente:
1 ( 1)
2 thru 5 ( 4)
6 thru 21 ( 16)
22 thru 85 ( 64)
86 thru 341 ( 256)
342 thru 1365 (1024)
Level 1:
1 -> 2 3 4 5
Level 2:
2 -> 6 7 8 9
3 -> 10 11 12 13
4 -> 14 15 16 17
5 -> 18 19 20 21
Level 3:
6 -> 22 23 24 25
7 -> 26 27 28 29
8 -> 30 31 32 33
9 -> 34 35 36 37
10 -> 38 39 40 41
11 -> 42 43 44 45
12 -> 46 47 48 49
13 -> 50 51 52 53
14 -> 54 55 56 57
15 -> 58 59 60 61
16 -> 62 63 64 65
17 -> 66 67 68 69
18 -> 70 71 72 73
19 -> 74 75 76 77
20 -> 78 79 80 81
21 -> 82 83 84 85
& nbsp;
Level 4:
22 -> 86 87 88 89
23 -> 90 91 92 93
24 -> 94 95 96 97
25 -> 98 99 100 101
: : : :
82 -> 326 327 328 329
83 -> 330 331 332 333
84 -> 334 335 336 337
85 -> 338 339 340 341
Esempi sono:
parent of 342 = int(344/4) = 86 (same for 343,344,345).
parent of 346 = int(348/4) = 87 (same for 347,348,349).
first child of 21 = 21 * 4 - 2 = 82
last child of 21 = 21 * 4 + 1 = 85
Altri suggerimenti
Prima una semplice osservazione. Il root è su 1 , quindi tutti i bambini iniziano su 2 . Prima dell'indice i ci sono i-1 vertici (ricorda, l'indice 0 non è un vertice!) Nell'heap, ognuno ha esattamente 4 figli. Quindi i i th saranno a 2 + 4 * (i-1) a 2 + 4 * i-1 ad esempio, i figli di 1 sono 2 + 4 * 0 = 2 a 2 + 4 * 0 + 3 = 5 .
def son_(i):
return range(2+4*(i-1),2+4*i)
for i in range(1,10): print i,son_(i)
uscita ??p>
1 [2, 3, 4, 5]
2 [6, 7, 8, 9]
3 [10, 11, 12, 13]
4 [14, 15, 16, 17]
5 [18, 19, 20, 21]
6 [22, 23, 24, 25]
7 [26, 27, 28, 29]
8 [30, 31, 32, 33]
9 [34, 35, 36, 37]
Nessun buco, vedi.
Se first_son (i) = 2 + 4i e last_son (i) = 2 + 4i + 3 = 4 (i + 1) +1, abbiamo quel padre (n) = floor ((n-2) / 4 ) +1. (il +1 serve a far iniziare l'array a 1)
Proviamo questo:
def father_(n):
return (n-2)/4+1
for i in range(2,20): print i,father_(i)
Output:
2 1
3 1
4 1
5 1
6 2
7 2
8 2
9 2
10 3
11 3
12 3
13 3
14 4
15 4
16 4
17 4
18 5
19 5
È necessaria la divisione e la moltiplicazione dei numeri interi.
Ad esempio, il genitore di 6 è 1 + ((6-1) / 4) = 2
.
Il genitore di 5 è 1 + ((5-1) / 4) = 2
.
Il genitore di 10 è 1 + ((10-1) / 4) = 3
, ecc.
I figli di 2 sono 2 + 4 * (2-1) .. (2 + 4 * (3-1)) - 1 = 6..9
.