Heapify

为什么heapify的顺序是从下往上？

guarantee that the smallest element can be switched up to the root

public class Solution {

    /**

     * @param A: Given an integer array

     * @return: void

     */

    public void heapify(int[] A) {

        // write your code here

        if (A == null || A.length == 0) return;

        //size - 1 == lastIndex  ->  (size - 1 - 1) / 2 == lastIndex's parent

        for (int i = (A.length - 2) / 2; i >= 0; i--) {

            percolateDown(A, i);

        }

        

    }

    private static void percolateDown(int[] A, int currIndex) {

        int leftChild, rightChild;

        int minIndex;

        //still has children

        while (currIndex * 2 + 1 < A.length) {

            minIndex =  currIndex;

            leftChild = currIndex * 2 + 1;

            rightChild = currIndex * 2 + 2;

            if (leftChild < A.length && A[leftChild] < A[minIndex]) {

                minIndex = leftChild;

            }

            if (rightChild < A.length && A[rightChild] < A[minIndex]) {

                minIndex = rightChild;

            }

            if (minIndex == currIndex) break;

            swap(A, currIndex, minIndex);

            currIndex = minIndex;

        }

    }

    

    private static void swap(int[] A, int index1, int index2) {

        int temp = A[index1];

        A[index1] = A[index2];

        A[index2] = temp;

    }

}