ShiftUp:

From top, to see if father < child, or swap O(nlgn)

ShiftDown:

From n/2 leafies, going up, to see if child > itself, or swap, O(n)

Video explains ShiftUp and ShiftDown

https://www.youtube.com/watch?v=d3qd_wQdYqg

class Solution {
public:
    /*
     * @param A: Given an integer array
     * @return: nothing
     */
     //method 1 ShiftUp O(nlogn)
    /*
    void heapify(vector<int> &A) {
        // write your code here
        for (int i = 0; i < A.size(); i++) {
            shiftUp(A, i);
        }
    }
    void shiftUp(vector<int> & A, int index) {
        while (index != 0) {
            int left = index * 2 + 1;
            int right = index * 2 + 2;
            int father = (index - 1) / 2;
            if (A[index] > A[father]) {
                break;
            } 
            int temp = A[index];
            A[index] = A[father];
            A[father] = temp;
            index = father;
        }
    }
    */
    //method 2 shiftDown (O(n))
    void heapify(vector<int> &A) {
        // write your code here
        for (int i = A.size() / 2; i >= 0; i--) {
            shiftDown(A, i);
        }
    }
    void shiftDown(vector<int> & A, int index) {
        while (index < A.size()) {
            int minNum = index;
            int left = index * 2 + 1;
            int right = index * 2 + 2;

            if (left < A.size() && A[left] < A[minNum]) {
                minNum = left;
            }
            if (right < A.size() && A[right] < A[minNum]) {
                minNum = right;
            }
            if (minNum == index) {
                break;
            }
            int temp = A[index];
            A[index] = A[minNum];
            A[minNum] = temp;
            index = minNum;
        }

    }

};