图解堆排序

Quinta ·

更新时间:2024-11-14

· 958 次阅读

在学习堆排序前，我们需要知道顺序存储二叉树和堆的知识点。

一、顺序存储二叉树
1.概念：顺序存储二叉树即用数组的方式存储二叉树的节点
2.顺序存储二叉树的特点:
①顺序二叉树通常只考虑完全二叉树
②第n个元素的左子节点为 2 * n + 1
③第n个元素的右子节点为 2 * n + 2
④第n个元素的父节点为 (n-1) / 2
（n : 表示二叉树中的第几个元素(按0开始编号如图所示)
在这里插入图片描述
二、堆
1.概念：堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。（注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系）每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
2.大顶堆
在这里插入图片描述
我们对堆中的结点按层进行编号，映射到数组中就是下面这个样子:

大顶堆特点：arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2] （i 对应第几个节点，i从0开始编号）
3.小顶堆

小顶堆特点：arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2] （i 对应第几个节点，i从0开始编号）

一般升序采用大顶堆，降序采用小顶堆

三、堆排序
1.堆排序的基本思想：
①将待排序序列构造成一个大顶堆
②此时，整个序列的最大值就是堆顶的根节点。
③将其与末尾元素进行交换，此时末尾就为最大值。
④然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

2.堆排序步骤图解：
要求：给你一个数组 {4,6,8,5,9} , 要求使用堆排序法，将数组升序排序。
1）假设给定无序序列如下：
在这里插入图片描述
2）此时我们从最后一个非叶子节点开始，从左只有，从下至上进行调整。

3）找到第二个非叶子节点4，由于整颗二叉树中9最大，所以4和9交换。

4）这时，交换导致了左子树结构混乱，所以继续调整，左子树6最大，交换4和6。
在这里插入图片描述
到这一步，大顶堆构造完成。
5）将堆顶元素9和末尾元素交换

6）重新调整结构，使其继续满足大顶堆定义（注意，此时调整好的9不用动了）

7）再将堆顶元素8与末尾元素5进行交换，得到第二大元素8
在这里插入图片描述
8）类似的，继续进行调整，交换，反复进行，直到整个序列有序为止

3.堆排序代码实现

public class HeapSort {
    public static void main(String[] args) {
       int arr[]={4,6,8,5,9};
        System.out.println("排序前的数组="+ Arrays.toString(arr));
       heapSort(arr);
    }
    private static void heapSort(int[] arr) {
        int temp=0;
        //将无序序列构建成一个大顶堆
        //这里的i=arr.length/2-1是求出非叶子节点的数量
        for(int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }
        /**
         * 将堆顶元素与末尾元素进行交换，将最大元素交换至数组末端
         * 重新调整结构，使其满最大足堆定义，然后继续交换堆顶与当前末尾元素，直到整个序列有序
         */
         //这里的j表示的是需要调整的节点的个数，因为调整到最后时，最后一个节点就已经在它该在的位置了，所以是arr.length-1
        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));
    }
    /**将一个数组，调整成一个大顶堆
     * 完成将以i对应的非叶子节点的树调整成大顶堆
     * int arr[]={4,6,8,5,9};->i=1（即对以6为根节点的子树调整为大顶堆结构）->adjustHeap->得到{4,9,8,5,6}
     * 再次调用adjustHeap传入的是i=0（即对整颗树调整为大顶堆结构）->得到{4,9,8,5,6}->{9,6,8,5,4}
     * @param arr 待调整的数组
     * @param i 表示非叶子节点在数组中的索引
     * @param length 表示对多少个元素继续进行调整，length是在逐渐的减少
     */
    private static void adjustHeap(int[] arr, int i, int length) {
    int temp=arr[i];//先取出当前元素的值，保存在临时变量
    //k是i节点的左子节点
        for(int k=i*2+1;k<length;k=k*2+1){
           //此时的k+1=k*2+1+1=k*2+2即为i节点的右子节点
            if(k+1<length&&arr[k]temp){//如果子节点大于父节点
                arr[i]=arr[k];//把较大的值赋值给当前节点
                i=k;//i指向k，继续循环比较
            }else{
                break;
            }
        }
        //当for循环结束后，我们已经将以i为节点的树的最大值放在了最顶
        arr[i]=temp;//将temp值放到调整后的位置
    }
}

4.运行结果：
在这里插入图片描述