常见排序算法总结 (五) - 堆排序与堆操作

堆排序（借助 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(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)$ 这个量级的。实现相对来说要更麻烦，原因是父节点可能有两个子节点，涉及到与谁交换的判断。

// 交换数组中的两个元素
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 + 1int 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 + 1int 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 + 1int 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(NlogN)$ 量级的时间，所以总的时间复杂度为 $O(NlogN)$。
在实现的选择上，虽然自顶向底建堆本身相对比较容易实现，但是由于出堆排序的过程中一定会涉及到由上而下的调整，反而需要记忆更多的内容。因此，可以考虑只记住自底向顶建堆的实现方法。
事实上鉴于堆排序不具有稳定性，性能上也只是中规中矩，所以通常只有在考试遇到、要求实现不使用额外空间的情况下（随机快排需要额外的递归栈空间，大约是 $O(logN)$ 的水平；归并需要额外的辅助数组，是 $O(N)$ 的水平），会手写实现堆排序。
而在实际应用的过程中，空间换时间是常见操作，所以不需要额外空间的堆并没有什么优势。

堆本身可以维护数组中最大最小值的性质是非常美妙的，一般来说直接调用语言本身提供的 API 即可，例如 C++ 的 STL 和 Java 中都提供了优先队列。

后记

使用 Leetcode 912. 排序数组 进行测试，堆排序能够比较高效地完成任务，大致与随机快速排序相当。

相关阅读

• 常见排序算法总结 (一) - 三种基本排序
• 常见排序算法总结 (二) - 不基于比较的排序
• 常见排序算法总结 (三) - 归并排序与归并分治
• 常见排序算法总结 (四) - 快速排序与随机选择