堆的结构及其调整操作
堆可被视为一棵完全二叉树，用数组来存储其元素，其结构和数组元素和二叉树结点对应关系如下图
堆的结构
数组元素与二叉树结点的对应关系
大根堆
当新加入结点时，我们需要对堆进行调整，来使得整个堆的结构不被破坏。新加入的结点默认放在堆的最末尾，此时就可能需要将该结点向上调整。结合之前，我们可以确定i元素的父亲结点所在位置，因此只需将i元素与其父亲结点比较，若大于父亲结点，则向上交换，之后继续向上比较判断；否则就保持不动
// i位置的数，向上调整大根堆
public static void heapInsert(int i) {
while (arr[i] > arr[(i - 1) / 2]) {
swap(i, (i - 1) / 2);
i = (i - 1) / 2;
}
}
而从堆中取出元素时，默认是堆顶元素弹出，然后用最末尾的元素放到堆顶位置，此时就需要向下比较调整堆的结构，若该元素大于左右两个孩子结点的最大元素，则保持不动；否则将该元素与左右孩子中最大的那个交换，继续向下判断调整
// i位置的数，向下调整大根堆
// 当前堆的大小为size
public static void heapify(int i, int size) {
int l = i * 2 + 1; // 左孩子
while (l < size) {
// 只有当右孩子存在且大于左孩子时，比较判断右孩子和i元素的大小
// 否则，一定选择左孩子来比较判断与i元素的大小
int best = l + 1 < size && arr[l + 1] > arr[l] ? l + 1 : l;
best = arr[best] > arr[i] ? best : i;
if (best == i) {
break;
}
swap(best, i);
i = best;
l = i * 2 + 1;
}
}
由于调整算法最多就从二叉树的根结点调整到底部，或者从底部调整到根，因此时间复杂度为O（logn）。
堆排序
第一步.建堆
建堆可分为自底到顶建堆和自顶到底建堆，接下来分别介绍一下
自顶到底建堆
对于无序数组arr，初始时假设堆的大小为0，每次加入数组中的新元素到堆的最后，然后堆的大小+1，新加入的元素向上进行调整，使得整个堆满足大根堆的结构。
自顶到底建堆
public static void heapSort1(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
heapInsert(arr, i);
}
}
一个数进入堆并向上调整的时间复杂度为O（logn），而共有n个数，因此时间复杂度为O（n*logn）。
自底到顶建堆
对于无序数组arr，初始时堆就包含整个数组元素，之后从堆的最后开始，依次向下调整
自底到顶建堆
public static void heapSort2(int[] arr) {
int n = arr.length;
for (int i = n - 1; i >= 0; i--) {
heapify(arr, i, n);
}
}
自底到顶每层节点向下调整次数
第二步.大数归位
完成第一步建堆之后，堆顶元素为整个数组中的最大元素，此时我们让堆顶元素与堆最末尾的元素交换位置，此时最大数就来到了数组的最后，后续就不再调整最大数的位置，再让堆的大小-1，这时需再次调整堆，使其满足大根堆的性质，不断进行，直到堆的大小为0，整个数组就是有序状态了。
大数归位
int size = n;
while (size > 1) {
swap(arr, 0, --size);
heapify(arr, 0, size);
}
每次调整堆的时间复杂度约O（logn），因此这一步的时间复杂度为O（n*logn）。
以上两步进行完，堆排序就完成了，堆排序总体的时间复杂度是O（n*logn），空间复杂度为O（1）。
