堆排序是一种利用堆数据结构进行排序的算法。堆排序分为两个步骤，第一步是构建最大堆或最小堆，第二步是进行排序。
1、构建最大堆或最小堆
最大堆是一种二叉树结构，满足任意一个非叶子节点的值都不小于其左右子节点的值，堆顶元素即为最大值。最小堆则相反，任意一个非叶子节点的值都不大于其左右子节点的值，堆顶元素即为最小值。
堆的构建可以通过自下而上或自上而下两种方式实现。以构建最大堆为例，自下而上的方式需要从最后一个非叶子节点开始向上遍历整个二叉树，并对每个节点进行调整，使其满足最大堆的定义。自上而下的方式则需要从根节点开始，递归地对每个子树进行调整，同样需要满足最大堆的定义。
2、排序
排序的过程需要将堆顶元素和堆中的最后一个元素交换位置，然后将堆的大小减1，再对堆进行调整，使其重新满足最大堆或最小堆的定义。重复这个过程直到堆中只剩下一个元素为止。
堆排序的时间复杂度为 O(nlogn)，空间复杂度为 O(1)。它的优点是不需要额外的空间，且时间复杂度比其他基于比较的排序算法更优秀，但是它的常数因子较大，不适合排序小规模的数据。
代码实现：
package com.algorithm.sort;
import java.util.Arrays;
/**
* @author LuoFei
* @className: HeapSort
* @projectName algorithm
* @description: TODO
* @date 2023/2/23 16:21
*/
public class HeapSort {
public static void heapSort(int[] arr) {
System.out.println("初始堆如下：");
printHeap(arr);
System.out.println("开始构建初始大顶堆");
// 构建最大堆
buildMaxHeap(arr);
System.out.println("初始大顶堆如下：");
printHeap(arr);
System.out.println("=============初始大顶堆构建完成==================");
// 进行排序
System.out.println("开始排序");
int k=1;
for (int i = arr.length - 1; i >= 1; i--) {
System.out.println("---------------第"+(k++)+"轮排序--------------");
System.out.println("将堆顶元素与最后一个元素交换");
swap(arr, 0, i); // 将堆顶元素与最后一个元素交换
System.out.println("最新数组: "+Arrays.toString(arr));
System.out.println("剩余元素重新构建最大堆");
maxHeapify(arr, 0, i); // 对剩下的元素重新构建最大堆
System.out.println("============新大顶堆构建完成============");
}
System.out.println("最后一个元素无需比较，排序完成");
}
public static void buildMaxHeap(int[] arr) {
int heapSize = arr.length;
System.out.println("从最后一个非叶子节点开始构建最大堆");
for (int i = heapSize / 2 - 1; i >= 0; i--) { // 从最后一个非叶子节点开始构建最大堆
maxHeapify(arr, i, heapSize);
}
}
public static void maxHeapify(int[] arr, int index, int heapSize) {
System.out.println("**************构建大顶堆***************");
System.out.println("构建下标: "+index+"节点大顶堆");
int leftChild = 2 * index + 1; // 左孩子的下标
int rightChild = 2 * index + 2; // 右孩子的下标
int largest = index; // 保存最大元素的下标
System.out.println("左孩子的下标: "+leftChild+"; 右孩子的下标: "+rightChild+"; 定义最大元素的下标: "+largest);
// 找出当前节点、左孩子、右孩子中的最大元素
String left = leftChild<arr.length?arr[leftChild]+"":"";
System.out.println("比较左孩子节点：["+largest+", "+leftChild+"]数据：["+arr[largest]+", "+left+"]");
if (leftChild < heapSize && arr[leftChild] > arr[largest]) {
largest = leftChild;
System.out.println("左孩子比最大元素大，更新最大元素下标为: "+largest);
} else {
System.out.println("左孩子比最大元素小，不更新最大元素下标");
}
String right = rightChild<arr.length?arr[rightChild]+"":"";
System.out.println("比较右孩子节点：["+largest+", "+rightChild+"]数据：["+arr[largest]+", "+right+"]");
if (rightChild < heapSize && arr[rightChild] > arr[largest]) {
largest = rightChild;
System.out.println("右孩子比最大元素大，更新最大元素下标为: "+largest);
} else {
System.out.println("右孩子比最大元素小，不更新最大元素下标");
}
if (largest != index) { // 如果最大元素不是当前节点
System.out.println("最大元素下标变更");
swap(arr, index, largest); // 将最大元素和当前节点交换
System.out.println("最新堆：");
printHeap(Arrays.copyOfRange(arr, 0, heapSize));
maxHeapify(arr, largest, heapSize); // 递归调整堆
} else {
System.out.println("最大元素下标未变，不交换数据");
System.out.println("新堆：");
printHeap(Arrays.copyOfRange(arr, 0, heapSize));
}
}
public static void swap(int[] arr, int i, int j) {
System.out.println("交换节点: ["+i+", "+j+"]的数据: ["+arr[i]+", "+arr[j]+"]");
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void printHeap(int[] arr) {
int height = (int) (Math.floor(Math.log(arr.length)/Math.log(2))+1);
int width = (int) (Math.pow(2, height) - 1);
for (int i=1;i<=height;i++) {
int l = 0;
int size = (int) (Math.pow(2, i) - 1);
int white = (int) (Math.pow(2,height-i)-1);
for (int j=1;j<=white;j++) {
l++;
System.out.print("-");
}
int length = (int) Math.pow(2, i-1);
int start = size-length;
int end = size>=arr.length?arr.length-1:size-1;
while (start<=end) {
System.out.print(arr[start]);
int midWhite = (int) (Math.pow(2, height-i+1)-1);
midWhite = i==1?1:midWhite;
l++;
if (start<end) {
for (int k = 1; k <= midWhite; k++) {
l++;
System.out.print("-");
}
}
start++;
}
for (;l<width;l++) {
System.out.print("-");
}
System.out.println();
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 3, 9, 1};
System.out.println("堆排序");
System.out.println("初始数组："+ Arrays.toString(arr));
System.out.println("==============开始堆排序===============");
heapSort(arr);
System.out.println("==============堆排序完成===============");
System.out.println("最终数组"+Arrays.toString(arr));
}
}执行过程：
堆排序
初始数组：[5, 2, 8, 3, 9, 1]
==============开始堆排序===============
初始堆如下：
---5---
-2---8-
3-9-1--
开始构建初始大顶堆
从最后一个非叶子节点开始构建最大堆
**************构建大顶堆***************
构建下标: 2节点大顶堆
左孩子的下标: 5; 右孩子的下标: 6; 定义最大元素的下标: 2
比较左孩子节点：[2, 5]数据：[8, 1]
左孩子比最大元素小，不更新最大元素下标
比较右孩子节点：[2, 6]数据：[8, ]
右孩子比最大元素小，不更新最大元素下标
最大元素下标未变，不交换数据
新堆：
---5---
-2---8-
3-9-1--
**************构建大顶堆***************
构建下标: 1节点大顶堆
左孩子的下标: 3; 右孩子的下标: 4; 定义最大元素的下标: 1
比较左孩子节点：[1, 3]数据：[2, 3]
左孩子比最大元素大，更新最大元素下标为: 3
比较右孩子节点：[3, 4]数据：[3, 9]
右孩子比最大元素大，更新最大元素下标为: 4
最大元素下标变更
交换节点: [1, 4]的数据: [2, 9]
最新堆：
---5---
-9---8-
3-2-1--
**************构建大顶堆***************
构建下标: 4节点大顶堆
左孩子的下标: 9; 右孩子的下标: 10; 定义最大元素的下标: 4
比较左孩子节点：[4, 9]数据：[2, ]
左孩子比最大元素小，不更新最大元素下标
比较右孩子节点：[4, 10]数据：[2, ]
右孩子比最大元素小，不更新最大元素下标
最大元素下标未变，不交换数据
新堆：
---5---
-9---8-
3-2-1--
**************构建大顶堆***************
构建下标: 0节点大顶堆
左孩子的下标: 1; 右孩子的下标: 2; 定义最大元素的下标: 0
比较左孩子节点：[0, 1]数据：[5, 9]
左孩子比最大元素大，更新最大元素下标为: 1
比较右孩子节点：[1, 2]数据：[9, 8]
右孩子比最大元素小，不更新最大元素下标
最大元素下标变更
交换节点: [0, 1]的数据: [5, 9]
最新堆：
---9---
-5---8-
3-2-1--
**************构建大顶堆***************
构建下标: 1节点大顶堆
左孩子的下标: 3; 右孩子的下标: 4; 定义最大元素的下标: 1
比较左孩子节点：[1, 3]数据：[5, 3]
左孩子比最大元素小，不更新最大元素下标
比较右孩子节点：[1, 4]数据：[5, 2]
右孩子比最大元素小，不更新最大元素下标
最大元素下标未变，不交换数据
新堆：
---9---
-5---8-
3-2-1--
初始大顶堆如下：
---9---
-5---8-
3-2-1--
=============初始大顶堆构建完成==================
开始排序
---------------第1轮排序--------------
将堆顶元素与最后一个元素交换
交换节点: [0, 5]的数据: [9, 1]
最新数组: [1, 5, 8, 3, 2, 9]
剩余元素重新构建最大堆
**************构建大顶堆***************
构建下标: 0节点大顶堆
左孩子的下标: 1; 右孩子的下标: 2; 定义最大元素的下标: 0
比较左孩子节点：[0, 1]数据：[1, 5]
左孩子比最大元素大，更新最大元素下标为: 1
比较右孩子节点：[1, 2]数据：[5, 8]
右孩子比最大元素大，更新最大元素下标为: 2
最大元素下标变更
交换节点: [0, 2]的数据: [1, 8]
最新堆：
---8---
-5---1-
3-2----
**************构建大顶堆***************
构建下标: 2节点大顶堆
左孩子的下标: 5; 右孩子的下标: 6; 定义最大元素的下标: 2
比较左孩子节点：[2, 5]数据：[1, 9]
左孩子比最大元素小，不更新最大元素下标
比较右孩子节点：[2, 6]数据：[1, ]
右孩子比最大元素小，不更新最大元素下标
最大元素下标未变，不交换数据
新堆：
---8---
-5---1-
3-2----
============新大顶堆构建完成============
---------------第2轮排序--------------
将堆顶元素与最后一个元素交换
交换节点: [0, 4]的数据: [8, 2]
最新数组: [2, 5, 1, 3, 8, 9]
剩余元素重新构建最大堆
**************构建大顶堆***************
构建下标: 0节点大顶堆
左孩子的下标: 1; 右孩子的下标: 2; 定义最大元素的下标: 0
比较左孩子节点：[0, 1]数据：[2, 5]
左孩子比最大元素大，更新最大元素下标为: 1
比较右孩子节点：[1, 2]数据：[5, 1]
右孩子比最大元素小，不更新最大元素下标
最大元素下标变更
交换节点: [0, 1]的数据: [2, 5]
最新堆：
---5---
-2---1-
3------
**************构建大顶堆***************
构建下标: 1节点大顶堆
左孩子的下标: 3; 右孩子的下标: 4; 定义最大元素的下标: 1
比较左孩子节点：[1, 3]数据：[2, 3]
左孩子比最大元素大，更新最大元素下标为: 3
比较右孩子节点：[3, 4]数据：[3, 8]
右孩子比最大元素小，不更新最大元素下标
最大元素下标变更
交换节点: [1, 3]的数据: [2, 3]
最新堆：
---5---
-3---1-
2------
**************构建大顶堆***************
构建下标: 3节点大顶堆
左孩子的下标: 7; 右孩子的下标: 8; 定义最大元素的下标: 3
比较左孩子节点：[3, 7]数据：[2, ]
左孩子比最大元素小，不更新最大元素下标
比较右孩子节点：[3, 8]数据：[2, ]
右孩子比最大元素小，不更新最大元素下标
最大元素下标未变，不交换数据
新堆：
---5---
-3---1-
2------
============新大顶堆构建完成============
---------------第3轮排序--------------
将堆顶元素与最后一个元素交换
交换节点: [0, 3]的数据: [5, 2]
最新数组: [2, 3, 1, 5, 8, 9]
剩余元素重新构建最大堆
**************构建大顶堆***************
构建下标: 0节点大顶堆
左孩子的下标: 1; 右孩子的下标: 2; 定义最大元素的下标: 0
比较左孩子节点：[0, 1]数据：[2, 3]
左孩子比最大元素大，更新最大元素下标为: 1
比较右孩子节点：[1, 2]数据：[3, 1]
右孩子比最大元素小，不更新最大元素下标
最大元素下标变更
交换节点: [0, 1]的数据: [2, 3]
最新堆：
-3-
2-1
**************构建大顶堆***************
构建下标: 1节点大顶堆
左孩子的下标: 3; 右孩子的下标: 4; 定义最大元素的下标: 1
比较左孩子节点：[1, 3]数据：[2, 5]
左孩子比最大元素小，不更新最大元素下标
比较右孩子节点：[1, 4]数据：[2, 8]
右孩子比最大元素小，不更新最大元素下标
最大元素下标未变，不交换数据
新堆：
-3-
2-1
============新大顶堆构建完成============
---------------第4轮排序--------------
将堆顶元素与最后一个元素交换
交换节点: [0, 2]的数据: [3, 1]
最新数组: [1, 2, 3, 5, 8, 9]
剩余元素重新构建最大堆
**************构建大顶堆***************
构建下标: 0节点大顶堆
左孩子的下标: 1; 右孩子的下标: 2; 定义最大元素的下标: 0
比较左孩子节点：[0, 1]数据：[1, 2]
左孩子比最大元素大，更新最大元素下标为: 1
比较右孩子节点：[1, 2]数据：[2, 3]
右孩子比最大元素小，不更新最大元素下标
最大元素下标变更
交换节点: [0, 1]的数据: [1, 2]
最新堆：
-2-
1--
**************构建大顶堆***************
构建下标: 1节点大顶堆
左孩子的下标: 3; 右孩子的下标: 4; 定义最大元素的下标: 1
比较左孩子节点：[1, 3]数据：[1, 5]
左孩子比最大元素小，不更新最大元素下标
比较右孩子节点：[1, 4]数据：[1, 8]
右孩子比最大元素小，不更新最大元素下标
最大元素下标未变，不交换数据
新堆：
-2-
1--
============新大顶堆构建完成============
---------------第5轮排序--------------
将堆顶元素与最后一个元素交换
交换节点: [0, 1]的数据: [2, 1]
最新数组: [1, 2, 3, 5, 8, 9]
剩余元素重新构建最大堆
**************构建大顶堆***************
构建下标: 0节点大顶堆
左孩子的下标: 1; 右孩子的下标: 2; 定义最大元素的下标: 0
比较左孩子节点：[0, 1]数据：[1, 2]
左孩子比最大元素小，不更新最大元素下标
比较右孩子节点：[0, 2]数据：[1, 3]
右孩子比最大元素小，不更新最大元素下标
最大元素下标未变，不交换数据
新堆：
1
============新大顶堆构建完成============
最后一个元素无需比较，排序完成
==============堆排序完成===============
最终数组[1, 2, 3, 5, 8, 9]