堆排序
首先介绍一下堆排序属于选择排序的一种类型。
其次就是他有点依赖于顺序存储树判断其孩子以及父节点的概念，接下来复习一下。
堆分为大根堆和小根堆
① 若满⾜：L(i)≥L(2i)且L(i)≥L(2i+1) （1 ≤ i ≤n/2 ）—— ⼤根堆（⼤顶堆）
② 若满⾜：L(i)≤L(2i)且L(i)≤L(2i+1) （1 ≤ i ≤n/2 ）—— ⼩根堆（⼩顶堆）
注意这里的判断条件结合一下前面树的节点判断条件来看。
接下来介绍如何进行堆排序，
在大根堆中堆顶元素的关键字值最大，
。
接下里介绍一下给出一堆数组如何建立大根堆，这里一定注意结合树来理解。
思路：把所有⾮终端结点都检查⼀遍，是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整
在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋
简单来说就是检查数组的前一半元素（采取从后到前的顺序）因为⾮终端结点编号 i≤⌊n/2⌋。检查这一半的非终端节点是否满足大根堆的定义看左右孩子是否都比他小
结合这个例子来看，你会发现一般的元素就是从下标4 开始算起，接下来就开始检查9会发现左子树大于根所以需要交换位置（包含数组中的位置，可以考虑采用swap来进行元素的交换。），如图所示
接下来该检查78了，会发现87比它大。所以需要交换元素。处理完同时扫描下一个元素也就是17。
扫描17发现左右孩子都比它大就需要选取最大的一个了这样才能满足大根堆的定义。
处理如下。
接着再处理53
53的处理有点特殊
53交换元素后还是不满足定义，这时就需要再一次的下坠。
此时得到一个大根堆的树形
接下来我们看一下代码的实现以及解析
从上往下看，首先设置i为二分之length同时
因为为了方便操作第一个元素也就是数组0元素不存储数据。然后调用
函数
接下来解析函数
首先设置数组0用来临时存储根节点，然后借用一个循环
注意这里的传参上一个函数传过来的i值（也就是用来算非终端节点的i）在本函数中用K来表示了，具体的比较函数的定义
理解了K然后我们继续看循环，循环体重新设置了一个变量i等于2k用来找到孩子节点，同时注意i要小于数组长度否则没有意义可能程序还会被脏数据污染。循环条件是
可以看为i=i*2
接下来进入循环体，
这一步是用来选取子节点里面较大的那个节点，如果
大，那么就让i+1也就是孩子中大的那个的下标。如果没有就说明时i大那就保持原本的。
如果
也就是暂存的元素（此时涉及到的非终端节点）大那就不需要交换位置此时这一棵子树满足大根堆的定义就可以直接跳出 循环执行
也就是原来的位置处
如果不满足
也就是孩子大那就将孩子调整到K的位置然后修改K值再一次执行
此时注意循环条件
，再一次检查调整过后是否还需要下坠才满足大根堆的条件直到
即跳出来数组，此时这个判断条件说明这个节点已经不能下坠了此时的节点一定是终端节点也就是叶子节点依据
来判断的，如果是这样的话也直接执行
，即将叶子节点的值设为暂存的元素值，因为它实在太小了，只能不断地下坠到达叶子节点。具体的看一下接下来53的过程.
同时改该函数里面的i值判断接下来的值是否符合标准。
再一次执行此时溢出数组了，结束循环。
上面的代码是建立大根堆，接下里我们介绍基于大根堆实现完整的排序
接下来看一下堆排序的完整代码。
接下来的才是完整堆排序的思想
堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（与待排序序列中的最后⼀个元素交换）
并将待排序元素序列再次调整为⼤根堆（⼩元素不断“下坠”）
第一步交换9 和87
然后新的大根堆需要length-1以方便重新排堆（让87直接输出到数组末尾同时重新拍大根堆不算87）
调整如下
再一次首元素和末尾元素
然后再一次调整剩下的元素的大根堆同时新大根堆的调整长度需要减1.
再次断开一个元素，再次调整大根堆剩下操作如此往复即可
n-1趟 处理之后：
接下来我们整合调整过程
注意一下完整逻辑的代码
这里第一步是建立了一个堆应该是如下图所示的
此时定义i让他指向最后一个元素用于交换首尾元素同时要实现上面断掉元素的过程让i--,进入循环交换首位元素然后调整大根堆，此时注意一下传入参数的信息。
调整数组A以下标为1的根堆长度为i-1。再然后循环起来i--再一次交换元素，然后再一次调整，实现之前说过的调整趟数的过程，最后得出升序排序。
堆的插入删除
首先声明一下，减轻一下心里负担的压力，堆的删除插入只要求弄懂手算过程没有代码，但是要求学会计算对比次数。
这里以小根堆为例演示一下
插入
插入13
注意小根堆规则，根要小于孩子。注意元素的上升，
1.首先对比，32和13发现13小然后就上升13
2.然后对比13和17，发现13需要上升
3.再次对比13和9，发现现在不需要上升了。
此时共发生了三次关键字的对比。
接下来插入一下46
发现只需要1次对比它不会上升。
接下来看一下删除的操作
删除
被删除的元素⽤堆底元素替代，然后让该
元素不断“下坠”，直到⽆法下坠为⽌
元素被删除了就会采用堆底的元素来代替。这里删除13可以选取46来做代替，选取代替元素的规则（要求拆掉元素以后满足二叉树的定义所以只能拆掉46），
拆掉46以后还得让其满足小根堆的要求先需要对比孩子里面小的值，然后拿孩子里面小的值来和根对比
第一次17和45比较；第二次17和46比较下沉46；第三次52和32比较；第四次比较46和32下沉46
总共对比了4次注意若下方就一个孩子则下坠只涉及到一次对比就没有孩子间的那次对比了。
接下来删除65试试
为了符合二叉树的规则只能借用46
第一次对比78和87，第二次对比78和46，对比结束
接下来总结一下
