Heap Sort

大顶堆，小顶堆

  1. 初始化堆，从下向上，开始位置为n/2-1，因为二叉树最后1个有子节点的节点的index为n/2-1

  2. 交换root位置(当前最大值) 和 最后1个位置的值， 每1次操作，相当于将当前最大值放到待排序数组对应位置；

交换后，需要调整。因为数组最后1个值被放到了root位置，它与左右节点的大小未知，需要调整；调整后带来的连带反应也会导致子树的root 和 左右节点大小关系位置，也需要调整。 和初始化堆不同，在这的调整，是从上到下调整

  1. 重复2的过程，直到数组中所有元素排序成功

左: root2+1
右: root2+2

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容