目录
一、向上调整来建堆
二、向下调整来建堆
三、向上建堆和向下建堆的优劣比较
比如我们对于这样一个数组来建立一个小根堆
一、向上调整来建堆
思想：
首先，我们把第一个数字看成堆，也就是4，当第二个数字插入进去的时候，进行向上调整算法，使其确保为小堆，向上调整的算法在上篇博文已详细讲解过，不过多赘述。一个一个的插入数据的过程就是遍历数组，确保数组里每一个数进行向上调整算法
其过程的图解如下
代码实现
public class Test2 {
private int[] array;
private int usedSize; // 当前堆中的有效元素个数
Test2() {
array = new int[10]; // 通过构造方法给数组分配空间
}
// 向上调整保证是小根堆：时间复杂度是O(log以2为底的N)---log2N
public void shiftUp(int child) {
int parent = (child - 1) / 2;
while (parent >= 0) {
if (this.array[child] < this.array[parent]) {
int tmp = this.array[child];
this.array[child] = array[parent];
this.array[parent] = tmp;
child = parent;
parent = (child - 1) / 2;
}
else {
break;
}
}
}
// 向堆中插入元素
public void offerHeap(int val) {
if (this.usedSize >= this.array.length) {
System.out.println("数组已满，插入失败！");
}
else {
this.array[usedSize] = val;
shiftUp(usedSize); // 插入数据后进行向上调整确保为小堆
++usedSize; // 堆中有效元素加一个
}
}
// 向上调整建立小根堆，时间复杂度是O(n * log2N)
public void createHeapUp() {
int[] a = {4, 2, 7, 8, 5, 1, 0, 6};
// 遍历a数组，将a数组中的元素一个一个的插入堆中
for (int i = 0; i < a.length; i++) {
offerHeap(a[i]);
}
}
public static void main(String[] args) {
Test2 test2 = new Test2();
test2.createHeapUp();
}
}
上面我们是一个一个的插入来建立小根堆的，那么我们能不能直接把数组看作是一个堆，然后对数组中的元素进行向上调整——建立小根堆呢？
当然可以，代码如下所示：
import java.util.Arrays; // 向上调整建立小根堆 public class Tmp { public static void main(String[] args) { Tmp tmp = new Tmp(); int[] array = {4, 2, 7, 8, 5, 1, 0, 6}; tmp.createHeapUp2(array); System.out.println(Arrays.toString(array)); } // 向上调整保证是小根堆：时间复杂度是O(log以2为底的N)---log2N public void shiftUp(int[] array, int child) { int parent = (child - 1) / 2; while (parent >= 0) { if (array[child] < array[parent]) { int tmp = array[child]; array[child] = array[parent]; array[parent] = tmp; child = parent; parent = (child - 1) / 2; } else { break; } } } // 建立小根堆的方法二： // 向上调整建立小根堆，时间复杂度是O(n * log2N) public void createHeapUp2(int[] array) { for (int i = array.length - 1; i > 0; --i) { shiftUp(array, i); // 对数组的每一个元素进行向上调整，从堆的最后一个叶子结点开始——既然是从下向上调整自然要从下面开始呀！ } } }
这个建堆的结果可能和向下调整来建堆一样，但思想其实是不同的
根据该数组建立小根堆
二、向下调整来建堆
思路：
因为向下调整的前提是根结点的左右子树均为小堆或大堆才可，而这里，数组为乱序的，无法直接从根结点开始向下调整
所以我们从倒数第一个非叶结点开始向下调整，从下往上调
分析：从该解决方案中，我们首先要找到这个倒数第一个非叶结点的数在哪？其实最后一个结点的父亲即为倒数第一个非叶结点。当我们找到这个非叶结点时，把它和它的孩子看成一个整体，进行向下调整。调整后，再将次父节点向前挪动，再次向下调整，依次循环下去。
再回顾下父亲和孩子间的关系：
- leftchild = parent*2 + 1
- rightchild = parent*2 + 2
- parent = (child - 1) / 2
过程图解
代码实现：
import java.util.Arrays;
public class Test3 {
public void createHeap(int[] arrays) {
// 倒数的第一个非叶子节点的子树开始调节，一直调节到根结点（根节点在数组中的下标为0）
// 注意这里是usdSize - 1 - 1,因为父亲结点的下标 = (孩子结点的下标 - 1） / 2，
// 我们是从倒数的第一个非叶子节点的子树开始调节的，而该子树的孩子结点坐标为arrays.length - 1
for (int i = (arrays.length - 1 - 1) / 2; i >= 0 ; --i) {
shiftDown(arrays, i); // 从下面的子树一直调到上面的子树
}
}
public void shiftDown(int[] arrays, int root) {
int parent = root; // 父亲结点的坐标
int child = 2 * parent + 1; // 获取左孩子结点的坐标
// 为什么不能child下标要小于usedSize,因为当前数组的最大下标就是usedSize - 1,如果大于或等于usedSize就越界了
while (child < arrays.length) { // 每个子树在调整的时候，是按从上到下，当child的下标小于usedSize时候就结束
// 这一步目的是找出孩子结点最小的那个值，然后在让该值和父亲结点比较（不过先要确定孩子结点存在）
if (child + 1 < arrays.length - 1 && arrays[child] > arrays[child + 1]) {
child = child + 1;
}
if (arrays[child] < arrays[parent]) {
int tmp = arrays[child];
arrays[child] = arrays[parent];
arrays[parent] = tmp;
parent = child; // 从上向下调整子树，更新父亲结点的下标
child = 2 * parent + 1; // 更新左孩子孩子结点的下标
}
// 因为我们是从上向下调整子树，当我们在调整上面的子树时，下面的子树一定是调整好了的，如果上面都已经满足小根堆，下面也一定满足
else {
break; // 此时已经是小根堆了，不需要再次调整，直接退出循环接着调整下一个子树
}
}
}
public static void main(String[] args) {
Test3 test3 = new Test3();
int[] a = {4, 2, 7, 8, 5, 1, 0, 6};
test3.createHeap(a);
// 注意我们建立的小根堆没有储存在a数组中，而是储存在Test3类中的elem数组中
System.out.println(Arrays.toString(a));
}
}
三、向上建堆和向下建堆的优劣比较
我们看一下他们各自的时间复杂度
栗子——一棵满完全二叉树
在构建这样一棵完全二叉树时，对于向上建堆
时间复杂度计算的是其调整的次数，根据上文的知识我们已经知晓其是从数组的第二个元素开始的，也就是可以理解为第二层的第一个节点。计算的思想非常简单：计算每层有多少个节点乘以该层的高度次，然后累计相加即可。如下：
通过计算得知：向上建堆的时间复杂度为O(N*logN)
那么向下建堆呢？
向下调整我们前面已经知道它是从倒数第1个非叶节点开始调整的
每层的调整次数为：该层的节点个数*该层高度减1
一直从倒数第2层开始调直至第1层，并将其依次累加，累加的计算过程和向上调整差不多，都是等比*等差的求和，（但不同的是：每层的调整次数不同）
综上，向下建堆其实性能更好一定
