BuildHeap
The general algorithm is to place the N
keys in an array and consider it to be an
unordered binary tree.
The following algorithm will build a heap
out of N keys.
for( i = N/2; i > 0; i-- )
percolateDown(i);
BuildHeap
i = 15/2 = 7 65
19
21
1424
26
13 15
68
16
65 21 1926 14 1668 13 24 15
1 2 3 5 6 7 8 9 10 11 12 13 140
1
2 3
7654
89 10
31
31
11
32
32
12
154
5
13 70
14 12
15
5 70 12
i
i
Why I=n/2?
BuildHeap
i = 15/2 = 7 65
19
21
1424
26
13 15
12
16
65 21 1926 14 1612 13 24 15
1 2 3 5 6 7 8 9 10 11 12 13 140
1
2 3
7654
89 10
31
31
11
32
32
12
154
5
13 70
14 68
15
5 70 68
i
i
BuildHeap
i = 6 65
19
21
1424
26
13 15
12
16
65 21 1926 14 1612 13 24 15
1 2 3 5 6 7 8 9 10 11 12 13 140
1
2 3
7654
89 10
31
31
11
32
32
12
154
5
13 70
14 68
15
5 70 68
i
i
BuildHeap
i = 5 65
5
21
1424
26
13 15
12
16
65 21 526 14 1612 13 24 15
1 2 3 5 6 7 8 9 10 11 12 13 140
1
2 3
7654
89 10
31
31
11
32
32
12
154
19
13 70
14 68
15
19 70 68
i
i
