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

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.

Challenge

O(n) time complexity

思路：

（1）自下而上：

算法思路：

对于每个元素A[i]，比较A[i]和它的父亲结点的大小，如果小于父亲结点，则与父亲结点交换。

交换后再和新的父亲比较，重复上述操作，直至该点的值大于父亲。

时间复杂度分析

对于每个元素都要遍历一遍，这部分是 O(n)O(n)。

每处理一个元素时，最多需要向根部方向交换 lognlogn 次。

因此总的时间复杂度是 O(nlogn)O(nlogn)

（2）自上而下：

算法思路：

初始选择最接近叶子的一个父结点，与其两个儿子中较小的一个比较，若大于儿子，则与儿子交换。

交换后再与新的儿子比较并交换，直至没有儿子。

再选择较浅深度的父亲结点，重复上述步骤。

时间复杂度分析

这个版本的算法，乍一看也是 O(nlogn)O(nlogn)， 但是我们仔细分析一下，算法从第 n/2 个数开始，倒过来进行 siftdown。也就是说，相当于从 heap 的倒数第二层开始进行 siftdown 操作，倒数第二层的节点大约有 n/4 个， 这 n/4 个数，最多 siftdown 1次就到底了，所以这一层的时间复杂度耗费是 O(n/4)O(n/4)，然后倒数第三层差不多 n/8 个点，最多 siftdown 2次就到底了。所以这里的耗费是 O(n/8 * 2), 倒数第4层是 O(n/16 * 3)，倒数第5层是 O(n/32 * 4) ... 因此累加所有的时间复杂度耗费为：

T(n) = O(n/4) + O(n/8 * 2) + O(n/16 * 3) ...

然后我们用 2T - T 得到：

2 * T(n) = O(n/2) + O(n/4 * 2) + O(n/8 * 3) + O(n/16 * 4) ...

T(n)    =          O(n/4)    + O(n/8 * 2) + O(n/16 * 3) ...

2 * T(n) - T(n) = O(n/2) +O (n/4) + O(n/8) + ...

                = O(n/2 + n/4 + n/8 + ... )

                = O(n)

因此得到 T(n) = 2 * T(n) - T(n) = O(n)

代码：