（二叉）堆是一个数组，它可以被看成是一个近似的完全二叉树。
完全二叉树:一棵二叉树中，只有最下面两层结点的度可以小于 2，并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树
二叉堆可以分为最大堆和最小堆：
- 最大堆：除了根以外的所有节点 i 都要满足 A[PARENT(i)]>=A[i],也就是说某个节点的值至多与其父节点一样大,堆中最大元素存放在根节点中
- 最小堆：除了根以外的所有节点 i 都要满足 A[PARENT(i)]<=A[i],最小堆中最小的元素存放在根节点中
MAX-HEAPIFY 通过让 A[i] 的值在最大堆中下沉，从而使得以下标 i 为根节点的子树重新遵循最大堆的性质。
该操作是按照堆的结构逐层下沉，最复杂的情况是从根节点逐层下沉到叶节点，所以该操作的时间复杂度主要取决于堆的高度，复杂度为 O(lgn)
我们可以用自底向上的方法利用过程 MAX-HEAPIFY 把数组转换为最大堆。
当 i>A.length/2 时，都是叶节点，叶节点只有一个节点没有建最大堆的必要
如果 i 从 1 遍历至 A.length/2 ，那么有可能导致创建的堆不满足最大堆的性质，使得根节点不是数组中最大的值。
例如考虑数组:[24,15,7,5,43,87,34]，如果从根节点开始遍历，那么数组最大值 87 无法通过建堆操作移动至根节点，如下所示：
初始的时候，堆排序算法利用建堆操作将数组建成最大堆，因为数组中的最大元素总在根节点中，通过把它与 A[n] 进行交换，我们可以让该元素放到正确的位置。
每次循环，通过交换最大值的方式，可以将数组最大值，第二个最大值...第 n 最大值依次放到正确的位置。
堆排序算法的核心就是交换最大值，所以该算法每次循环都能确定好一个第 n 个最大值的位置。
O(nlgn)
因为每次调用建堆 BUILD-MAX-HEAP 操作的时间复杂度是 O(n)，维护堆性质的操作 MAX-HEAPIFY 的时间复杂度为 O(lgn)，所以总的复杂度为 O(nlgn)
不稳定
堆排序算法无法判断数组是否已经排序好，所以当数组已经排序好时，堆排序还是会继续执行，例如数组[1,1,1,1]，堆排序无法知晓数组是否需要排序，所以依然会交换相等的元素，从这个角度看堆排序是不稳定排序。
其次，堆排序交换元素不是基于相邻元素交换的算法，所以对于相等元素之间的相对位置无法做到控制。例如，反过来考虑冒泡排序，针对于数组 [5,2,5]，当数组交换 5，2 后变成 【2，5，5】,这时通过比较 5，5 即可确定不需要交换元素。 堆排序不是基于相邻元素比较的算法，所以当数组中存在 5,5 相等元素时，可能第一个 5 在堆的左分支中，第二个 5 在堆的右分支中，两个相等元素交换相对位置是有可能的。
// 堆排序-算法导论版本
type HeapSortAlgorithms struct {
Value []int
}
func (s *HeapSortAlgorithms) Sort() ([]int, error) {
s.buildMaxHeap()
for i := len(s.Value) - 1; i > 0; i-- {
s.Value[i], s.Value[0] = s.Value[0], s.Value[i]
s.maxHeapify(0, i)
}
return s.Value, nil
}
func (s *HeapSortAlgorithms) maxHeapify(t, len int) {
if t >= len {
return
}
largest, left, right := t, Left(t), Right(t)
if left < len && s.Value[left] > s.Value[largest] {
largest = left
}
if right < len && s.Value[right] > s.Value[largest] {
largest = right
}
if largest != t {
s.Value[t], s.Value[largest] = s.Value[largest], s.Value[t]
s.maxHeapify(largest, len)
}
}
func (s *HeapSortAlgorithms) buildMaxHeap() {
for i := len(s.Value)/2 - 1; i >= 0; i-- {
s.maxHeapify(i, len(s.Value))
}
}
func Left(t int) int {
return 2*t + 1
}
func Right(t int) int {
return 2*t + 2
}