堆排序
堆排序（Heap Sort）是一种基于堆数据结构的排序算法。
堆的定义
堆是一棵完全二叉树，树的根节点永远比它的孩子节点大（大根堆）或小（小根堆）。
数组模拟
为了节省空间，并不需要真正构建树结构，而是用数组下标来模拟树结构。
建堆过程：从最后一个非终端节点（非叶子结点）开始向前建堆，因为终端节点没有子节点。
构建大根堆
从最后一个非终端节点开始比较其与孩子节点的大小：
- 如果该节点大于两个孩子节点，则略过
- 否则与孩子节点中较大的一个进行交换，并继续与交换后的孩子节点进行比较调整
算法分析
- 时间复杂度：O(n log n)
- 空间复杂度：O(1)
- 稳定性：不稳定
链接到
- 上一个知识点：6.8 树形选择排序
- 下一个知识点：6.10 归并排序