要想了解“堆排序、大根堆、小根堆”是什么，首先要知道什么是 堆。
堆 是一种特别的 彻底二叉树，具有堆化的特性。
其存储结构类似于彻底二叉树，能够用数组实现。
与一般的排序方式所界说的 有序 不同，看似数组中的数字并未按照 升序 或 降序 摆放，但其实这棵树是已经有序的状态了。为什么呢？这就要引入 大、小根堆 的概念了：
大根堆: 父结点的值 大于或等于 其子结点的值
小根堆: 父结点的值 小于或等于 其子结点的值
由此能够看出，在上图所表明的堆中，不论哪一个结点为根，其子结点均大于根结点，因而这是一个 小根堆。
因为是一种特别的彻底二叉树，其性质与二叉树类似。它能以 O(logN)O(logN) 的时间复杂度完结刺进、删去和查找操作，经过调整数组中元素的顺序，维护堆的结构。
下面咱们以 大根堆 为例，对堆的两个重要操作: 下调 ( heapfiy ) 和 上调 ( heapInsert ) 进行说明。
若结点数组下标为 i ，则：
父结点数组下标：( i – 1 ) / 2;
左孩子数组下标：2 * i + 1 ;
右孩子数组下标：2 * i + 2 ;
下调 heapfiy
给定一个无序数组，期望调整成为一个大根堆。
向前持续移动，直到一切结点均遍历一遍，一切父结点均大于其孩子结点，便成为了一棵大根堆。
- 一句话总结：小数往下移
如图所示，6、7、5 是叶子结点，没有孩子。直到遍历到下标为 2 的 2 结点，小于了左子结点 6 ，交流。
接着遍历到了下标为 1 的 9 结点，不小于左右孩子 5 和 7 。因而不需求交流，直接跳过。
至此，整个遍历结束。将一个无序数组调整成为了大根堆。**留意：**例子中的数组刚好降序摆放，仅仅个偶然哦！
理解了思路，上代码：
// 建 大根堆
public static void heapify(int[] arr, int index, int heapSize) {
int left = index * 2 + 1;
while (left < heapSize) {
// 左右子树的最大值下标 largest
int largest = left + 1 < heapSize && arr[left] < arr[left + 1] ? left + 1 : left;
if (arr[largest] <= arr[index]) {
break;
} else {
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}
}
代码解说
因为堆是彻底二叉树，所以结点纷歧定有右子树，因而需求进行越界判别 left + 1 < heapSize，将左右子树的最大值下标赋给 largest。若最大值大于父结点，则进行交流，并持续向下传导：index = largest; left = index * 2 + 1; 。
上面代码进行了 一次下调 的完好操作即 heapify(), 将数组一切元素倒着遍历一遍即可完结整个大根堆的树立。
for (int i = arr.length - 1; i >= 0; i--) {
heapify(arr, i, arr.length);
}
上调 heapInsert
若提前不知道一切的数字（数字一个一个的给出），期望每给出一个数后，都能调整为一个大根堆。
此刻咱们能够换个方向考虑，从下往上刺进。
每给到一个数，调查父结点是否小于该结点，若小于该结点就交流。交流到新方位后持续判别，直到不能再往上交流停止。
- 一句话总结：大数往上移
例如，别离到来的数字序列为：2，5，6，4，9，7。
2，5 别离到来，5 结点往上移。
代码超级简单：
public static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
上面代码进行了 一次上调 的完好操作即 heapInsert(), 每到来一个数字就调用一次，此刻 index 值为 arr.length - 1 ，终究即可完结整个大根堆的树立。
堆排序
有了大根堆之后，咱们就能很轻松的进行堆排序了。其思想是将数组划分为 有序 和 无序 的部分，找到未排序部分的最值，放入到已排序部分中，直到未排序的部分为空。
每次将堆顶元素与最后一个元素进行交流，这样最大值就来到了数组的最后。因为堆顶发生了变化，或许不再是一个大根堆，因而进行 heapfiy 操作进行调整。
留意 ：此刻堆巨细减一（最后一个元素已经是有序部分了，不需求参与堆的调整）。
以此往复，直到一切的元素均排好序。
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// heapify
for (int i = arr.length - 1; i >= 0; i--) {
heapify(arr, i, arr.length);
}
int heapSize = arr.length;
swap(arr, 0, --heapSize);
while (heapSize > 0) {
heapify(arr, 0, heapSize);
swap(arr, 0, --heapSize);
}
}
// 建 大根堆
public static void heapify(int[] arr, int index, int heapSize) {
int left = index * 2 + 1;
while (left < heapSize) {
int largest = left + 1 < heapSize && arr[left] < arr[left + 1] ? left + 1 : left;
if (arr[largest] <= arr[index]) {
break;
} else {
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
理解了 heapInsert 操作之后，再来看堆排序的代码是不是很轻松呢？
下篇文章咱们持续对 堆 做进一步深入的学习 —— 手写加强堆！
~点赞 ~ 重视 ~ 不迷路 ~！！！
——-往期回忆——-
