排序算法 - 堆排序

1. 什么是堆

堆的本质上是一种完全二叉树，它分为两个类型

最大堆： 最大堆的任何一个父节点的值，都大于或等于它左、右孩子节点的值

在这里插入图片描述

最小堆： 最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值

在这里插入图片描述

堆的根节点叫做堆顶

最大堆和最小堆的特点决定了最大堆的堆顶是整个堆中的最大元素，最小堆的堆顶就是整个堆中的最小元素

在这里插入图片描述

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆排序

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

步骤一构建堆：也就是把一个无需的完全二叉树调整为堆，本质就是让所有非叶子节点依次 "下沉"

在这里插入图片描述

首先，从最后一个叶子节点开始，也就是从节点10开始，如果节点10大于它左、右孩子节点中最小的一个，则节点10 "下沉"

在这里插入图片描述

接下来轮到节点3，如果节点3大于它左、右孩子节点中最小的一个，则节点3 "下沉"

在这里插入图片描述

然后轮到节点1，如果节点1大于它左、右孩子节点中最小的一个，则节点1 "下沉"。事实上节点1小于它左右孩子，所以不用改变

在这里插入图片描述

接下来轮到节点7，如果节点7大于它左右孩子节点中最小的一个，则节点7 "下沉"

在这里插入图片描述

经过上述几轮比较和 "下沉" 操作，最终每一节点都小于它的左右孩子节点，一个无需的完全二叉树就被构建成一个最小堆。

步骤二将堆顶元素与末尾元素进行交换，使末尾元素最小。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二小元素。如此反复进行交换、重建、交换。

将堆顶元素1和末尾元素10进行交换

在这里插入图片描述

.重新调整结构，使其继续满足堆定义

在这里插入图片描述

再将堆顶元素2与末尾元素9进行交换，得到第二小元素2

在这里插入图片描述
后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

在这里插入图片描述

总结：

把无序数组构建成堆，需要从小到大排序，则构建成最大堆；需要从大到小排序，则构建成最小堆。
循环删除堆顶元素，替换到堆的末尾，调整堆产生新的堆顶

代码：

package com.personal.task;

import java.util.Arrays;

public class test {


    public static void heapSort(int[] arr){
        for(int i = arr.length; i > 0; i--){
            min_heapify(arr, i);   //得到小顶堆
            int temp = arr[0];    //堆顶元素(第一个元素)与Kn交换
            arr[0] = arr[i-1];
            arr[i-1] = temp;
        }
    }
    private static void min_heapify(int[] arr, int limit){
        if(arr.length <= 0 || arr.length < limit) return;     //limit表示剩余的无序数组的长度
        for(int parentIdx = limit/2; parentIdx >= 0; parentIdx--){
            if(parentIdx * 2 >= limit){
                continue;
            }
            int left = parentIdx * 2;       //左子节点位置
            int right = (left+1) >= limit ? left : (left + 1);   //右子节点位置，如果没有右节点，默认为左节点位置
            int minChildId = arr[left] <= arr[right] ? left : right;
            if(arr[minChildId] < arr[parentIdx]){   //交换父节点与左右子节点中的最小值
                int temp = arr[parentIdx];
                arr[parentIdx] = arr[minChildId];
                arr[minChildId] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {7,1,3,10,5,2,8,9,6};
        heapSort(arr);
        System.out.printf(Arrays.toString(arr));
    }


}

[10, 9, 8, 7, 6, 5, 3, 2, 1]

个人博客地址：http://blog.yanxiaolong.cn ｜ 『纵有疾风起，人生不言弃』

最后编辑于：2021.06.20 23:35:28