今天来总结一下堆数据结构的相关知识。
1.堆的概念：
堆是在完全二叉树的基础上进行了条件的限制，即：每个节点都比其孩子节点大，则为大堆；每个节点都比其孩子节点小则为小堆。
2.堆的性质：
a.堆中某个节点的值总是不大于或不小于其父节点的值；
b.堆总是一棵完全二叉树。
大堆、小堆示意图：
为什么堆适合使用顺序表（数组）存储呢？
解答：堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储；而对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。
参考如图：
3.堆中双亲节点与孩子节点的关系：
因为堆内部实际上使用数组存储且堆是一颗完全二叉树，所以双亲节点与孩子节点的坐标是有数学关系的，具体如下：
1.如果i为0，则i表示的节点为根节点，否则 双亲节点坐标 = （孩子节点坐标 + 1）/ 2；
2.左孩子坐标 = 2 * 双亲节点坐标 + 1；
3.右孩子坐标 = 2 * 双亲节点坐标 + 2；
…
相关问题拓展：
1.如何知道下标i所在的元素有没有右（左）孩子：判断 2 * i + 2 >= size （右孩子下标是否合法，size为数组长度）。
2.如何知道下标i所在的元素有是不是叶子节点：判断 2 * i + 1 >= size && 2 * i + 2 >= size（即左孩子不存在&&右孩子不存在），简化一下就是 2 * i + 1 >= size ,因为堆是一棵完全二叉树，所以没有左孩子必定没有右孩子。
4.堆的构建：
4.1.堆的向下调整 / 堆化操作（小堆）：
以集合{ 27,15,19,18,28,34,65,49,25,37 }为例，根节点的左右子树已经完全满足小堆的性质，因此只需将根节点向下调整好即可，调整之后的集合顺序为{ 15,18,19,25,28,34,65,49,27,37 }，接下来代码实现做验证。
集合示例：
过程图示：
代码实现：
递归：时间复杂度O(log(n))，空间复杂度：O(n)
public class adjustDown {
public static void main(String[] args) {
int[] arr = new int[]{27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
recursionAdjust(arr, 0);
for (int i : arr) {
System.out.print(i + " ");
}
}
public static void recursionAdjust(int[] arr, int idx) {
//默认下标idx的左右孩子中左孩子比较小
int minIdx = 2 * idx + 1;
int rightIdx = 2 * idx + 2;
//若没有左孩子
if (minIdx >= arr.length) {
return;
}
//若左孩子不是两个孩子中的较小值
if (rightIdx < arr.length && arr[minIdx] > arr[rightIdx]) {
minIdx = rightIdx;
}
//比较要调整的元素是否大于其孩子的较小值
if (arr[idx] > arr[minIdx]) {
swap(arr, idx, minIdx);
recursionAdjust(arr, minIdx);
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
迭代：时间复杂度O(log(n))，空间复杂度O(1)
public class adjustDown {
public static void main(String[] args) {
int[] arr = new int[]{27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
iterationAdjust(arr, 0);
for (int i : arr) {
System.out.print(i + " ");
}
}
public static void iterationAdjust(int[] arr, int idx) {
//如果idx是叶子节点 则执行
while (2 * idx + 1 < arr.length) {
//左右孩子下标
int minIdx = 2 * idx + 1;
int rightIdx = 2 * idx + 2;
if (rightIdx < arr.length && arr[minIdx] > arr[rightIdx]) {
minIdx = rightIdx;
}
//比较要调整的元素是否大于其孩子的较小值
if (arr[idx] > arr[minIdx]) {
swap(arr, idx, minIdx);
}
idx = minIdx;
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
4.2.堆的创建（大堆）：
给定无序的序列列{ 1,5,3,8,7,6 }，以创建大堆为例，思路是从尾结点开始，由最后一个节点找到它的双亲节点，然后对其进行向下调整，这样就形成了一个子小堆，然后一直循环操作就可以逐渐形成完整的小堆了。
过程图示：
代码实现：时间复杂度O(n)
public class Operation {
public static void main(String[] args) {
int[] arr = new int[]{1,5,3,8,7,6 };
createHeap(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
//建堆
public static void createHeap(int[] arr) {
// 找倒数第一个节点的双亲节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整
//arr.length - 1 为最后一个节点下标，再 - 1 除 2 为它的双亲节点
int pIdx = (arr.length - 1 - 1) / 2;
for (; pIdx >= 0; pIdx--) {
iterationAdjust(arr, pIdx);
}
}
//迭代向下调整
public static void iterationAdjust(int[] arr, int idx) {
//如果idx是叶子节点 则执行
while (2 * idx + 1 < arr.length) {
//左右孩子下标
int minIdx = 2 * idx + 1;
int rightIdx = 2 * idx + 2;
if (rightIdx < arr.length && arr[minIdx] < arr[rightIdx]) {
minIdx = rightIdx;
}
//比较要调整的元素是否小于其孩子的较大值
if (arr[idx] < arr[minIdx]) {
swap(arr, idx, minIdx);
}
idx = minIdx;
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
5.堆的插入与删除：
5.1.插入：
堆的插入总共需要两个步骤：
1.先将元素放入到底层空间中(注意：空间不够时需要扩容)
2. 将最后新插入的节点向上调整，直到满足堆的性质
ps：核心即为向上调整
过程图示：
5.2.删除：
堆的删除一定删除的是堆顶元素。具体如下：
1.将堆顶元素对堆中最后一个元素交换
2. 将堆中有效数据个数减少一个
3. 对堆顶元素进行向下调整
过程图示：
