Heapify

Heapify这个函数要会手写。
今天不会写，丢人了 :(
heapify要从用percolateDown的方法来写。
时间复杂度是 O(N）的。
为什么时间复杂度是O(N)的，
最后一层的元素不需要往下走，
倒第二层的元素需要走1步 （1/4 N * 1）
倒第三层的元素需要走2步， (1/8 N * 2)
加起来是O(N)
我们从最后一个非叶子结点开始往下percalote Down。

public class Heap {

    public int[] heapify(int[] array) {
    //这是一个maxHeap
        for (int i = (array.length) / 2; i >= 0; i--) {
            percolateDown(array, i, array.length);
        }
        return array;
    }
   private void percolateDown(int[] array, int i, int len) {
     // Max Heap
        int left = i * 2 + 1, right = i * 2 + 2;
        int leftValue = left < len ? array[left] : Integer.MIN_VALUE;
        int rightValue = right < len ? array[right] : Integer.MIN_VALUE;
        if (leftValue >= rightValue) {
            if (array[i] < leftValue) {
                swap(array, i, left);
                percolateDown(array, left, len);
            }
        } else {
            if (array[i] < rightValue) {
                swap(array, i, right);
                percolateDown(array, right,len);
            }
        }
    }
    private void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}