堆排序
假设我们要对一个数组从小到大进行排序，首先我们可以将原数组中的数据建立成一个大顶堆。这样，最大的元素就会在数组的首位。正常情况下，从堆中删除一个元素，是直接将堆顶元素弹出，然后将堆中最后一位的元素放到堆顶，再做向下调整的。这样的话，原来堆中的末尾元素位置就空了出来。
现在，由于要对原数组进行排序，因此我们可以把弹出的堆顶元素与堆中的末尾元素进行位置交换，再向下做调整。也就是将图中的元素 9 和 4 做调换，再对 4 做向下调整。经过一轮这样的操作，我们就可以将一个堆顶的最大值放到正确的排序位置上。我在下图中给出了三轮操作以后，数组中元素的排序情况：
经过三轮弹出大顶堆顶元素的操作以后，原数组中最大的三个值就被放置到了最后三位。当大顶堆中元素弹空时，也就完成了对原数组排序的过程。
堆排序的流程
- 在原数组上建立堆结构
- 将堆顶元素与堆末元素进行调换，再对堆顶元素进行向下调整
- 经过 n 轮操作以后，数组中的元素就有序了
对于第 1 步，如果想在一个数组上建立一个堆结构，我们要怎么做呢？
一种最直接的方式，就是我们先将原数组分成两部分，前半部分是堆，后半部分是数组中的元素。然后通过堆的向上调整策略，我们依次将后面的元素插入到前面的堆结构中。下图展示的就是用这种尾插法建堆的前三轮数组中的元素情况：
一种最直接的方式，就是我们先将原数组分成两部分，前半部分是堆，后半部分是数组中的元素。然后通过堆的向上调整策略，我们依次将后面的元素插入到前面的堆结构中。下图展示的就是用这种尾插法建堆的前三轮数组中的元素情况：
这种建堆的方法比较直观，所以建堆的时间复杂度我们很容易就可以计算出来，就是 O(nlogn)。
