前面的堆的介绍，堆有个很重要的性质，堆顶元素始终是所有元素的的最大值或者最小值，借助这个特性，可以实现对数组进行排序

思路：
按照insert的流程，依次将数组元素插入到堆中，本质上就是数组元素的交换，做完这个操作之后，数组就具备了堆的性质
依次将堆顶元素删除，这里的删除指的是将堆顶元素放到未排序的元素的后面，这样，就能保证后面的元素是有序的

1.将数组堆化 heapify，参考 堆中数组堆化的实现，最优的时间复杂度为 $O(n)$

2.依次将堆顶元素和堆的最后一个元素交换，并重新堆化最后一个元素之前的数组（从堆的最后元素开始，数组的后面是有序的）

for size := len(data) - 1; size >= 1; size-- {
    idx := 0
    //将堆顶元素和最后的元素交换顺序，等价于删除堆顶元素，从size 开始的元素是有序的
    data[idx], data[size] = data[size], data[idx]
    for {
        leftIdx := idx<<1 + 1
        rightIdx := leftIdx + 1
        if leftIdx >= size {
            break
        } else if rightIdx >= size {
            if data[leftIdx] < data[idx] {
                data[leftIdx], data[idx] = data[idx], data[leftIdx]
            }
            break
        } else {
            if data[leftIdx] < data[rightIdx] && data[idx] > data[leftIdx] {
                data[leftIdx], data[idx] = data[idx], data[leftIdx]
                idx = leftIdx
            } else if data[rightIdx] < data[leftIdx] && data[idx] > data[rightIdx] {
                data[rightIdx], data[idx] = data[idx], data[rightIdx]
                idx = rightIdx
            } else {
                break
            }
        }
    }
}

排序过程中，只需要申请常数级的临时空间，空间复杂度为 $O(1)$
排序分成两个过程：
1.整个数组堆化
2.依次删除堆顶元素，并堆化

排序的时间复杂度

假设共有n个元素构成的堆，高度为 $H = log_2n$，对于第h（从1开始）层，节点最多是 $2^{h-1}$，每个节点都需要和堆的根节点交换，然后再重新堆化，比较的次数最多为 h次，所有节点的总的比较次数是：

$$\sum_{h=H}^{2}h * 2 ^{h-1} = (\sum_{h=2}^{H}h * 2 ^{h})/2 = (H - 1)*2^{H}$$

化简之后，等于 $n*log_2n - n$，因此时间复杂度是 $O(nlog_2n)$。

堆排序过程中会存在节点数据交换，导致数据位置变化，不是稳定的排序算法。

相对于快速排序，堆排序的优点是性能比较稳定，最坏的情况下的时间复杂度是$O(nlog_2n)$，但性能可能不如快速排序，原因如下：

• 堆排序的数组访问不是连续的，不太符合程序的局部性原理
• 堆化可能会破坏原来已经有序的子序列