总目录：地址如下看总纲
1、堆的基本介绍
- 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
- 堆是具有以下性质的完全二叉树：
1、每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。
2、每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
3、注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。
1、何为大顶堆和小顶堆
大顶堆(升序)
大顶堆特点：arr[i] >= arr[2*i+1] && arr[i] >= arr[2 * i + 2 ] // i 对应第几个节点，i从0开始编号
image.png
我们对堆中的结点按层进行编号，映射到数组中就是下面这个样子:
image.png
小顶堆(降序)
小顶堆特点：arr[i] <= arr[2*i+1] && arr[i] <= arr[2 * i+2] // i 对应第几个节点，i从0开始编号
image.png
- 一般升序采用大顶堆，降序采用小顶堆
3、堆排序的基本思想
- 将待排序序列构造成一个大顶堆
- 构造完后的整个序列的最大值就是堆顶的根节点
- 将其与末尾元素进行交换，此时末尾就为最大值
- 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
- 可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了
- 大顶堆和小顶堆的代码本质区别的公式 ：这边案例写的是大顶堆(升序)
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
4、详细案例分解：
步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)
（1）假设给定无序序列结构如下：
image.png
（2）此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整
image.png
（3）找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换
image.png
（4）这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6
image.png
（5）此时，我们就将一个无序序列构造成了一个大顶堆
步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换
（1）将堆顶元素9和末尾元素4进行交换
image.png
（2）重新调整结构，使其继续满足堆定义
image.png
（3）再将堆顶元素 8 与末尾元素 5 进行交换，得到第二大元素 8
image.png
（4）后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
image.png
- 步骤总结：
1).将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
2).将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端
3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序
5、代码
**
* title: 堆排序(大顶堆案例--800W数据测试
* @author 阿K
* 2021年1月2日 下午11:22:55
*/
public class HeapSort {
public static void main(String[] args) {
// 要求将数组进行升序排序
// int arr[] = {4, 6, 8, 5, 9};
// heapSort(arr);
// System.out.println(Arrays.toString(arr));
// 800w 数据测试
int[] arr = new int[8000000];
for (int i = 0; i < 8000000; i++) {
arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
}
long time1 = System.currentTimeMillis();
heapSort(arr);
long time2 = System.currentTimeMillis();
System.out.println("堆排序实现大顶堆排序800W数据：" + (time2 - time1) + "毫秒");
}
/**
* 构建堆排序(最终调用)
* @param arr 传入的数组
*/
public static void heapSort(int[] arr) {
int temp = 0;
// 分步测试
// adjustHeap(arr, 1, arr.length);
// System.out.println("第一次" + Arrays.toString(arr)); // 4, 9, 8, 5, 6
// adjustHeap(arr, 0, arr.length);
// System.out.println("第二次" + Arrays.toString(arr)); // 9, 6, 8, 5, 4
// 完整步骤
// 将无序序列构建成的一个堆，根据升序或者降序，选择大顶堆或者小顶堆
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
// 将堆顶元素与末尾元素交换，将最大元素 "沉"到数组末端
// 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，（就这样反复执行 【调整 -> 交换】，直到整个序列有序）
// 时间复杂度 为线性 O(nlogn)
for (int j = arr.length - 1; j > 0; j--) {
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0, j);
}
}
/**
* 将一个数组（二叉树），调整成一个大顶堆
* 功能：完成将 以 i 对应的非叶子节点的树调整成大顶堆
* eg：第一次：int arr[] = {4, 6, 8, 5, 9}; => adjustHeap(i=1) => 得到 {4, 9, 8, 5, 6}
* eg：第一次：int arr[] = {4, 9, 8, 5, 6}; => adjustHeap(i=0) => 得到 {9, 6, 8, 5, 4}
* @param arr 待调整的数组
* @param i 表非叶子节点在数组中的索引
* @param length 表对多少个元素进行调整（length会逐渐减少，因为被调整好的增加了）
*/
public static void adjustHeap(int[] arr, int i, int length) {
// 先取出当前元素的值，报错在临时变量中
int temp = arr[i];
// 开始调整
// 故：k = 2*i+1; 表示 k 是 i节点的左子节点
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {// k=2*k+1 ,k 左子节点的左子节点
if (k + 1 < length && arr[k] < arr[k + 1]) {// 说明左子节点的值，小于右子节点的值
k++;// k 指向右子节点
}
if (arr[k] > temp) {// 若子节点大于父节点的值
arr[i] = arr[k]; // 把较大的值赋值给当前节点
i = k;// 指向 k,继续比较(移动)
} else {
break;
}
}
// 当for 循环结束后,已经将以 i 为父节点的树的最大值，放在最顶点(局部)
arr[i] = temp;// 将 temp放到调整后的位置
}
}
6、性能测试和总结
作者的机子平均在 2000 - 2300 毫秒
image.png
- 可见速度相当快，平均时间复杂度均为O(nlogn)，它也是不稳定排序
网友评论