[LintCode] Heapify

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].

Example

Given [3,2,1,4,5], return [1,2,3,4,5] or any legal heap array.

class Solution {
public:
    void heapify(vector<int> &num) 
    {
        int len = num.size();
        int start = (len-2)/2;
        while(start >= 0)
        {
            int root = start;
            while(2*root+1 < len)
            {
                int swap = root;
                int left = 2*root + 1;
                int right = left + 1;
                
                if(num[swap]>num[left]) swap = left;
                if(right<len&&num[right]<num[swap]) swap = right;
                
                if(swap == root) break;
                int tmp = num[swap];
                num[swap] = num[root];
                num[root] = tmp;
                root = swap;
            }
            start --;
        }
    }
};