前言数据 data 结构(structure)是一门 研究组织数据方式的学科 ， 有了编程语言也就有了数据结构.学好数据结构才可以编写出更加漂亮,更加有效率的代码 。
- 要学习好数据结构就要多多考虑如何将生活中遇到的问题,用程序去实现解决.
- 程序 = 数据结构 + 算法
- 数据结构是算法的基础, 换言之，想要学好算法，需要把数据结构学到位
注：数据结构与算法【Java】这一系列的博客参考于B站尚硅谷的视频，视频原地址为【尚硅谷】数据结构与算法（Java数据结构与算法）上一篇文章数据结构与算法【Java】07---树结构基础部分
1、堆排序1.1、堆排序简介? 1.堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏 ， 最好，平均时间复杂度均为
O(nlogn)，它是不稳定排序 。- 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大根堆（或大顶堆）, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系 。
- 每个结点的值都小于或等于其左右孩子结点的值 ， 称为小根堆（或小顶堆）
- 一般升序采用大根堆，降序采用小根堆
文章插图
文章插图
1.2、堆排序过程演示
堆排序的基本思想是：
- 将待排序序列构造成一个大根堆
- 此时，整个序列的最大值就是堆顶的根节点 。
- 将其与末尾元素进行交换，此时末尾就为最大值 。
- 然后将剩余 n-1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值 。如此反复执行，便能得到一个有序序列了 。
步骤图解要求：给你一个数组 {4,6,8,5,9} , 要求使用堆排序法，将数组升序排序 。
- 步骤一 构造初始堆 。将给定无序序列构造成一个大根堆（一般升序采用大根堆，降序采用小根堆) 。
- 原始的数组 [4, 6, 8, 5, 9]
- 假设给定无序序列结构如下
文章插图
- 此时我们从最后一个非叶子结点开始（叶结点自然不用调整 ， 第一个非叶子结点
arr.length/2-1=5/2-1=1， 也就是下面的 6 结点） ， 从左至右 ， 从下至上进行调整 。
文章插图
3.找到第二个非叶节点 4，由于[4,9,8]中 9 元素最大 ， 4 和 9 交换 。
文章插图
4.这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中 6 最大，交换 4 和 6 。
文章插图
此时，我们就将一个无序序列构造成了一个大顶堆.
- 步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大 。然后继续调整堆，再将堆顶元素与末尾元素交换得到第二大元素 。如此反复进行交换、重建、交换
文章插图
2.重新调整结构，使其继续满足堆定义
文章插图
3.再将堆顶元素 8 与末尾元素 5 进行交换 ， 得到第二大元素 8
文章插图
4.后续过程，继续进行调整，交换 ， 如此反复进行，最终使得整个序列有序
文章插图
再简单总结下堆排序的基本思路：1).将无序序列构建成一个堆，根据升序降序需求选择大根堆或小根堆;2).将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素 ， 反复执行调整+交换步骤，直到整个序列有序
动态演示
推荐阅读
![教你如何使用迅雷离线下载[新发布]](http://img.zhejianglong.com/220413/032F04306-0-lp.jpg)
- 1 python-数据描述与分析
- 创造与魔法最新每日礼包兑换码是多少
- 企业运维 | MySQL关系型数据库在Docker与Kubernetes容器环境中快速搭建部署主从实践
- 驱动通信：通过PIPE管道与内核层通信
- 光与夜之恋双十一礼包怎么购买
- MES系统与ERP系统信息集成有哪些原则？
- 企业MES系统与ERP信息集成要素有哪些？
- 光与夜之恋钜惠嘉年华怎么买划算
- 补充部分---ScheduledThreadPoolExecutor类分析 线程池底层原理详解与源码分析
- 驱动开发：通过ReadFile与内核层通信