Die Implementierung eines 4-Heap eine Anordnung unter Verwendung von

Question

Welche Art von Mathematik verwenden Sie das 4-Haufen zu durchqueren, wenn ein Array mit allen Elementen speichern? Genauer gesagt, wie finden Sie den Index eines übergeordneten Knoten zu einem bestimmten Blatt?

Nehmen wir an, ich habe folgendes Array:

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |. Etc ...

mit dem Heap dann aus, dass gebaut mit 1 die Wurzel ist, 2..5 seine Kinder, 6..9 2 Kinder etc.

Was genau ist die Mathematik ich brauche, wenn ich finden müssen (zum Beispiel) die Eltern von 6?

Answer 1

Um die Eltern eines Kindes (außer 1, die kein Elternteil hat) zu finden:

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

Um das erste und das letzte Kind eines Elternteils zu finden:

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

Sie können in Betrieb sehen dies, da auf jeder Ebene, Sie viermal so viele Elemente hinzufügen, wie Sie in der vorherige Ebene haben:

  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

Beispiele sind:

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 2

Zuerst wird eine einfache Beobachtung. Root ist in 1 , so dass alle Kinder beginnen in 2 . Vor dem Index i es i-1 Ecken (denken Sie daran, Index 0 ist kein Vertex!) In dem Haufen, jeder hat vier Kinder genau. So i ^th Kinder werden in seine 2 + 4 * (i-1) 2 + 4 * i-1 zum Beispiel 1 's Kinder sind 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)

Ausgang

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]

Keine Löcher finden.

Wenn first_son (i) = 2 + 4i und last_son (i) = 2 + 4i + 3 = 4 (i + 1) +1, haben wir, dass Vater (n) = floor ((n-2) / 4 ) +1. (Die +1 ist, um das Array zu bilden, auf 1 zu starten)

Lassen Sie uns prüfen, dass:

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

Ausgabe:

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 3

Sie müssen Integer-Division und Multiplikation. Zum Beispiel ist die Mutter von 6 1+((6-1)/4) = 2. Die Mutter von 5 ist 1+((5-1)/4) = 2. Die Mutter von 10 1+((10-1)/4) = 3 usw. 2 Kinder sind 2+4*(2-1)..(2+4*(3-1))-1 = 6..9.