【前言】：
看了左神的很多视频，感觉一些算法最好的复现方式应该是用一张张的图来细节刻画，个人感觉这种效果会比动态图要好。
故在此先将全部的笔记附到这里，后续在一点一点把过程图复原完整（暂时没研究手绘软件）。
【1】: 快排遗留
【空间复杂度】：
【快排的额外空间复杂度】：
本质上也是在求一个累加；
// 如图最差的情况，空间复杂度为 O（ N ）
【二叉树展开，空间复杂度为log N】：
因为左侧申请的空间递归结束后，可以提供给右侧使用；
//左图即为——二叉树展开；
//改成迭代的话，需要我们自己压栈；
【最终快排v3空间复杂度】：
和时间复杂度一样，求每种情况出现的概率累加， 数学上的长期期望为——O（ log N ）
【2】：完全二叉树
【完全二叉树】：
//上述三张图片，都叫做完全二叉树～～～！！！
【非完全二叉树】：
如果跳过左侧节点，直接在右侧生出枝干，这就不是完全二叉树；
【下图就不是完全二叉树】：
//跳过了左侧节点～～～！！！
//没有从左往右依次变满～～～！！！
【完全二叉树 与 数组】：
你把数组从 0 出发的连续一段儿，可以对应成完全二叉树；
// size=7 ; 表示从0出发连续七个位置作为完全二叉树的节点；——即：连续的一段可以用size来描述。
【完全二叉树的理解】：
【 i位置的孩子公式 】：
有了这三个公式的话，我们就能够把数组中的 《 从0出发连续的一段 》 脑补成一颗完全二叉树～～～！！！
【3】：堆结构
【堆的逻辑概念】：
//堆在逻辑概念上是——完全二叉树。
【堆】：
堆是一个特殊的完全二叉树；堆在逻辑概念上，其实是一颗完全二叉树结构；
【左神原话】：（对堆这一数据结构的经典解释！！！）
首先堆必须是一棵完全二叉树，其次堆分为大根堆 和 小根堆。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iUaTWT8N-1663993283147)(/Users/yuguangyao/Library/Application Support/typora-user-images/image-20220416173151054.png)]
【大根堆】：
每一个头节点都是其子树上的最大值；
// 左图即为一个大根堆～ ～ ～！ ！ ！
// 6 是其两颗子树上的最大数；
// 5 是其两颗子树上的最大数；
// 4 是其两颗子树上的最大数；
。。。所有节点都是其两颗子树上的最大数——此即大根堆。
【小根堆】：
。。。所有节点都是其两颗子树上的最小数——此即小根堆。
【 完全二叉树 调整成 堆 】：
//视频中演示的是——用户不断给我数字，得不停地调整堆的结构。
【堆与数组】：
理解了完全二叉树的形状之后，实际的结构如何实现呢？——借助数组。（从0出发的一段儿，可以对应成完全二叉树。）
如何把数组连续出发的一段儿，搞成一个堆呢？
假设：
? 堆外面有一个接口，用户可以通过这个接口，依次给我一些数字，我把这些数字依次放到我准备好的干净的数组上，然后我怎么样让每一个用户进来的数字，整体形成一个大根堆呢？
【规律】：
新加进来的数会一直和父比较，如果一直比父节点的数要大，就一直交换，一路往上窜，直到比较失败为止。
来到了头节点位置 / 比较失败。
【 heapInsert 】：
从一个位置出发，往上动的过程称之为heapInsert。
//某个数现在处在index位置 ， 往上继续移动。
【调整堆结构】：
【用户的需求】：
问题（1）——直接返回堆的头节点即可～～～
//用户想让我提供一种操作～～～
【大根堆堆化过程】：
【heapify】：
从一个位置出发，往下动的过程称之为heapify （ 堆化 ）。
【大根堆堆化示例】：
【堆结构最重要的操作】：
这是最重要的两个操作 ， 其余的操作都是从这两种操作演变而来～～～
【 用户的新操作 】：
如果将某堆中的数字a变成未知数X , 那么你还能保持此时的有效区域仍然还是堆数据结构呢？？？
【复杂度】：
//用户新加一个数字，调整代价是logN级别的；heapInsert只关心我的父的路径，所以只走一个高度，所以用户新加一个数字的时候，调整代价即是logN。
//用户删掉最大值 ， 并将剩下的数调整成堆——代价也是LogN级别。
【 完全二叉树的高度 】：
【4】：堆排序
【堆排序本质】：
周而复始 ， 当heapSize减至0时 ， 这个数组便排好序了，即——不断地将最大的数往后放，并移出堆区。
【 用户新要求 】：
之前是用户一个一个给你数字，现在要求——用户一口气提供一个数组，直接搞成大根堆。
[ 时间复杂度 ]:
O（ N*logN ）
[ 额外空间复杂度 ]:
O( 1 )
【 分析时间复杂度 】：
【5】：堆排序扩展
【优先级队列】：
优先级队列结构，就是堆结构。
起名虽然叫做优先级队列 ， 但是其底层就是堆结构。——通常堆顶是优先级最大的～～～！！！
【核心】：
堆排序的地位远远没有堆结构重要！！！
【堆排序扩展题目】：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-npjy6meQ-1663993283148)(/Users/yuguangyao/Library/Application Support/typora-user-images/image-20220613220227745.png)]
【JAVA中的小根堆】：
//优先级队列的意思；
【6】：堆扩容
【堆扩容】：
既然底层是用数组做的我堆结构的实际结构，我虽然可以用heapSize来规定堆的有效范围，但是如果一直添加数字的话，这个数组一定有耗尽的时候；
扩容时：需要将原数组所有内容全部都拷贝到新数组中；
单次扩容的代价是 O（ N ）；
一个数组一共从头开始加了N个数的话，需要扩容 （ log N ）次；
【 堆扩容时间复杂度 】：
【何时需要手写堆？？？】：
需要细腻调整堆结构时，必须手写堆；
//系统堆不是不能完成这种功能，而是不会做到高效；
【系统堆】：
【与系统堆交流的唯一方式】：
//你给它一个，它给你一个（唯一交流方式）。
【系统堆所不支持】：
已经形成了堆结构，自己人为的变动某些节点，然后又想以很轻的代价重新调整成堆结构 ， 这对于系统堆来说 ， 是无法完成的。
【手写堆优势】：
如果某一个节点变了，我可以只针对这一个节点看是否需要——heapIfy / heapInsert .
【7】：比较器
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FSHubZVJ-1663993283148)(/Users/yuguangyao/Library/Application Support/typora-user-images/image-20220818151941943.png)]
【 比较的核心 】：
【 正 】—— 二参置前
【 负 】—— 一参置前
【复杂的比较策略】：
【 J a v a中的大根堆 】：
new PriorityQueue<>(new IdAscendingComparator())
【8】：桶排序
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rsCiCike-1663993283148)(/Users/yuguangyao/Library/Application Support/typora-user-images/image-20220818155815241.png)]
【词频排序】：
词频排序——又称：计数排序。
【年龄例子】：
数组里存放的是人的年龄，因为是年龄，所以可以认为数据状况是——（ 0～200 ）
【词频排序的弊端】：
如果数组中元素过大，上万位，那么数组的长度是不可想象的。2^ 31 长度的数组？——词频表直接爆炸～ ～ ～
【总结】：
不基于比较的排序 ， 全是根据数据状况作的排序 ；
【 基数排序 】：
【 分析 】：
因为高位数字是晚排序的，所以其优先级最高～ ～ ～
【桶的概念】：
桶就是容器的意思，桶的具体结构可以是队列，可以是数组，可以是栈，什么都行～
//在这里我们认为桶的结构是队列。
【 桶的个数 】：
比数组好太多，比计数排序好太多。
如果是十进制，搞十个桶即可。三进制，搞三个桶即可。
但桶排序依然和数据状况挂钩：
? 数据必须要有进制这个玩意儿～ ～ ～
【进出桶的次数】：
完全是由数组中最大值的位数决定～ ～ ～
最大值的位数为N。 <==> 所有数字进出桶的次数。
100 ----> 3次；
1000 ----> 4次；
10000 ----> 5次；
【9】：前缀和数组思想
[ 分片儿 ]:
我们利用这个count数组，其实可以做到分片儿～～～
原数组从右往左，根据count[] 来输入到 bucket[] 中，实际上就相当于完成了一次入桶 / 出桶；
利用词频表来完成进出桶～～～