Реализация 4-кучи с использованием массива

Question

Какую математику вы используете для обхода 4-кучи при использовании массива для хранения всех элементов? В частности, как вы находите индекс родительского узла для определенного листа?

Допустим, у меня есть следующий массив:

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ... и т. Д.

с кучей, построенной из той, где 1 является корнем, 2..5 его потомками, 6..9 2 потомками и т. Д.

Какая именно математика мне нужна, если мне нужно найти (например) родителя 6?

Answer 1

Сначала простое наблюдение. Корень находится на 1 , поэтому все дети начинаются с 2 . До индекса i в куче есть i-1 вершин (помните, что индекс 0 не является вершиной!), У каждого из них 4 ребенка. Так, например, i ^th детей будет в 2 + 4 * (i-1) до 2 + 4 * i-1, 1 дети 2 + 4 * 0 = 2 до 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)

выход

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]

дырок нет, см.

Если first_son (i) = 2 + 4i и last_son (i) = 2 + 4i + 3 = 4 (i + 1) +1, то у нас этот отец (n) = этаж ((n-2) / 4 ) +1. (+1 означает, что массив должен начинаться с 1)

Давайте проверим это:

def father_(n):
    return (n-2)/4+1
for i in range(2,20): print i,father_(i)

Выход:

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

Answer 2

Чтобы найти родителя любого ребенка (кроме 1, у которого нет родителя):

parent = int((child + 2) / 4)

Чтобы найти первого и последнего потомка родителя:

child_first = parent * 4 - 2
child_last  = parent * 4 + 1

Вы можете увидеть это в действии, поскольку на каждом уровне вы добавляете в четыре раза больше элементов, чем на предыдущем уровне:

  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

Примеры:

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

Answer 3

Вам нужно целочисленное деление и умножение. Например, родительский элемент 6 - 1+((6-1)/4) = 2. Родитель 5 1+((5-1)/4) = 2. Родитель 10 1+((10-1)/4) = 3 и т. Д. 2 детей 2+4*(2-1)..(2+4*(3-1))-1 = 6..9.