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

http://www.lintcode.com/en/problem/heapify/

Discussion

这里的数组是树的一种存储方式，给定i，它的左右子树分别是2i+1和2i+2，parent是(i-1)/2, 从n/2开始到n-1都是叶子节点。画个图就明白了，数据结构里也讲过的。

最小堆就是给定任意node，都比它的左右孩子（如果存在的话）小，最大堆则相反。heapify的过程就是建立这样的关系的过程。

思路1：自底向上。从有左右子树的最底层的node开始，也就是n/2-1开始，如果node的两个子节点都比node节点小，那么就swap最小的那个, 只有一个小就swap小的那个。swap之后，我们要重新heapify 被换的节点（曾经的母节点，现在的子节点）。时间复杂度O(n).

Solution 1

class Solution {
public:
    /**
     * @param A: Given an integer array
     * @return: void
     */
    void heapify(vector<int> &A) {
        // write your code here
        for(int i=A.size()/2-1; i>=0; i--) {
       // for(int i=0; i<A.size(); i++) {
            heapify(A, i);
        }
    }
    void heapify(vector<int> &A, int index) {
        int left = 2*index+1 < A.size() ? A[2*index+1] : INT_MAX;
        int right = 2*index+2 < A.size() ? A[2*index+2] : INT_MAX;
        if(left < right && left < A[index] ) {
            A[2*index+1] = A[index];
            A[index] = left;
            heapify(A, 2*index+1);
        } else if(right < A[index]) {
            A[2*index+2] = A[index];
            A[index] = right;
            heapify(A, 2*index+2);
        }
    }
};

思路2： 自定向下。给定节点node i，比较它的父节点(i-1)/2，根据堆的定义决定要不要交换，如果要交换，还要接着heapify新的父节点。

class Solution {
public:
    /**
     * @param A: Given an integer array
     * @return: void
     */
    void heapify(vector<int> &A) {
        // write your code here
        //for(int i=A.size()/2-1; i>=0; i--) {
       for(int i=0; i<A.size(); i++) {
            heapify(A, i);
        }
    }
    void heapify(vector<int> &A, int index) {
        while (true) {
            int parent = (index-1)/2;
            if(parent < 0) break;
            if(A[parent] > A[index]) {
                swap(A[parent], A[index]);
                index = parent;
            } else {
                break;
            }
        }
    }
};

逐次插入新元素到heap里：

class Solution {
public:
    /**
     * @param A: Given an integer array
     * @return: void
     */
    void heapify(vector<int> &A) {
        vector<int> heap;
        for(auto const& val : A) {
            Insert(heap, val);
        }
        A = heap;
    }

    void Insert(vector<int> &heap, int val) {
        heap.emplace_back(val);
        int i = heap.size()-1; //the postion of the new value
        //bottom-up heapify it
        while(i>0 && heap[i] < heap[(i-1)/2]) {
           swap(heap[i], heap[(i-1)/2]);
           i = (i-1)/2;
        }
    }
};