heapify

核心 siftup, siftdown

code

class Solution {
public:
    /**
     * @param A: Given an integer array
     * @return: void
     */
    void heapify(vector<int> &A) {
        // write your code here
        if(A.size() == 0)
        {
            return ;
        }

        vector<int> ret(A.size(), 0);
        int pos = 0;
        for(int tmp : A)
        {
            push(ret, pos, tmp);
        }

        A = ret;
    }

    void push(vector<int>& vec, int& pos, int value)
    {
        vec[pos] = value;

        int i = pos;
        int rootindex = (i-1)/2;
        while(i > 0 && vec[rootindex] > vec[i])
        {
            int tmp = vec[rootindex];
            vec[rootindex] = vec[i];
            vec[i] = tmp;

            i = rootindex;
            rootindex = (i-1)/2;
        }
        pos++;
    }
};