堆排序
算法定义
堆排序（Heap Sort）是一种基于堆数据结构的高效排序算法，它利用堆的特性（父节点的值大于等于或小于等于子节点的值）来实现排序。堆排序属于选择排序的一种改进，通过反复提取堆顶元素（最大值或最小值）并调整堆结构，最终得到有序数组。
堆是一种完全二叉树，分为两种类型：
- 大顶堆：每个父节点的值大于等于其子节点的值
- 小顶堆：每个父节点的值小于等于其子节点的值
堆排序通常使用大顶堆实现升序排序。
算法思路
堆排序的核心步骤如下：
- 构建堆：将无序数组转换为大顶堆（或小顶堆）。
- 提取堆顶元素：将堆顶元素（最大值）与数组末尾元素交换，此时最大值已放到正确位置。
- 调整堆：将剩余元素重新调整为大顶堆。
- 重复操作：重复步骤 2-3，直到所有元素排序完成。
例如，排序[4, 10, 3, 5, 1]：
- 构建大顶堆：
[10, 5, 3, 4, 1] - 交换堆顶与末尾元素：
[1, 5, 3, 4, 10]，调整堆为[5, 4, 3, 1, 10] - 重复操作，最终得到
[1, 3, 4, 5, 10]
算法复杂度
- 最好时间复杂度：O (n log n) - 无论输入数据分布如何，复杂度保持稳定
- 最坏时间复杂度：O (n log n) - 与最好情况相同
- 平均时间复杂度：O(n log n)
- 空间复杂度：O (1) - 原地排序，只需常数级额外空间
优点与缺点
- 优点：
- 时间复杂度稳定为 O (n log n)，不受输入数据影响
- 原地排序，空间复杂度低（O (1)）
- 适合处理大规模数据
- 可高效解决 Top K 问题
- 缺点：
- 不稳定的排序算法（相等元素的相对位置可能改变）
- 缓存友好性较差（堆操作涉及非连续内存访问）
- 实现相对复杂，需要理解堆的结构和调整逻辑
应用场景
- 需要 O (n log n) 时间复杂度且空间有限的场景
- Top K 问题（如获取数组中最大的 K 个元素）
- 优先级队列的实现
- 操作系统的进程调度
- 大数据处理中的部分排序需求
各版本优化说明
- 基本版（大顶堆）：
- 经典实现，使用递归方式进行堆调整
- 清晰展示堆排序的核心流程：建堆→提取堆顶→调整堆
- 适合理解堆排序的基本原理
- 迭代版堆调整：
- 将递归的堆调整改为迭代实现，减少递归调用开销
- 避免了递归可能带来的栈溢出风险
- 实际运行效率通常高于递归版本
- 小顶堆实现降序：
- 使用小顶堆实现降序排序，扩展了堆排序的应用场景
- 展示了堆排序的灵活性，通过改变堆的类型可实现不同排序方向
- 混合插入排序优化：
- 当剩余元素数量小于阈值（如 15）时，改用插入排序
- 利用插入排序在小规模数据上的高效性，减少堆操作的开销
- 综合性能优于纯堆排序，尤其对中等规模数据
堆排序是一种高效稳定的排序算法，时间复杂度始终为 O (n log n)，且空间开销小，适合处理大规模数据。虽然实现稍复杂，但在对排序稳定性要求不高且需要控制空间开销的场景中表现出色。Java 的PriorityQueue底层就使用了堆结构，可用于实现高效的优先级排序。
代码
import java.util.Arrays;
public class HeapSort {
// 1. 基本版堆排序（大顶堆实现升序）
public static void heapSortBasic(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
// 构建大顶堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapifyBasic(arr, n, i);
}
// 提取堆顶元素并调整堆
for (int i = n - 1; i > 0; i--) {
// 交换堆顶（最大值）和当前末尾元素
swap(arr, 0, i);
// 调整剩余元素为大顶堆
heapifyBasic(arr, i, 0);
}
}
// 基本版堆调整（大顶堆）
private static void heapifyBasic(int[] arr, int heapSize, int i) {
int largest = i; // 根节点索引
int left = 2 * i + 1; // 左子节点索引
int right = 2 * i + 2; // 右子节点索引
// 找出根、左、右三个节点中的最大值
if (left < heapSize && arr[left] > arr[largest]) {
largest = left;
}
if (right < heapSize && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是根节点，则交换并继续调整
if (largest != i) {
swap(arr, i, largest);
heapifyBasic(arr, heapSize, largest);
}
}
// 2. 优化版1：迭代实现堆调整（避免递归开销）
public static void heapSortIterative(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
// 构建大顶堆（迭代方式）
for (int i = n / 2 - 1; i >= 0; i--) {
heapifyIterative(arr, n, i);
}
// 提取堆顶元素并调整
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
heapifyIterative(arr, i, 0);
}
}
// 迭代版堆调整
private static void heapifyIterative(int[] arr, int heapSize, int i) {
while (true) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < heapSize && arr[left] > arr[largest]) {
largest = left;
}
if (right < heapSize && arr[right] > arr[largest]) {
largest = right;
}
if (largest == i) {
break; // 不需要继续调整
}
swap(arr, i, largest);
i = largest; // 继续调整子树
}
}
// 3. 优化版2：小顶堆实现降序排序
public static void heapSortDescending(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
// 构建小顶堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapifyMin(arr, n, i);
}
// 提取堆顶元素（最小值）并调整
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
heapifyMin(arr, i, 0);
}
}
// 小顶堆调整
private static void heapifyMin(int[] arr, int heapSize, int i) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < heapSize && arr[left] < arr[smallest]) {
smallest = left;
}
if (right < heapSize && arr[right] < arr[smallest]) {
smallest = right;
}
if (smallest != i) {
swap(arr, i, smallest);
heapifyMin(arr, heapSize, smallest);
}
}
// 4. 优化版3：混合排序（小规模数据使用插入排序）
public static void heapSortHybrid(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
final int INSERTION_THRESHOLD = 15;
// 对于小规模数据，直接使用插入排序
if (n <= INSERTION_THRESHOLD) {
insertionSort(arr, 0, n - 1);
return;
}
// 构建大顶堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapifyIterative(arr, n, i);
}
// 提取堆顶元素，当剩余元素小于阈值时使用插入排序
for (int i = n - 1; i > INSERTION_THRESHOLD; i--) {
swap(arr, 0, i);
heapifyIterative(arr, i, 0);
}
// 对剩余的小规模元素使用插入排序
insertionSort(arr, 0, INSERTION_THRESHOLD);
}
// 辅助插入排序
private static void insertionSort(int[] arr, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int key = arr[i];
int j = i - 1;
while (j >= left && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// 交换元素
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7, 9, 3, 2, 1};
int[] arr1 = Arrays.copyOf(arr, arr.length);
int[] arr2 = Arrays.copyOf(arr, arr.length);
int[] arr3 = Arrays.copyOf(arr, arr.length);
int[] arr4 = Arrays.copyOf(arr, arr.length);
heapSortBasic(arr1);
System.out.println("基本版（大顶堆升序）: " + Arrays.toString(arr1));
heapSortIterative(arr2);
System.out.println("迭代版堆调整: " + Arrays.toString(arr2));
heapSortDescending(arr3);
System.out.println("小顶堆实现降序: " + Arrays.toString(arr3));
heapSortHybrid(arr4);
System.out.println("混合插入排序优化: " + Arrays.toString(arr4));
}
}
公式
// 父节点的值等于 (子结点i-1)/2
parent = (i-1)/2
// 左子节点等于(父结点i * 2) + 1
c1 = i*2 + 1
// 左子节点等于(父结点i * 2) + 2
c2 = i*2 + 2
heapify（堆化）
/**
* @param tree 要做heapify的数组
* @param n 这个数组的长度
* @param i 要对哪个结点做heapify
*/
public static void heapify(int[] tree, int n, int i) {
if (i >= n) return; // 结点的长度超过总长度就退出
int c1 = 2 * i + 1; // i结点的左孩子结点
int c2 = 2 * i + 2; // i结点的右孩子结点
int max = i; // 先假设i结点的值最大
// 判断左孩子结点小于数组长度并且左孩子的值大于父亲结点，那么更换最大结点索引位置为左节点
if (c1 < n && tree[c1] > tree[max]) {
max = c1;
}
// 判断右孩子结点小于数组长度并且右孩子的值大于父亲结点，那么更换最大结点索引位置为右节点
if (c2 < n && tree[c2] > tree[max]) {
max = c2;
}
// 如果max值和父亲结点不一致，说明孩子结点比父节点大，那么更换两个结点的值，并且重新根据孩子结点的位置进行堆化
if (max != i) {
SortUtils.swap(tree, max, i);
heapify(tree, n, max);
}
}
构建堆
// nums.length - 1 是完全二叉树中最后一个结点
int cLast = nums.length - 1;
// 最底层的开始heapify结点(从第一个非叶子节点开始)公式 ((nums.length-1) - 1)/2
int heapifyBeginIndex = cLast - 1 >> 1;
for (int i = heapifyBeginIndex; i >= 0; i--) {
heapify(nums, nums.length, i); // 从第一个非叶子结点开始堆化，直到第0个位置
}
堆排序
每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换
然后重新整理被换到根节点的末尾元素，使其符合堆的特性(堆化 heapify)
直至未排序的堆长度为 0。
for (int i = cLast; i >= 0; i--) {
SortUtils.swap(nums, i, 0); // 交换0位置和最后位置，使最大值排在最后
heapify(nums, i, 0); // 然后对减一的数组长度进行堆化
}
完整堆排序
public static void main(String[] args) {
int[] nums = new int[]{4, 1, 3, 5, 10, 2};
System.out.println(Arrays.toString(nums));
heapSort(nums);
System.out.println(Arrays.toString(nums));
}
public static void heapSort(int[] nums) {
int cLast = nums.length - 1;
int heapifyBeginIndex = cLast - 1 >> 1;
/*
* 第一步：将数组堆化
* beginIndex = 第一个非叶子节点(最后一个叶子结点的父节点) 求父结点公式(i-1)/2 ((n-1)-1)/2
* 从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
* 叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
*/
for (int i = heapifyBeginIndex; i >= 0; i--) {
heapify(nums, nums.length, i);
}
/*
* 第二步：对堆化数据排序
* 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，遍历n-1次，从后面遍历i=n-1大于0，交换两个元素循环次数就是n-1，像冒冒泡排序i=0，<n-1
* 然后重新整理被换到根节点的末尾元素，使其符合堆的特性(堆化 heapify)
* 直至未排序的堆长度为 0。
*/
for (int i = cLast; i >= 0; i--) {
SortUtils.swap(nums, i, 0);
heapify(nums, i, 0);
}
}
/**
* @param tree 要做heapify的数组
* @param n 这个数组的长度
* @param i 要对哪个结点做heapify
*/
public static void heapify(int[] tree, int n, int i) {
if (i >= n) return; // 结点的长度超过总长度就退出
int c1 = 2 * i + 1; // i结点的左孩子结点
int c2 = 2 * i + 2; // i结点的右孩子结点
int max = i; // 先假设i结点的值最大
// 判断左孩子结点小于数组长度并且左孩子的值大于父亲结点，那么更换最大结点索引位置为左节点
if (c1 < n && tree[c1] > tree[max]) {
max = c1;
}
// 判断右孩子结点小于数组长度并且右孩子的值大于父亲结点，那么更换最大结点索引位置为右节点
if (c2 < n && tree[c2] > tree[max]) {
max = c2;
}
// 如果max值和父亲结点不一致，说明孩子结点比父节点大，那么更换两个结点的值，并且重新根据孩子结点的位置进行堆化
if (max != i) {
SortUtils.swap(tree, max, i);
heapify(tree, n, max);
}
}
代码
import java.util.Arrays;
/**
* 堆排序(Heap Sort）
*/
public class Heap {
public static void main(String[] args) {
int[] nums = SortUtils.arrays();
heapSortExam(nums);
System.out.println("堆排序：" + Arrays.toString(nums));
}
public static void heapSort(int[] nums) {
int cLast = nums.length - 1;
int heapifyBeginIndex = cLast - 1 >> 1;
/*
* 第一步：将数组堆化
* beginIndex = 第一个非叶子节点(最后一个叶子结点的父节点) 求父结点公式(i-1)/2 ((n-1)-1)/2
* 从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
* 叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
*/
for (int i = heapifyBeginIndex; i >= 0; i--) {
heapify(nums, nums.length, i);
}
/*
* 第二步：对堆化数据排序
* 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，遍历n-1次，从后面遍历i=n-1大于0，交换两个元素循环次数就是n-1，像冒冒泡排序i=0，<n-1
* 然后重新整理被换到根节点的末尾元素，使其符合堆的特性(堆化 heapify)
* 直至未排序的堆长度为 0。
*/
for (int i = cLast; i >= 0; i--) {
SortUtils.swap(nums, i, 0);
heapify(nums, i, 0);
}
}
/**
* @param tree 要做heapify的数组
* @param n 这个数组的长度
* @param i 要对哪个结点做heapify
*/
public static void heapify(int[] tree, int n, int i) {
if (i >= n) return; // 结点的长度超过总长度就退出
int c1 = 2 * i + 1; // i结点的左孩子结点
int c2 = 2 * i + 2; // i结点的右孩子结点
int max = i; // 先假设i结点的值最大
// 判断左孩子结点小于数组长度并且左孩子的值大于父亲结点，那么更换最大结点索引位置为左节点
if (c1 < n && tree[c1] > tree[max]) {
max = c1;
}
// 判断右孩子结点小于数组长度并且右孩子的值大于父亲结点，那么更换最大结点索引位置为右节点
if (c2 < n && tree[c2] > tree[max]) {
max = c2;
}
// 如果max值和父亲结点不一致，说明孩子结点比父节点大，那么更换两个结点的值，并且重新根据孩子结点的位置进行堆化
if (max != i) {
SortUtils.swap(tree, max, i);
heapify(tree, n, max);
}
}
// ========第二种========
/**
* 堆排序的主要入口方法，共两步。
*/
public static void heapSort2(int[] nums) {
/*
* 第一步：将数组堆化
* beginIndex = 第一个非叶子节点(最后一个叶子结点的父节点) 求父结点公式(i-1)/2 ((n-1)-1)/2
* 从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
* 叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
*/
int lastNode = nums.length - 1;
int beginHeapifyNode = lastNode - 1 >> 1;
for (int i = beginHeapifyNode; i >= 0; i--)
maxHeapify(nums, i, lastNode);
/*
* 第二步：对堆化数据排序
* 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，遍历n-1次，从后面遍历i=n-1大于0，交换两个元素循环次数就是n-1，像冒冒泡排序i=0，<n-1
* 然后重新整理被换到根节点的末尾元素，使其符合堆的特性(堆化 heapify)
* 直至未排序的堆长度为 0。
*/
for (int i = lastNode; i >= 0; i--) {
SortUtils.swap(nums, 0, i);
maxHeapify(nums, 0, i);
}
}
/**
* 调整索引为 index 处的数据，使其符合堆的特性。
*
* @param index 需要堆化处理的数据的索引
* @param len 未排序的堆（数组）的长度
*/
private static void maxHeapify(int[] nums, int index, int len) {
// int li = (index << 1) + 1; // 左子节点索引
// int ri = li + 1; // 右子节点索引
// int max = li; // 子节点值最大索引，默认左子节点。
// if (li > len) return; // 左子节点索引超出计算范围，直接返回。
// if (ri <= len && nums[ri] > nums[li]) // 先判断左右子节点，哪个较大。
// max = ri;
// if (nums[max] > nums[index]) {
// SortUtils.swap(nums, max, index); // 如果父节点被子节点调换，
// maxHeapify(nums, max, len); // 则需要继续判断换下后的父节点是否符合堆的特性。
// }
int left = (index << 1) + 1; // 左子节点
int right = left + 1; // 右子节点
int max = index; // 暂时定在Index的位置就是最大值
// 如果左子节点的值，比当前最大的值大，就把最大值的位置换成左子节点的位置
if (left <= len && nums[left] > nums[max]) {
max = left;
}
// 如果右子节点的值，比当前最大的值大，就把最大值的位置换成右子节点的位置
if (right <= len && nums[right] > nums[max]) {
max = right;
}
// 如果不相等说明，这个子节点的值有比自己大的，位置发生了交换了位置
if (max != index) {
SortUtils.swap(nums, max, index); // 如果父节点被子节点调换，
// 交换完位置后还需要判断子节点是否打破了最大堆的性质。最大堆性质：两个子节点都比父节点小。
maxHeapify(nums, max, len);
}
}
// ======第三种======
public static void sort(int[] nums) {
for (int i = nums.length / 2; i >= 0; i--)
adjustHeap(nums, i, nums.length - 1);
for (int i = nums.length - 1; i >= 0; i--) {
SortUtils.swap(nums, 0, i);
adjustHeap(nums, 0, i - 1);
}
}
public static void adjustHeap(int[] input, int i, int n) {
int child;
for (; i <= n / 2; ) {
child = i * 2;
if (child + 1 <= n && input[child] < input[child + 1])
child += 1;
if (input[i] < input[child]) {
int temp = input[i];
input[i] = input[child];
input[child] = temp;
i = child;
} else
break;
}
}
// ===练习===
public static void heapSortExam(int[] nums) {
// 1. 堆化数组
int last = nums.length - 1;
int beginHeapify = last - 1 >> 1;
for (int i = beginHeapify; i >= 0; --i) {
heapifyExam(nums, nums.length, i);
}
// 2. 把最大值移到最后
for (int i = last; i >= 0; --i) {
SortUtils.swap(nums, i, 0);
heapifyExam(nums, i, 0);
}
}
public static void heapifyExam(int[] nums, int n, int i) {
if (i >= n) return;
int c1 = (i << 1) + 1;
int c2 = c1 + 1;
int max = i;
if (c1 < n && nums[c1] > nums[max]) {
max = c1;
}
if (c2 < n && nums[c2] > nums[max]) {
max = c2;
}
if (max != i) {
SortUtils.swap(nums, max, i);
heapify(nums, n, max);
}
}
}
资料
https://mp.weixin.qq.com/s/JIwmkT52G2A1PajLWijiuA