前言数据 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.重新调整结构，使其继续满足堆定义
文章插图
经验总结扩展阅读
- 1 python-数据描述与分析
- 红薯的功效与作用
- 创造与魔法最新每日礼包兑换码是多少
- 芽庄沉香的香味与特点
- 蜂蜜的作用与功效减肥的方法
- 企业运维 | MySQL关系型数据库在Docker与Kubernetes容器环境中快速搭建部署主从实践
- 驱动通信：通过PIPE管道与内核层通信
- 横隔板与湿接缝的区别
- 光与夜之恋双十一礼包怎么购买
- 药理学是什么