用堆序找到当前最大项
最大二叉堆要求每个父键不小于孩子，因此根就是当前最大项；完全二叉树的形状可用数组下标表示。堆序只约束父子路径，不会把同层或左右子树的所有元素排成完整顺序。
堆排序直接在待排数组中维持这套结构。它与使用一个独立优先队列逐项取值的思路相关，但不必另建完整结果容器；数组的一段保存尚待取出的堆，另一段逐步保存已经定位的最大项。
参考：[1]
自底向上建堆，再逐项移出
批量建堆可以从最后一个内部节点向根执行下沉，让每个节点在孩子已经成堆的前提下修复自己的子树。虽然个别下沉可能走对数级路径，绝大多数节点靠近底部，总工作可在线性时间内完成。
排序阶段把根与当前堆末项交换，将堆范围缩小一个位置，再把新根下沉。被取出的最大项已经在最终位置，不再参加堆调整；重复至堆只剩至多一个元素，整个数组便按升序排列。
参考：[1]
最坏界与稳定性的取舍
每次移出后至多沿一条树高路径修复，因而n次移出的总时间为O(n log n)。这个界不依赖输入本来随机或枢轴恰好均衡；按通常单位比较成本计算，迭代数组实现还只需O(1)额外空间。
代价之一是普通堆排序不稳定，远距离交换会改变同键记录次序。堆本身也不是完整有序数组，不能在建堆后就把任意位置当作对应排名。比较具体排序方案时，还需考虑键比较成本及实际数据访问行为，不能仅凭最坏阶数断定速度。