给出一个整数数组，堆化操作就是把它变成一个最小堆数组。对于堆数组 A，A[0] 是堆的根，并对于每个 A[i]，A [i * 2 + 1] 是 A[i] 的左儿子并且 A[i * 2 + 2] 是 A[i] 的右儿子。
说明
什么是堆？
堆是一种数据结构，它通常有三种方法：push， pop 和 top。其中，“push”添加新的元素进入堆，“pop”删除堆中最小/最大元素，“top”返回堆中最小/最大元素。
什么是堆化？
把一个无序整数数组变成一个堆数组。如果是最小堆，每个元素A[i]，我们将得到 A[i * 2 + 1] >= A[i] 和 A[i * 2 + 2] >= A[i]，如果有很多种堆化的结果？返回其中任何一个。
样例
给出 [3,2,1,4,5]，返回 [1,2,3,4,5] 或者任何一个合法的堆数组
挑战
O(n) 的时间复杂度完成堆化
知识点
所谓堆化就是构造一个堆，堆化是堆排序的前提，堆排序就是建立一个初始堆，然后通过取出堆顶元素，再将剩下来的重新调整，最终可以得到一个有序的排序，不能对链表进行堆排序，因为链表不能像数组一样快速通过下标读取元素，堆中对结点的左儿子和右儿子之间谁大谁小没要求，只要左右儿子都同时大于或小于结点本身值就行
代码
方法区别
- 方法 1 和 2 都是从一颗二叉树的倒数第二层开始往上遍历，每次往下调顺序，倒数第二层最多要调 n/2 个点(最后一层只有最左边一个点)，每次最多 O(1) 的操作，倒数第三层最多要调 n/4 个点，每次最多 O(2) 的操作......最顶层只有1个点，最多 O(logn) 次操作。时间复杂度为 n/2 * O(1) + n/4 * O(2) + ...... + O(log(n)) = O(n)
- 方法3的操作从上往下遍历每个结点，每次往上调，第一层1个结点 log1 的操作，第二层2个结点最多 log2 操作......最后一层 n/2 个结点最多 logn 的操作时间复杂度为 log 1 + 2 * log 2 + 3 * log 3......+ n/2 * log n
- 从倒数第二行最后一个元素开始往根结点扫描，对当前结点的子结点进行下面操作，跳过大于等于当前结点的儿子结点，如果子结点中较小的结点小于当前结点，交换当前结点和子结点中的较小结点，时间复杂度 O(n)
public class Solution {
/**
* @param A: Given an integer array
* @return: void
*/
private void siftdown(int[] A, int k) {
while (k * 2 + 1 < A.length) {
int son = k * 2 + 1;
// 最小堆堆化，若左儿子大于右儿子，则根结点执行下沉操作同子结点交换值也轮不到左儿子，所以将结点切换到右儿子就可以了
if (k * 2 + 2 < A.length && A[son] > A[k * 2 + 2]) {
son = k * 2 + 2;
}
if (A[son] >= A[k]) {
break;
}
int temp = A[son];
A[son] = A[k];
A[k] = temp;
// 结点仍是原先的结点，堆的形态未变，但交换的 k 值变化成新的，对应结点下移
// son 结点在 key 结点的下方
k = son;
}
}
public void heapify(int[] A) {
for (int i = A.length / 2 - 1 ; i >= 0; i--) {
siftdown(A, i);
}
}
}
- 和上种区别就在于多了个 A[smallest] 记录根结点，写法上的区别，时间复杂度 O(n)
public class Solution {
/**
* @param A: Given an integer array
* @return: void
*/
private void siftdown(int[] A, int k) {
while (k < A.length) {
int smallest = k;
if (k * 2 + 1 < A.length && A[k * 2 + 1] < A[smallest]) {
smallest = k * 2 + 1;
}
if (k * 2 + 2 < A.length && A[k * 2 + 2] < A[smallest]) {
smallest = k * 2 + 2;
}
if (smallest == k) {
break;
}
int temp = A[smallest];
A[smallest] = A[k];
A[k] = temp;
k = smallest;
}
}
public void heapify(int[] A) {
for (int i = A.length / 2; i >= 0; i--) {
siftdown(A, i);
} // for
}
}
- 從尾到頭掃一遍，如果遇到本身的值比 parent element 的值小的就一直跟 parent element 的值交換，直到交換到最頂層或是本身的值大於 parent element 的值
// O(nlogn)
public class Solution {
/**
* @param A: Given an integer array
* @return: void
*/
private void siftup(int[] A, int k) {
while (k != 0) {
int father = (k - 1) / 2;
if (A[k] > A[father]) {
break;
}
int temp = A[k];
A[k] = A[father];
A[father] = temp;
k = father;
}
}
public void heapify(int[] A) {
for (int i = 0; i < A.length; i++) {
siftup(A, i);
}
}
}
