堆排序是怎样实现的？为什么一般应用很少用它？
先自己想一想，再看参考要点
参考要点
- 堆是一棵完全二叉树，大顶堆中每个节点都不小于它的子节点，可以存放在数组中，下标从 1 开始时位置 k 的子节点是 2k 和 2k+1、父节点是 k/2
- 节点比父节点大时不断和父节点交换叫上浮，比子节点小时不断和较大的子节点交换叫下沉
- 建堆时从右往左对一半的元素做下沉（叶子节点不用），这种方法是线性的，少于 2N 次比较
- 排序时把堆顶的最大元素和堆的最后一个元素交换，堆的大小减一，再对新的堆顶下沉，重复 N 次得到递增序列，复杂度 NlogN，原地排序
- 它很少和相邻的元素比较、交换，无法利用局部性原理进行缓存，所以一般的应用很少使用