堆排序是依赖堆的特性完成的排序。

堆分为小顶堆和大顶堆，堆是满二叉树结构且每个节点都是这个节点子树的最大或最小值，这样的结构为堆。根节点大的为大根堆，根节点为小的为小根堆。

堆排序，首先将数组映射成一个堆结构。可以映射成堆结构的原因是：数组的每个位置可以映射到堆的每个节点上。

排序原理：

我们现将数组的每个元素构造成大顶堆，然后逐个将堆顶与堆底交换，然后将堆底从堆中移除，重新维护大顶堆结构。周而复始可以将每个元素排好序。

如下图可以直观的感受数组和堆结构位置的映射关系