概念

堆排序的基本思想是利用堆这种数据结构进行排序。
堆是一个特殊的完全二叉树，分为大顶堆、小顶堆。

实现步骤

建堆：从最后一个非叶子节点开始，逐步向上调整每个节点，使其满足堆的性质。
排序：将堆顶元素（最大或最小）与数组末尾元素交换，然后对数组剩余元素重新调整为堆，重复这个过程直到数组有序。
备注：如做升序排序则创建大顶堆，降序排序则创建小顶堆

实际应用

1. 堆空间要求严格的场景：堆排序是一种原地排序算法，起空间复杂度为O(1)，适合在空间资源有限的环境中使用。
2. 部分排序场景：在某些情况下，可能只需要堆数据的一部分进行排序。堆排序可以高效的完成部分排序任务，因为它只需要构建部分堆，而不是整个数组。
**3. 动态数据处理：在动态数据流中，数据不断变化，需要频繁地重新排序。堆排序有这高效的重新排序能力。

代码实现

import java.util.Arrays;

/**
 * 堆排序
 * 1. 根据排序方式，确认创建大顶堆还是小顶堆
 * 2. 将堆顶元素 与 末尾元素进行交换，使其堆顶元素（最大或最小）沉至数组末尾
 * 3. 重新调整堆结构，使其满足堆定义（大顶堆、小顶堆），然后继续交换堆顶元素与末尾元素（排除掉以已调整过的数组尾部元素）
 * 4. 重复进行调整+交换动作，直至数组有序
 */
public class HeapSortDemo {
    public static void main(String[] args) {
        int[] array = {4,6,8,5,9,20,30,-1,-30,-5};
        heapSort(array, "asc");
        System.out.println(Arrays.toString(array));
    }

    /**
     * 排序方法
     * @param arr
     * @param way
     */
    public static void heapSort(int[] arr, String way) {
        if("asc".equals(way)) {
            for (int i = arr.length / 2 - 1; i >= 0; i--) {
                adjustHeapAes(arr,i, arr.length);
            }
            //调整堆顶元素与尾部元素位置
            for (int i = arr.length - 1; i > 0; i--) {
                int temp = arr[i];
                arr[i] = arr[0];
                arr[0] = temp;
                adjustHeapAes(arr, 0, i);
            }
        }
        if("desc".equals(way)) {
            for (int i = arr.length / 2 - 1; i >= 0; i--) {
                adjustHeapDesc(arr, i, arr.length);
            }
            //调整堆顶元素与尾部元素位置
            for (int i = arr.length - 1; i > 0; i--) {
                int temp = arr[i];
                arr[i] = arr[0];
                arr[0] = temp;
                adjustHeapDesc(arr, 0, i);
            }
        }

    }

    /**
     * 将以 i 为索引的子树，调整为大顶堆(升序)
     * @param array 待调整数组
     * @param i 非叶子结点在数组中的索引
     * @param length 调整的元素个数（排除尾部已调整元素）
     */
    public static void adjustHeapAes(int[] array, int i, int length) {
        int temp = array[i];    //临时存储当前数据
        //寻找当前 i 结点的左子结点 ; 当前结点的下一个结点：i*2+1 != 调整后的结点leftNodeIdx 退出循环
        for(int leftNodeIdx = i*2+1; leftNodeIdx<length; leftNodeIdx = i*2+1) {
            //调整当前树变为大顶堆，堆当前节点、当前结点的左/右子结点进行比较，调整为大顶堆
            if(leftNodeIdx+1 < length && array[leftNodeIdx] < array[leftNodeIdx+1]) {
                leftNodeIdx++;  //左子结点调换至右子结点位置
            }
            //判断左子结点值与 i结点值的大小
            if(array[leftNodeIdx] > temp) { //左子结点大于i结点
                array[i] = array[leftNodeIdx];  //调换位置
                i = leftNodeIdx; //更改左子结点索引
            }else{
                //不改变位置
                break;
            }
        }
        array[i] = temp;    //更改调整后的i索引位置的值
    }

    /**
     * 将以 i 为索引的子树，调整为小顶堆(降序)
     * 1. 确定树的高度：arr.length / 2 - 1 ; i结点的父节点：parentIndex = ( i - 1 ) / 2
     * 2. i索引结点的 左子节点：leftNodeIdx = i * 2 + 1  右子结点 rightNodeIdx =  i * 2 + 2 = leftNodeIdx + 1
     * @param array 待调整数组
     * @param i 非叶子结点在数组中的索引
     * @param length 调整的元素个数（排除尾部已调整元素）
     */
    public static void adjustHeapDesc(int[] array, int i, int length) {
        int temp = array[i];    //临时存储当前数据
        //寻找当前 i 结点的左子结点 ; 当前结点的下一个结点：i*2+1 != 调整后的结点leftNodeIdx 退出循环
        for(int leftNodeIdx = i*2+1; leftNodeIdx<length; leftNodeIdx = i*2+1) {
            //调整当前树变为大顶堆，堆当前节点、当前结点的左/右子结点进行比较，调整为小顶堆
            if(leftNodeIdx+1 < length && array[leftNodeIdx+1] < array[leftNodeIdx]) {
                leftNodeIdx++;  //左子结点调换至右子结点位置
            }
            //判断左子结点值与 i结点值的大小
            if(array[leftNodeIdx] < temp) { //左子结点小于i结点
                array[i] = array[leftNodeIdx];  //调换位置
                i = leftNodeIdx; //更改左子结点索引
            }else{
                //不改变位置
                break;
            }
        }
        array[i] = temp;    //更改调整后的i索引位置的值
    }
}