我们之前在学习常见的算法时,说过关于堆排序的学习在有了一定对树了解的基础上讲解,因为堆排序是利用了树的一些特性,所以我们本节我们来学习什么是堆排序,接下来我们先介绍下什么是堆排序
堆排序介绍
首先堆排序是利用堆这种数据结构而设计的一种排序算法,同样堆排序也是一种选择算法,它的平均时间复杂度为O(nlogn),也是不稳定排序.
其次堆是具有以下性质的完全二叉树:
1.每个节点的值是大于等于其左右孩子节点的值的,因此我们称它为大顶堆,这里我们要注意一点:这里提到的不并要求节点的左孩子和右孩子的值的大小关系的
2.每个节点的值都小于或等于其左右孩子节点的值的,因此我们称它为小顶堆
大顶堆介绍
首先我们来看张图如下:
上述这个二叉树就是大顶堆,我们发现每个节点的值都是大于它的左右节点的值的,我们对堆中的节点进行按层编号,按照二叉树的顺序存储的特点映射到数组中如下图:
看完了什么是大顶堆我们来总结下大顶堆的特点:
arr[i] > =arr[2 *i+1] && arr[i] >=arr[2 *i +2] 其中变量i为对应第几个节点,当然i是从0开始的.也就是图中的所示,看完了大顶堆我们在来看看小顶堆的特点.
小顶堆介绍
首先我们来看张图如下:
上述这个二叉树就是小顶堆,我们发现每个节点的值都是小于它的左右节点的值的,我们对堆中的节点进行按层编号,按照二叉树的顺序存储的特点映射到数组中如下图:
看完了什么是小顶堆我们来总结下大顶堆的特点:
arr[i] <=arr[2 *i+1] && arr[i] <=arr[2 *i +2]
关于大顶堆和小顶堆的特点我们都介绍完了,接下来我们通过具体的实际案例来深入的学习我们的堆排序
案例分析
假设我有一个待排序的数组{4,6,8,5,9},通过使用堆排序的方式来将数组进行升序排序
看完了需求我们通过图解的方式来讲解该过程,首先需求要求我们是通过升序的方式来完成,那么我们这里采用构建大顶堆的方式来实现,具体实现过程请看如下讲解过程:
-
步骤一:构建初始堆,将给定的无序序列构建成一个大顶堆,如图:
构建大顶堆步骤1.png
- 1.1.此时我们从上述堆中最后一个非叶子节点开始,从左至右,从下至上调整.注意:这里叶子节点我们不做调整,我们的第一个非叶子节点的为 arr.length/2-1=5/2-1 = 1,也就是这里的节点6,具体调整过程如下图:
-
1.2.接着我们找到第二个非叶子节点也就是节点4,我们在{4,9,8}中进行比较发现9是最大的,因此我们进行4和9的交换,具体图解如下:
大顶堆构建图解3.png
- 1.3.我们可以发现,上述交换导致了我们的子根{4,5,6}的结构也需要调整,发现6大于4,我们进行4和6的交换
通过上述的这几步我们将一个无需序列构建成了一个大顶堆,接下来我们需要对堆顶元素和末尾元素进行交换,这样做的目的是为了始终确保末尾的元素是最大的,接着我们来看此过程:
- 步骤二 将堆顶元素和末尾元素进行交换,让末尾元素保持最大,接着我们继续调整堆,在将堆顶元素和末尾元素交换得到第二个最大的元素...反复交换和重建以及交换,具体过程如下图过程:
上述图中我们发现先是节点4和堆顶(节点9)进行位置交换,接着是我们发现节点6指向节点9的指针是断开的,这样的做的目的是我们在本轮的交换已经找到了最大值,为了下轮的交换和重建过程,我们的arr的大小会减1,也就是图中的{4,6,8,5},不在考虑元素9接着我们进行下轮的重建和交换过程.
- 2.1.我们在剩下的{4,6,8,5}元素中进行重新调整结构使其满足堆的定义,如下图:
通过上述的过程我们完成了大顶堆的构建过程,接着我们应该是交换堆顶和末尾的元素的位置,始终让其末尾的元素的值保持最大,具体过程如下图:
我们节点值最大的8进行排序之后,后面的过程就是继续调整,交换的过程,最终将使得我们的序列为有序的,我们接着看
上述已经调整为一个大顶堆,接着我们进行交换过程如下图:
通过上述的过程我们完成了最终的排序的过程,那么关于大顶堆完成排序的图解我们完成了,可能晕我们实质性的总结下在这个思路过程:
- 我们首先做的是将我们的无序序列构建成了一个大顶堆的过程
- 此时,我们其实也发现了整个序列最大的值就是我们堆顶的根节点
- 接着我们进行将堆顶和末尾的元素进行了交换,也就是说此时我们末尾成了最大值
- 然后我们接着将剩余的元素重新构建成了一个大顶堆,接着交换,如此反复执行,我们最终得到了一个有序序列.
在上述的过程中,我们每次的操作都会使得元素的个数在减少 .接着我们通过代码的方式来实现
代码实现
1.首先我们将要待排序的数组调整成一个大顶堆,代码如下:
/**
*
* @param arr 待调整的数组
* @param index 非叶子节点在数组中所对应的下标
* @param length 表示要对多少个元素进行调整,length每次调整完后都会减少
*/
public static void adjustHeap(int[] arr,int index, int length){
//1.1.定义一个临时的变量temp来保存我们index下标对应的值
int temp = arr[index];
//1.2.循环来处理
//说明:
// k = index *2+1 表示的是index所对应的左子节点
for (int k = index *2+1;k< length;k = k *2+1){
//k+1右子节点,我们需要找到最大节点
if (k +1 <length && arr[k] <arr[k+1]){ //说明左子节点的值小于右子节点的值
k++; //指向右子节点
}
if (arr[k] > temp){ //表示大于父节点
arr[index] = arr[k];//把较大的值赋给当前节点
index = k; //让index指向k,进行下一次的循环比较操作
}else {
break;
}
}
//当for循环结束后,表示我们已将index为父节点的树的最大值放在了最顶端(局部调整)
arr[index] = temp;//将temp放在调整后的位置
}
上述只是将无序序列调整为一个大顶堆的过程,接着我们来看排序的过程,代码如下:
//堆排序的方法
public static void heapSort(int[] arr){
//创建一个临时的变量用来保存调整的节点
int temp;
//首先我们将无序的序列构建成一个堆
for (int i = arr.length /2 -1; i >=0 ; i--) {
adjustHeap(arr,i,arr.length);
}
//2.将堆顶元素与末尾元素交换,这样做的目的是将最大元素沉到数组的末端
//3.重新构建,让其满足堆的定义,然后继续交换堆顶元素与末端元素,重复执行直到数组变得有序
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));
}
接着我们来看测试代码:
/**
* 堆排序(升序排列)----大顶堆
*/
public class HeapSort {
public static void main(String[] args) {
int[] arr = {4,6,8,5,9};
heapSort(arr);
}
测试结果如下图所示:
从测试结果来看,跟我们之前图解分析的结果是一致的,那么关于堆排序的学习就到这里了,想看全代码的可以在git上找
