배열을 사용하여 4- 힙 구현하기

Question

배열을 사용하여 모든 요소를 ​​저장할 때 4-heap을 트래버스하는 수학은 어떤 종류입니까? 특히, 특정 리프에 대한 부모 노드의 인덱스를 어떻게 찾을 수 있습니까?

의 나는 다음과 같은 배열이 있다고 가정 해 봅시다 :

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

힙과를 그 다음에 1을 루트로, 2..5 그 자식을, 6.9 2의 자식 등으로 구성합니다.

6의 부모를 찾아야 할 때 정확히 필요한 수학은 무엇입니까?

Answer 1

1 이외의 다른 아이의 부모를 (찾으려면, 하는) 부모가없는 :

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

부모의 처음과 마지막 아이를 찾으려면 :

,536,913,632

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 

예는 다음과 같습니다 이후 10

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

당신은 당신이 이전 레벨에서했던대로 4 배 많은 요소를 추가, 각 레벨에서 동작에서 볼 수 있습니다 :

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

정수 나누기 및 곱셈이 필요합니다. 예를 들어, 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입니다.

Answer 3

처음 간단한 관찰. 루트는 이므로 모든 어린이는 에서 시작합니다. 인덱스 전에 i 힙에는 i-1 버텍스가 있습니다 (인덱스 0은 꼭지점이 아닙니다!), 각각 4 개의 아이를 정확하게 가지고 있습니다. 그래서 난^번째 어린이에있을 것이다 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