一、堆
堆一般指的是二叉堆，二叉堆是完全二叉树或者近似完全二叉树
每个节点的值都大于或等于其子节点的值，为最大堆；反之为最小堆。
堆排序是利用堆这种数据结构设计的排序算法，更准确的说，是利用堆的删除操作所设计的一种排序算法。
比如：删除堆顶元素的时候，我们使用的是替换法删除，也就是将堆顶元素和数组末尾的元素交换，每次选择的堆顶元素是堆中当前的最大or最小元素。相当于每次都能在待排序序列中选出一个最值，从后往前填入数组中的一个正确位置。
- 如果是大堆，任意节点值 ≥ 其子节点值，每次选出的数据就是当前堆中最大的元素，从数组后面往前填入数组，排出来的数据是升序的。
- 如果是小堆，任意节点值 ≤ 其子节点值，每次选出的数据就是当前堆中最小的元素，从数组后面往前填入数组，排出来的数据是降序的。
所以，如果我们想排升序，建堆的时候，应该建立大堆；如果我们想排降序，建堆的时候，应该建立小堆。
二、堆存储结构
以大堆为例：
image-20241022171439530
实际数组存储结构
image-20241022171505207
- 如果某二叉树节点（非叶子节点）的下标为 ii，那么其左孩子节点下标为 `2×i+12×i+1，右孩子节点下标为 2×i+22×i+2。
- 如果某二叉树节点（非根结点）的下标为 ii，那么其根节点下标为 ⌊i−12⌋⌊2i−1⌋（向下取整）。
二、堆排序实现
堆排序的实现主要分为两步：建堆和选数。
