[LintCode] 130 Heapify 解题报告

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

Clarification
What is heap?

Heap is a data structure, which usually have three methods: push, pop and top. where "push" add a new element the heap, "pop" delete the minimum/maximum element in the heap, "top" return the minimum/maximum element.

What is heapify?
Convert an unordered integer array into a heap array. If it is min-heap, for each element A[i], we will get A[i * 2 + 1] >= A[i] and A[i * 2 + 2] >= A[i].

What if there is a lot of solutions?
Return any of them.


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


Challenge
O(n) time complexity


思路
只要往一个方向就可以了。
注意要想清楚从(A.length - 1) / 2这个index开始往前一直到0。
如果反过来就不对了。反过来最直接的错误就是i = 0开始往下sink。然后从i=1开始。这时候i = 0的地方并不一定是最小的。而且i = 0再也不会被比到了。


Code

public class Solution {
    /**
     * @param A: Given an integer array
     * @return: void
     */
    public void heapify(int[] A) {
        // write your code here
        
        for (int i = (A.length - 1) / 2; i >= 0; i--) {
            sink(A, i);
        }
    }
    
    private void sink(int[] A, int k) {
        while (2 * k + 1 < A.length) {
            int j = 2 * k + 1;
            if (j + 1 < A.length && A[j + 1] < A[j]) {
                j++;
            }
            if (A[k] > A[j]) {
                exch(A, k, j);
            }
            k = j;
        }
    }
    
    private void exch(int[] A, int i, int j) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}