目录

• • 一、前言
  • • 1.1、概念
    • 1.2、大根堆特点
  • 二、maven依赖
  • 三、流程解析
  • • 3.1、初始建堆
    • 3.2、堆化第一步
    • 3.2、堆化第二步
    • 3.3、堆化第三步
    • 3.4、堆化第四步
    • 3.5、堆化第五步
    • 3.6、堆化第六步
  • 四、编码实现
  • • 4.1、代码实现
    • 4.2、运行结果：
  • 扩展

一、前言

1.1、概念

  根据堆的结构可以分为大根堆和小根堆，它是一个完全二叉树，先来了解下什么是大根堆和小根堆吧。

• 大根堆：每个结点的值都大于其左孩子和右孩子结点的值，即：arr[i]arr[i]arr[i] > arr[2∗i+1]arr[2*i+1]arr[2∗i+1] && arr[i]arr[i]arr[i] > arr[2∗i+2]arr[2*i+2]arr[2∗i+2]
• 小根堆：每个结点的值都小于其左孩子和右孩子结点的值，即：arr[i]arr[i]arr[i] < arr[2∗i+1]arr[2*i+1]arr[2∗i+1] && arr[i]arr[i]arr[i] < arr[2∗i+2]arr[2*i+2]arr[2∗i+2]

1.2、大根堆特点

  本文主要以大根堆为例，它的特点如下：

• 数组索引为 000 的位置存放堆顶的元素（大根堆根节点就是最大值了）
• 数组索引为 iii 的元素的左右叶子节点的索引分别是2∗i+12 * i + 12∗i+1 和 2∗i+22 * i + 22∗i+2
• 数组索引为 iii 的元素的父节点的下标索引为i−12\frac{i-1}{2}2i−1​

二、maven依赖

pom.xml

org.springframework.bootspring-boot-starter2.6.0org.projectlomboklombok1.16.14

三、流程解析

3.1、初始建堆

  先把我们数组的元素转化为大根堆。

• 数组索引为 iii 的元素的左右叶子节点的索引分别是2∗i+12 * i + 12∗i+1 和 2∗i+22 * i + 22∗i+2，我们可以把数组转化为图1的树，这个是初始化的数据
• 图1中最后一个父节点是101010，它不满足大根堆的条件，因为它的子节点的值191919比它大，所以我们交换他们的值得到图2，当前的节点就满足大根堆了，然后继续下一个节点
• 往前继续找到父节点888（也就是从最右的父节点一直往前遍历），它不满足大根堆的条件，因为它的子节点的值232323比它大，所以交换 888 和 232323 得到图3，然后继续下一个节点
• 下一父节点是282828，它的值比两个子节点的值都大，已经满足大根堆的条件了，建堆完成

3.2、堆化第一步

  我们这一步是接着上面建堆的结果的，也就是以图3为基础变化的。

• 通过上一步建堆时我们已经得到了大根堆了，也就是图3，我们把大根堆的值和最右未排序的子节点进行交换，也就是 282828 和 999 得到图4，则 282828 就是排序完成的数据
• 从图4中知道，排除排序好的节点（282828）来看，191919 和 232323 满足大根堆，不用变化，但是根节点9不满足，因为它比它最大子节点232323小，所以交换 999 和 232323 得到图5
• 交换后的节点999还是不满足大根堆条件，因为它比最大子节点 212121小，所以交换 999 和 212121 得到图6，999 已经没有子节点了，建堆完成

3.2、堆化第二步

  我们这一步是接着上面建堆的结果的，也就是以图6为基础变化的。

• 上一步建堆时我们已经得到了大根堆了，我们把大根堆的值和最右未排序的子节点进行交换，也就是 232323 和 101010 得到图7，则 232323 就是排序完成的数据
• 从图7中知道，排除排序好的节点（232323、282828）来看，191919 和 212121 满足大根堆，不用变化，但是根节点101010不满足，因为它比它最大子节点212121小，所以交换 101010 和 212121 得到图8
• 图8中，交换后的节点101010已经满足大根堆的条件了，建堆完成

3.3、堆化第三步

  我们这一步是接着上面建堆的结果的，也就是以图8为基础变化的。

• 上一步建堆时我们已经得到了大根堆了，我们把大根堆的值和最右未排序的子节点进行交换，也就是212121和999得到图9，则 212121 就是排序完成的数据
• 从图9中知道，排除排序好的的节点（212121、232323、282828）来看，191919 和 101010 满足大根堆，不用变化，但是根节点999不满足，因为它比它最大子节点191919小，所以交换 999 和 191919 得到图10
• 图10中，交换后的节点999（除去排序完成的没有子节点了）已经满足大根堆的条件了，建堆完成

3.4、堆化第四步

  我们这一步是接着上面建堆的结果的，也就是以图10为基础变化的。

• 上一步建堆时我们已经得到了大根堆了，我们把大根堆的值和最右未排序的子节点进行交换，也就是191919和888得到图11，则 191919 就是排序完成的数据
• 从图11中知道，排除排序好的的节点（191919、212121、232323、282828）来看，999 和 101010 满足大根堆，不用变化，但是根节点888不满足，因为它比它最大子节点101010小，所以交换 888 和 101010 得到图12
• 图12中，交换后的节点888（除去排序完成的没有子节点了）已经满足大根堆的条件了，建堆完成

3.5、堆化第五步

  我们这一步是接着上面建堆的结果的，也就是以图12为基础变化的。

• 上一步建堆时我们已经得到了大根堆了，我们把大根堆的值和最右未排序的子节点进行交换，也就是 101010 和 999 得到图13，则 101010 就是排序完成的数据
• 从图13中知道，排除排序好的的节点（101010、191919、212121、232323、282828）来看，交换后的节点888（除去排序完成的没有子节点了）已经满足大根堆的条件了
• 最后结果就是图14，节点都已经满足大根堆的条件了，建堆完成

3.6、堆化第六步

  我们这一步是接着上面建堆的结果的，也就是以图14为基础变化的。

• 上一步建堆时我们已经得到了大根堆了，我们把大根堆的值和最右未排序的子节点进行交换，也就是 999 和 888 得到图15，则 999 就是排序完成的数据
• 从图15中知道，排除排序好的的节点（999、101010、191919、212121、232323、282828）来看，只有一个根节点节点888了，也就是图16，不用比较了，最后的结果就是全部排序完的图17，到此我们的排序就完成了

四、编码实现

4.1、代码实现

public static void heapSort(int[] arr) {// 获取数组长度int length = arr.length;// 数组索引为 i 的元素的父节点的下标索引为：i-1/2 得到// 因为下标从0开始，最后一个子节点（length-1）减去1再除以2得到父节点（length-1-1）/2=length / 2 - 1// 我们从最后一个父节点开始遍历直到根节点（父节点会和子节点进行比较的）for (int i = length / 2 - 1; i >= 0; i--) {// 把数组转化为堆，我们称之为建堆buildHeap(arr, i, length);}log.info("数组建堆后的结果：{}", arr);// 排序，因为之前已经完成了建堆，意味着，根节点就是我们需要的值for (int i = length - 1; i >= 0; i--) {// 将当前根节点与未排序的最大子节点进行交换swap(arr, 0, i);// 剩下的元素继续建堆,要理解i--,刚刚交换的根节点的值就是已排序的不会参与遍历了buildHeap(arr, 0, i);}
}private static void buildHeap(int[] arr, int i, int length) {// 大顶堆的节点调整while (true) {// 定义最大节点的位置int maxPos = i;// 检查在未排序列表中，当前节点的值是不是小于它的左子节点(2i+1)if (i * 2 + 1 < length && arr[i] < arr[i * 2 + 1]) {maxPos = i * 2 + 1;}// 检查在未排序列表中，同时当前的最大节点和i节点的右子节点（2i+2）也比较找出最大值的节点// 也就是找出父节点，左节点，右节点三者中的最大节点值if (i * 2 + 2 < length && arr[maxPos] < arr[i * 2 + 2]) {maxPos = i * 2 + 2;}// maxPos没变说明已经找不到比当前节点大的了if (maxPos == i) {break;}// 交换两个节点（当前节点和最大值的节点进行交换）// 这里就是父节点和子节点中那个较大的节点进行交换swap(arr, i, maxPos);// 继续往下处理这个过程（）也就是继续处理最大节点，看它是否满足大根堆的条件（比它的子节点都大）i = maxPos;}log.info("大顶堆的节点调整后结果：{}", arr);
}private static void swap(int[] arr, int i, int j) {log.info("交换数据：{}和{}交换", arr[i], arr[j]);int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}public static void main(String[] args) {int[] arr = new int[]{28, 8, 10, 23, 21, 19, 9};log.info("要排序的初始化数据：{}", arr);//从小到大排序heapSort(arr);
}

  一定要结合本地第一节的概念和特点去看代码，才会事半功倍。

4.2、运行结果：

要排序的初始化数据：[28, 8, 10, 23, 21, 19, 9]
交换数据：10和19交换
大顶堆的节点调整后结果：[28, 8, 19, 23, 21, 10, 9]
交换数据：8和23交换
大顶堆的节点调整后结果：[28, 23, 19, 8, 21, 10, 9]
大顶堆的节点调整后结果：[28, 23, 19, 8, 21, 10, 9]
数组建堆后的结果：[28, 23, 19, 8, 21, 10, 9]
交换数据：28和9交换
交换数据：9和23交换
交换数据：9和21交换
大顶堆的节点调整后结果：[23, 21, 19, 8, 9, 10, 28]
交换数据：23和10交换
交换数据：10和21交换
大顶堆的节点调整后结果：[21, 10, 19, 8, 9, 23, 28]
交换数据：21和9交换
交换数据：9和19交换
大顶堆的节点调整后结果：[19, 10, 9, 8, 21, 23, 28]
交换数据：19和8交换
交换数据：8和10交换
大顶堆的节点调整后结果：[10, 8, 9, 19, 21, 23, 28]
交换数据：10和9交换
大顶堆的节点调整后结果：[9, 8, 10, 19, 21, 23, 28]
交换数据：9和8交换
大顶堆的节点调整后结果：[8, 9, 10, 19, 21, 23, 28]
交换数据：8和8交换
大顶堆的节点调整后结果：[8, 9, 10, 19, 21, 23, 28]

扩展

  实际在我们的数据结构中，有一种队列采用的也是堆排序，那就是PriorityQueue（优先队列），大家可以作一个了解。

package com.alian.algorithm.sort;import lombok.extern.slf4j.Slf4j;import java.util.Iterator;
import java.util.PriorityQueue;@Slf4j
public class HeapSort {public static void heapSort(int[] arr) {PriorityQueue queue = new PriorityQueue<>();for (int value : arr) {queue.offer(value);}Iterator iterator = queue.iterator();while (iterator.hasNext()) {log.info("排序后的数据：{}", queue.poll());}}public static void main(String[] args) {int[] arr = new int[]{28, 8, 10, 23, 21, 19, 9};log.info("要排序的初始化数据：{}", arr);//从小到大排序heapSort(arr);}
}

运行结果：

要排序的初始化数据：[28, 8, 10, 23, 21, 19, 9]
排序后的数据：8
排序后的数据：9
排序后的数据：10
排序后的数据：19
排序后的数据：21
排序后的数据：23
排序后的数据：28