Given an integer array, heapify it into a min-heap array.

For a heap array A, A[0] is the root of heap, and for each A[i], A[i 2 + 1] is the left child of A[i] and A[i 2 + 2] is the right child of A[i].


复习堆的时候把这个题目当练习做了,这实际上是构造一个最小堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void heapify(int[] A) {
for (int i = A.length / 2 - 1; i >= 0; i--) {
heapify(A, i);
}
}
public void heapify(int[] A, int i) {
int l = 2 * i + 1;
int r = 2 * i + 2;
int min = i;
if (l < A.length && A[l] < A[i])
min = l;
if (r < A.length && A[r] < A[min])
min = r;
if (min != i) {
int temp = A[min];
A[min] = A[i];
A[i] = temp;
heapify(A, min);
}
}