树结构入门教程-堆排序

2020-03-13  本文已影响0人  会上树的程序猿

我们之前在学习常见的算法时,说过关于堆排序的学习在有了一定对树了解的基础上讲解,因为堆排序是利用了树的一些特性,所以我们本节我们来学习什么是堆排序,接下来我们先介绍下什么是堆排序

堆排序介绍

首先堆排序是利用堆这种数据结构而设计的一种排序算法,同样堆排序也是一种选择算法,它的平均时间复杂度为O(nlogn),也是不稳定排序.

其次堆是具有以下性质的完全二叉树:

1.每个节点的值是大于等于其左右孩子节点的值的,因此我们称它为大顶堆,这里我们要注意一点:这里提到的不并要求节点的左孩子和右孩子的值的大小关系的

2.每个节点的值都小于或等于其左右孩子节点的值的,因此我们称它为小顶堆

大顶堆介绍

首先我们来看张图如下:

大顶堆.png

上述这个二叉树就是大顶堆,我们发现每个节点的值都是大于它的左右节点的值的,我们对堆中的节点进行按层编号,按照二叉树的顺序存储的特点映射到数组中如下图:

大顶堆的顺序存储.png

看完了什么是大顶堆我们来总结下大顶堆的特点:
arr[i] > =arr[2 *i+1] && arr[i] >=arr[2 *i +2] 其中变量i为对应第几个节点,当然i是从0开始的.也就是图中的所示,看完了大顶堆我们在来看看小顶堆的特点.

小顶堆介绍

首先我们来看张图如下:

小顶堆.png

上述这个二叉树就是小顶堆,我们发现每个节点的值都是小于它的左右节点的值的,我们对堆中的节点进行按层编号,按照二叉树的顺序存储的特点映射到数组中如下图:

小顶堆顺序存储.png

看完了什么是小顶堆我们来总结下大顶堆的特点:
arr[i] <=arr[2 *i+1] && arr[i] <=arr[2 *i +2]

关于大顶堆和小顶堆的特点我们都介绍完了,接下来我们通过具体的实际案例来深入的学习我们的堆排序

案例分析

假设我有一个待排序的数组{4,6,8,5,9},通过使用堆排序的方式来将数组进行升序排序

看完了需求我们通过图解的方式来讲解该过程,首先需求要求我们是通过升序的方式来完成,那么我们这里采用构建大顶堆的方式来实现,具体实现过程请看如下讲解过程:

数组1.png 大顶堆构建图解2.png 数组2.png 数组3.png 大顶堆构建图解4.png
数组4.png

通过上述的这几步我们将一个无需序列构建成了一个大顶堆,接下来我们需要对堆顶元素和末尾元素进行交换,这样做的目的是为了始终确保末尾的元素是最大的,接着我们来看此过程:

大顶堆交换顺序1.png 交换数组1.png

上述图中我们发现先是节点4和堆顶(节点9)进行位置交换,接着是我们发现节点6指向节点9的指针是断开的,这样的做的目的是我们在本轮的交换已经找到了最大值,为了下轮的交换和重建过程,我们的arr的大小会减1,也就是图中的{4,6,8,5},不在考虑元素9接着我们进行下轮的重建和交换过程.

大顶堆顺序调整2.png 顺序调整数组2.png

通过上述的过程我们完成了大顶堆的构建过程,接着我们应该是交换堆顶和末尾的元素的位置,始终让其末尾的元素的值保持最大,具体过程如下图:

大顶堆顺序调整3.png 顺序调整数组3.png

我们节点值最大的8进行排序之后,后面的过程就是继续调整,交换的过程,最终将使得我们的序列为有序的,我们接着看

大顶堆顺序调整4.png
顺序调整数组5.png

上述已经调整为一个大顶堆,接着我们进行交换过程如下图:

[图片上传中...(顺序调整数组6.png-7bf634-1584106192597-0)] 顺序调整数组6.png

通过上述的过程我们完成了最终的排序的过程,那么关于大顶堆完成排序的图解我们完成了,可能晕我们实质性的总结下在这个思路过程:

在上述的过程中,我们每次的操作都会使得元素的个数在减少 .接着我们通过代码的方式来实现

代码实现

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);
}

测试结果如下图所示:

测试结果图.png

从测试结果来看,跟我们之前图解分析的结果是一致的,那么关于堆排序的学习就到这里了,想看全代码的可以在git上找

上一篇 下一篇

猜你喜欢

热点阅读