Implementieren eines 4-Heap mit einem Array

Question

Welche Art von Mathematik verwenden Sie, um den 4-Heap zu durchlaufen, wenn Sie ein Array verwenden, um alle Elemente zu speichern? Wie finden Sie den Index eines übergeordneten Knotens zu einem bestimmten Blatt speziell?

Angenommen, I die folgende Anordnung haben:

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

mit dem Heap dann konstruiert daraus mit 1 die Wurzel, 2..5 seine Kinder, 6..9 2 Kinder usw.

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

Answer 1

Um die Eltern eines Kindes (ausgenommen 1 zu finden, das keine Eltern):

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 diese in Betrieb sehen auf jeder Ebene, da Sie viermal so viele Elemente hinzufügen, wie Sie in der vorherigen Ebene tat

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

Sie benötigen ganzzahlige Division und Multiplikation. Zum Beispiel ist der Elternteil von 6 1+((6-1)/4) = 2. Die Eltern von 5 ist 1+((5-1)/4) = 2. Die Eltern von 10 ist 1+((10-1)/4) = 3, etc. 2 Kinder sind 2+4*(2-1)..(2+4*(3-1))-1 = 6..9.

Answer 3

Zuerst eine einfache Beobachtung. Root ist um , so beginnen alle Kinder bei . Vor dem Index i gibt es i-1 Vertices (denken Sie daran, Index 0 ist kein Eckpunkt!) Im Heap, jeder hat 4 Kinder genau. So i^th Kinder werden bei 2 + 4 * (i-1)-2 + 4 * i-1 zum Beispiel ‚s Kinder sind 2 + 4 * 0 = 2 bis 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 das Array zu machen bei 1 starten)

Lassen Sie uns Test, dass:

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

Ausgang:

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