堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于(或者大于)它的父节点。在堆的数据结构中，堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作：

1.最大堆调整(Max Heapify)：将堆的末端子节点作调整，使得子节点永远小于父节点

2.创建最大堆(Build Max Heap)：将堆中的所有数据重新排序

3.堆排序(HeapSort)：移除位在第一个数据的根节点，并做最大堆调整的递归运算

堆排序的过程是什么?

1.根据拿到的数组构建大顶堆/小顶堆;

2.从堆顶取走元素，放到其应该存在的位置中去。从堆底拿到堆中最后一个元素，放到堆顶，此时这个堆很可能不再合法也就是说不再是一个堆;

3.维护这个堆，通过自己写的方法调整堆中节点结构，让它重新变成一个堆;

4.重复2,3过程，直到堆被取空，此时数组也被完全排列好;我们可以发现堆排序并没有面向我们如何对于这个数组进行数值比较，如何排序，它的思路和其他的排序方式很不同，它是面向了一个堆的维护，而不是把重心放到了数组的排列上。在堆排序中，最为耗费时间的时候就是堆的构建，一旦这个堆被构建好之后，从堆顶取元素，从堆底拿元素的行为就不会让这个堆变得特别无序，也就是说它肯定是比以前没有被构建的时候有序的多，因此再维护起来，时间复杂度就会小很多，每次维护可能只会移动几个节点，因而效率就能够得到提升。接下来我们进行堆排序的图解以及代码分析。