如何借鉴完全二叉树特性，快速实现堆排序算法？

本文共计1833个文字，预计阅读时间需要8分钟。

前言：什么是堆+堆是一种数据结构，它是完全二叉树或近似完全二叉树的一种数据结构，其中树中每个节点的值都不小于（或不大于）其左右子节点的值。+完全二叉树：完全二叉树是指除了最底层外，每一层都被完全填满的二叉树。+完全二叉树是堆

前言

什么是堆

堆是一种数据结构，它是完全二叉树或者是近似完全二叉树的一种数据结构，树中每个结点的值都不小于(或不大于)其左右孩子结点的值。

何为完全二叉树

完全二叉树是一种特殊的二叉树，完全二叉树是除了最后一层之外的其他每一场层都被完全填充，叶子节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树，也就是说所有节点都保持向左对齐。如果想了解更多关于二叉树的介绍，可参考之前写的一篇文章《​​手把手带你快速实现自定义二叉树​​》

对完全二叉树来说，较为简洁的实现方法就是使用数组来存储完全二叉树。这样结点就按层序存储于数组中，其中第一个结点将存储于数组中的1号位，并且数组i号位表示的结点的左孩子就是2i号位，而右孩子则是(2i+1)号位。

什么是堆排序

堆排序与快速排序，归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法，堆排序是将数据看成完全二叉树，然后根据完全二叉树的特性来进行排序的一种排序算法，这有点草船借箭的妙用。正所谓他山之，石可以攻玉。