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

Have you met this question in a real interview? 

Yes

Example

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

Challenge

O(n) time complexity

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.

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--){

            _heapify(A, i);

        }

    }

    

    private void _heapify(int[] A, int i){

        

        int left = i * 2 + 1 < A.length ? A[i*2+1] : Integer.MAX_VALUE;

        int right = i * 2 + 2 < A.length ? A[i*2+2] : Integer.MAX_VALUE;

        if(left <= right && left < A[i]){

            A[i*2+1] = A[i];

            A[i] = left;

            _heapify(A, i*2+1);

        } else if(right <= left && right < A[i]){

            A[i*2+2] = A[i];

            A[i] = right;

            _heapify(A, i*2+2);

        }

    }

}