A implementação de um 4-pilha usando uma matriz
Pergunta
Que tipo de matemática que você usa para atravessar o 4-heap quando se usa uma matriz para armazenar todos os elementos? Especificamente, como você encontrar o índice de um nó pai para uma folha específica?
Vamos dizer que eu tenho a seguinte matriz:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |. Etc ...
com a pilha em seguida, construído a partir de que, com 1 sendo a raiz, 2..5 suas crianças, 6..9 2 de crianças etc.
O que exatamente é a matemática que eu preciso se eu precisar de encontrar (por exemplo) o pai de 6?
Solução
Para encontrar o pai de qualquer criança (diferente de 1, o que não tem pai):
parent = int((child + 2) / 4)
Para encontrar o primeiro e último filho de um pai:
child_first = parent * 4 - 2
child_last = parent * 4 + 1
Você pode ver isso em operação uma vez que, em cada nível, você adicionar quatro vezes o número de elementos, como você fez no nível anterior:
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
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
Os exemplos são:
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
Outras dicas
Primeiro, uma simples observação. Root é a 1 , então todas as crianças começam em 2 . Antes índice i , existem i-1 vértices (lembre-se, o índice 0 não é um vértice!) Na pilha, cada um tem 4 filhos exatamente. Então, i th crianças estarão em 2 + 4 * (i-1) e 2 + 4 * i-1 por exemplo, 1 's crianças são 2 + 4 * 0 = 2 e 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)
saída
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]
Não há buracos, ver.
Se first_son (i) = 2 + 4i e last_son (i) = 2 + 4i + 3 = 4 (i + 1) 1, temos que o pai (n) = andar ((N-2) / 4 ) 1. (A 1 é fazer com que a matriz para iniciar em 1)
Vamos teste que:
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
Você precisa divisão inteira e multiplicação.
Por exemplo, o pai de 6 é 1+((6-1)/4) = 2
.
O pai de 5 é 1+((5-1)/4) = 2
.
A mãe de 10 é 1+((10-1)/4) = 3
, etc.
2 de crianças são 2+4*(2-1)..(2+4*(3-1))-1 = 6..9
.