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

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.

Solution:

基本的堆排序思路，

首先就是把数组想象成一个二叉堆，但是需要调整后满足小顶堆， 首先遍历最后一个根结点，跟左右节点去比较，如果不是最小则进行交换，有可能交换后的子节点有子子节点，而且有可能不满足条件，所以要进行继续交换，通过While.

Heapify 定义是给定一个数组，把这个数组变成有序的小顶堆。满足这个条件： A[i].left = A[i2 +1] A[i] .right = A[i2 + 2]

http://www.jianshu.com/p/e44f2ca9938a

https://aaronice.gitbooks.io/lintcode/content/data_structure/heapify.html

首先，先搞懂几个概念：heap，min-heap，complete tree。这里只要知道heap是一种complete tree的树结构，结点i的左右子结点的index为2i+1和2i+2，min-heap是子结点大于根节点的树，就大概明白题目要怎么heapify了。

思路是从底部开始构建数组，将较小的结点移向上层结点。先取数组末尾的两个元素为left和right，若2i+1和2i+2越界，则赋Integer.MAX_VALUE，这样可以在后面的分支语句避免对越界情况不必要的讨论。然后，取left和right的较小者和上层A[i]结点交换，实现min-heap结构。交换了A[i]和A[2i+1]/A[2i+2]之后，还要重新heapify被交换到末位的原先的A[i]，即交换之后的A[2i+1]/A[2i+2]。然后i不断减小，直到整个数组完成heapify。

其实，这就相当于对数组A进行堆排序。

class Solution:
    # @param A: Given an integer array
    # @return: void
    def heapify(self, A):
        for i in range(len(A) / 2 - 1, -1, -1):
            self.shiftdown(A, i)
        # write your code here
    def shiftdown(self, A, k):
        while k < len(A):
            smallest = k
            if 2 * k + 1 < len(A) and A[2 * k + 1] < A[smallest]:
                smallest = 2 * k + 1
            if 2 * k + 2 < len(A) and A[2 * k + 2] < A[smallest]:
                smallest = 2 * k + 2
            if smallest == k:
                break
            A[k], A[smallest] = A[smallest], A[k]
            k = smallest