可以看到在构建大顶堆的过程中,元素的个数逐渐减少,最后就得到一个有序序列了.
步骤一 构造初始堆。将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆)。 原始的数组 [4, 6, 8, 5, 9]
此时,我们就将一个无序序列构造成了一个大顶堆。
步骤二 将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换.
得到第二大元素。如此反复进行交换、重建、交换。
要求:给你一个数组 {4,6,8,5,9} , 要求使用堆排序法,将数组升序排序。
package com.hyc.DataStructure.tree;
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.tree
* @className: HeapSort
* @author: 冷环渊 doomwatcher
* @description: TODO
* @date: 2022/2/6 23:52
* @version: 1.0
*/
public class HeapSort {
public static void main(String[] args) {
int[] test = new int[8000000];
//测试数据
for (int i = 0; i < 8000000; i++) {
test[i] = (int) (Math.random() * 800000);
}
long time = System.currentTimeMillis();
heapsort(test);
long end = System.currentTimeMillis();
long t = ((end - time) / 1000);
System.out.println("一共用时 " + t + "秒");
int arr[] = {4, 6, 8, 5, 9};
}
public static void heapsort(int[] arr) {
int temp = 0;
//按照 大顶堆的方式调整堆
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
/*将最大元素和末尾元素交换,将最大元素放入数组末尾
*重新调整结构,满足堆的定义
* */
for (int j = arr.length - 1; j > 0; j--) {
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0, j);
}
//System.out.println("排序后的数组是 = " + Arrays.toString(arr));
}
/**
* @author 冷环渊 Doomwatcher
* @context:
* 大顶堆交换思路, 判断左右节点大小,之后判断左右节点的比对结果,与父节点判断,将最大值交还给父节点
* @date: 2022/2/6 23:54
* @param arr 存放需要将交换节点的数组
* @param i 需要做调整的父节点索引
* @param length 有多少节点需要调整
* @return: void
*/
public static void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i];
// 开始调整
/* 说明
* k =i*2+1按照之前线索查找树的公式,找出左子树的节点位置
* */
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
//判断条件 k(节点索引)首先不能大于我们要遍历的结点索引总数,之后判断左右节点的大小,交换
if (k + 1 < length && arr[k] < arr[k + 1]) {
k++;
}
//找出最大的子节点,与父节点的值比对,
if (arr[k] > temp) {
//将较大的值放入到父节点
arr[i] = arr[k];
i = k; //i指向k , 继续循环比较
} else {
break;
}
}
// for 循环结束之后 我们i已经是父节点以及最大值的索引了
// 将 temp 调整到最后得位置
arr[i] = temp;
}
}