Given an integer array, heapify it into a min-heap array. If there are multiple solutions, return any one.

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

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

Example

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

The following algorithm uses sorting, which has the time complexity of O(nlogn).

public class Solution {
    public void heapify(int[] a) {
        if (a == null || a.length <= 1)
            return;
        
        Integer[] temp = new Integer[a.length];
        
        for (int i = 0; i < a.length; i++)
            temp[i] = a[i];
            
        Arrays.sort(temp, new Comp());
        
        for (int i = 0; i < a.length; i++)
            a[i] = temp[i];
    }
    
    class Comp implements Comparator<Integer> {
        public int compare(Integer a, Integer b) {
            return a.compareTo(b);
        }
    }
}