Heapify

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

Thoughts

从下往上建堆，时间复杂度为O(n).证明参考https://www.zhihu.com/question/20729324

Code

public class Solution {
    /**
     * @param A: Given an integer array
     * @return: void
     */
    public void heapify(int[] A) {
        for (int i = A.length / 2; i >= 0; i--) {
            siftdown(A, i);
        }
    }

    private void siftdown(int[] nums, int index) {
        while (index < nums.length) {
            int smallest = index;
            if (index * 2 + 1 < nums.length && nums[index * 2 + 1] < nums[index]) {
                smallest = index * 2 + 1;
            }
            if (index * 2 + 2 < nums.length && nums[index * 2 + 2] < nums[smallest]) {
                smallest = index * 2 + 2;
            }

            if (smallest == index) {
                break;
            }

            int tmp = nums[index];
            nums[index] = nums[smallest];
            nums[smallest] = tmp;

            index = smallest; 
        }        
    }
}

Analysis

TC: O(n)