106，排序-堆排序

这一部分来分析一下堆排序，也可以理解为二叉树排序，这里的堆分为两种，一种是大顶堆，一种是小顶堆，我们所有的排序方法都以升序为主，其实倒序原理也都差不多，所以这里我们主要分析的是大顶堆。大顶堆就是根节点不小于他的两个子节点，先看一下代码

上面代码中heapSort方法表示对数组进行排序，buildMaxHeap表示堆的构建，maxHeapfy表示堆的调整，包括每次截取数据的时候也都需要调整，截取数据就相当于把root节点截取，然后用最后的一个节点替换到root的位置，然后再进行调整。看代码可能不是很直观，下面看一下图有助于理解

这是堆的构建的过程，其实也就是代码中的buildMaxHeap方法执行的过程，下面再来看一下是怎么排序的。

其实就是每次截取root节点然后存放到数组中，存放数组的位置是从后往前，然后把最后一个节点截取放到原来的root节点的位置，因为最后一个节点放到root节点，打破了二叉树的平衡，所以要从root节点开始进行调整。然后通过不断的循环不断的截取不断的再调整，直到截取完为止。

关注，点赞，评论，转发