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);
    }
}