堆排序（借助 API）
算法思想
利用堆能够维护数组中最大值的性质，根据数组元素建立最大堆，依次弹出元素并维护堆结构，直到堆为空。
稳定性分析
堆排序是不稳定的，因为堆本质上是完全二叉树，排序的过程涉及二叉树的父子节点交换，没有办法保证办法保证相等的值一定在同一棵子树上被处理。
具体实现
// Java 本身实现了优先队列的 API，其本质类似于堆，可以用来实现堆排序
private void heapSort(int[] arr) {
Queue<Integer> queue = new PriorityQueue<>();
for(int item : arr) {
queue.offer(item);
}
for(int i = 0; i < arr.length; i++) {
arr[i] = queue.poll();
}
}
堆操作
上面的堆排序实现，有一种脑干缺失的美，图一乐就行。堆相关的内容中，堆的原理和操作显然更重要。
自顶向底建堆
自顶向底建堆，时间复杂度是 O ( N l o g N ) O(NlogN) O(NlogN) 这个量级的。自下而上的调整操作实现起来比较简单，原因是对于每个子节点而言，父节点是唯一的。
// 交换数组中的两个元素
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 由下而上调整元素
private void upAdjust(int[] arr, int cur) {
while (arr[cur] > arr[(cur - 1) / 2]) {
// 当前元素大于父节点，那么进行交换并移动工作指针
swap(arr, cur, (cur - 1) / 2);
cur = (cur - 1) / 2;
}
}
// 自顶向底建堆
private void buildHeap(int[] arr) {
for (int i = 0; i < arr.length; i++) {
upAdjust(arr, i);
}
}
自底向顶建堆
自底向顶建堆，它的时间复杂度是 O ( N ) O(N) O(N) 这个量级的。实现相对来说要更麻烦，原因是父节点可能有两个子节点，涉及到与谁交换的判断。
// 交换数组中的两个元素
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 由上而下调整元素
private void downAdjust(int[] arr, int cur, int size) {
// 数组下标从零开始，当前节点的左孩子下标为 2 * cur + 1
int child = 2 * cur + 1;
while (child < size) {
// 如果当前节点有右孩子，那么比较两个子节点的值确定潜在的交换对象
int target = child + 1 < size && arr[child + 1] > arr[child] ? child + 1 : child;
// 再与当前节点比较大小
target = arr[target] > arr[cur] ? target : cur;
// 一旦发现此次操作中无需交换，立即停止流程
if (target == cur) {
break;
}
// 交换父子节点
swap(arr, target, cur);
// 移动工作指针
cur = target;
child = 2 * cur + 1;
}
}
// 自底向顶建堆
private void buildHeap(int[] arr) {
int n = arr.length;
for (int i = n - 1; i >= 0; i--) {
downAdjust(arr, i, n);
}
}
堆排序（自己实现）
自顶向底建堆并实现排序
// 交换数组中的两个元素
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 由下而上调整元素
private void upAdjust(int[] arr, int cur) {
while (arr[cur] > arr[(cur - 1) / 2]) {
// 当前元素大于父节点，那么进行交换并移动工作指针
swap(arr, cur, (cur - 1) / 2);
cur = (cur - 1) / 2;
}
}
// 自顶向底建堆
private void buildHeap(int[] arr) {
for (int i = 0; i < arr.length; i++) {
upAdjust(arr, i);
}
}
// 由上而下调整元素
private void downAdjust(int[] arr, int cur, int size) {
// 数组下标从零开始，当前节点的左孩子下标为 2 * cur + 1
int child = 2 * cur + 1;
while (child < size) {
// 如果当前节点有右孩子，那么比较两个子节点的值确定潜在的交换对象
int target = child + 1 < size && arr[child + 1] > arr[child] ? child + 1 : child;
// 再与当前节点比较大小
target = arr[target] > arr[cur] ? target : cur;
// 一旦发现此次操作中无需交换，立即停止流程
if (target == cur) {
break;
}
// 交换父子节点
swap(arr, target, cur);
// 移动工作指针
cur = target;
child = 2 * cur + 1;
}
}
// 堆排序
private void heapSort(int[] arr) {
buildHeap(arr);
int size = arr.length;
// 不断地交换堆顶元素与堆中的最后一个元素，并向下调整维护堆
while (size > 0) {
swap(arr, 0, --size);
downAdjust(arr, 0, size);
}
}
自底向顶建堆并实现排序
// 交换数组中的两个元素
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 由上而下调整元素
private void downAdjust(int[] arr, int cur, int size) {
// 数组下标从零开始，当前节点的左孩子下标为 2 * cur + 1
int child = 2 * cur + 1;
while (child < size) {
// 如果当前节点有右孩子，那么比较两个子节点的值确定潜在的交换对象
int target = child + 1 < size && arr[child + 1] > arr[child] ? child + 1 : child;
// 再与当前节点比较大小
target = arr[target] > arr[cur] ? target : cur;
// 一旦发现此次操作中无需交换，立即停止流程
if (target == cur) {
break;
}
// 交换父子节点
swap(arr, target, cur);
// 移动工作指针
cur = target;
child = 2 * cur + 1;
}
}
// 自底向顶建堆
private void buildHeap(int[] arr) {
int n = arr.length;
for (int i = n - 1; i >= 0; i--) {
downAdjust(arr, i, n);
}
}
// 堆排序
private void heapSort(int[] arr) {
buildHeap(arr);
int size = arr.length;
// 不断地交换堆顶元素与堆中的最后一个元素，并向下调整维护堆
while (size > 0) {
swap(arr, 0, --size);
downAdjust(arr, 0, size);
}
}
梳理总结
堆排序主要有两大步骤，包括建堆和出堆排序，其中建堆的操作根据方向的不同有效率上的差异，但是因为出堆排序需要 O ( N l o g N ) O(NlogN) O(NlogN) 量级的时间，所以总的时间复杂度为 O ( N l o g N ) O(NlogN) O(NlogN)。
在实现的选择上，虽然自顶向底建堆本身相对比较容易实现，但是由于出堆排序的过程中一定会涉及到由上而下的调整，反而需要记忆更多的内容。因此，可以考虑只记住自底向顶建堆的实现方法。
事实上鉴于堆排序不具有稳定性，性能上也只是中规中矩，所以通常只有在考试遇到、要求实现不使用额外空间的情况下（随机快排需要额外的递归栈空间，大约是 O ( l o g N ) O(logN) O(logN) 的水平；归并需要额外的辅助数组，是 O ( N ) O(N) O(N) 的水平），会手写实现堆排序。
而在实际应用的过程中，空间换时间是常见操作，所以不需要额外空间的堆并没有什么优势。
堆本身可以维护数组中最大最小值的性质是非常美妙的，一般来说直接调用语言本身提供的 API 即可，例如 C++ 的 STL 和 Java 中都提供了优先队列。
后记
使用 Leetcode 912. 排序数组 进行测试，堆排序能够比较高效地完成任务，大致与随机快速排序相当。