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

Thinking:

There is a relationship of index between parent and their children. We should use relationship to solve this problem.

Steps:

1. check whether input is valid
2. If we choose sift down, use the relationship of A[i] > A[i/2]then we need begin at the end of the Array, to make sure that it is a heap structure.
3. If we choose sift up, then we need begin at the beginning of the Array. Use the relationship of A[i] < A[i*2] and A[i] < A[i*2+1]

Codes:

Siftup:

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

Siftdown:

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/2;i>=0; i--){
             siftdown(A, i);
        }
    }
    private void siftdown(int[] A, int index){
        int k = index;
        int smallest = k;
        while(k < A.length){
            if(k * 2 + 1 < A.length && A[k * 2 + 1] < A[smallest]){
                smallest = k * 2 + 1;
            }
            if(k * 2 + 2 < A.length && A[k * 2 + 2] < A[smallest]){
                smallest = k * 2 + 2;
            }
            if(smallest == k){
                break;
            }
            else{
                swap(A, k, smallest);
                k = smallest;
            }
        }

    }
    private void swap(int[] A, int i, int j){
        A[i] = A[i]^A[j];
        A[j] = A[j]^A[i];
        A[i] = A[i]^A[j];
    }
}

Conclusion:

In the siftdown function, using a variable smallest that tracks the smallest among the parent and two children is a really smart method.