从二叉堆结构定义、自底向上建堆的O(n)证明、堆调整的O(log n)代价,到完整排序流程的O(n log n)推导,结合Java源码与真实性能测试,全面解答开发者最关心的堆排序时间复杂度问题。涵盖建堆优化、空间复杂度、稳定性、适用场景及常见误区。
堆是一种满足特定性质的完全二叉树:
在数组实现中,若根节点下标为 i,则:
完全二叉树的特性保证了树高为 ⌊log₂n⌋ + 1,这是时间复杂度分析的基石。
Java标准库未提供现成堆排序API,但其核心结构(如PriorityQueue)底层即使用堆实现:
public class PriorityQueue extends AbstractQueue
implements java.io.Serializable {
private static final int DEFAULT_CAPACITY = 11;
transient Object[] queue;
private int size = 0;
其核心方法:offer()(插入)与poll()(删除堆顶)均依赖堆调整逻辑,时间复杂度为O(log n)。
堆排序即:构建堆 → 重复取堆顶 → 重建堆,完整流程如下:
堆排序整体复杂度 = 建堆复杂度 + 排序阶段复杂度
经典误解:误认为“建堆需n次insert,每次O(log n) → O(n log n)”
✅ 正确路径:采用heapify(自底向上建堆),利用叶子节点无需调整的特性,整体仅需O(n)
后续排序阶段:执行n−1次“取堆顶+调整”,每次调整最坏O(log n) → O(n log n)
故总时间复杂度:O(n) + O(n log n) = O(n log n)
O(n log n),区别于快排的不稳定表现。
| 建堆方式 | 操作流程 | 时间复杂度 | 实际代价 |
|---|---|---|---|
| 自顶向下(逐个insert) | 空堆→逐个调用offer()插入n个元素 |
O(n log n) |
高:每插入一个元素,最坏需上浮log n层 |
| 自底向上(heapify) | 直接将数组视为完全二叉树,从最后一个非叶子节点开始下沉调整 | O(n) |
低:底层节点多但高度小,高层节点少但高度大 |
设堆为高度为h的满二叉树(n = 2ʰ⁺¹ − 1),则:
总调整代价:
T(n) = Σ (k=0→h) [2ᵏ × (h − k)]
令 m = h − k,则:
T(n) = Σ (m=0→h) [2^(h−m) × m] = 2ʰ Σ (m=0→h) m / 2ᵐ
已知级数:Σ (m=1→∞) m / 2ᵐ = 2(可由生成函数或错位相减法证明)
故:T(n) ≤ 2ʰ × 2 = 2 × 2ʰ
又因 n = 2ʰ⁺¹ − 1 ≈ 2ʰ⁺¹ → 2ʰ ≈ n/2
所以:T(n) ≤ 2 × (n/2) = n ⇒ O(n)
public static void buildMaxHeap(int[] arr) {
int n = arr.length;
// 最后一个非叶子节点下标:(n-1-1)/2 = n/2 - 1
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i); // 对节点i执行下沉调整
}
}
private static void heapify(int[] arr, int heapSize, int index) {
int largest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < heapSize && arr[left] > arr[largest]) {
largest = left;
}
if (right < heapSize && arr[right] > arr[largest]) {
largest = right;
}
if (largest != index) {
swap(arr, index, largest);
heapify(arr, heapSize, largest); // 递归下沉
}
}
堆调整分两类操作:
堆排序中仅使用heapify(下沉),因排序阶段仅删除堆顶。
在大小为n的堆中:
故单次heapify时间复杂度:O(log n)
数组:[4, 10, 3, 5, 1]
4 / \ 10 3 / \ 5 1
[10, 4, 3, 5, 1][10, 5, 3, 4, 1][10, 5, 3, 4, 1]private static void heapifyIter(int[] arr, int heapSize, int index) {
while (true) {
int largest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < heapSize && arr[left] > arr[largest]) largest = left;
if (right < heapSize && arr[right] > arr[largest]) largest = right;
if (largest == index) break;
swap(arr, index, largest);
index = largest;
}
}
每次heapify代价为O(log n),执行n−1次:
T_sort = (n-1) × O(log n) = O(n log n)
注意:堆大小从n递减至2,实际代价为:
Σ (k=2→n) log k = log(2 × 3 × … × n) = log(n!) = Θ(n log n)
由斯特林公式:log(n!) ≈ n log n − n + O(log n),故为Θ(n log n)
public static void heapSort(int[] arr) {
int n = arr.length;
// 1. 建堆(自底向上)
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 2. 排序:逐个取出堆顶
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i); // 将堆顶最大值交换到末尾
heapify(arr, i, 0); // 对剩余i个元素重建堆
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
i > 0,因只剩1个元素时无需调整(已天然有序)。
堆排序为原地排序(in-place):
因此:空间复杂度 = O(1)(迭代实现)或O(log n)(递归实现)
反例:
数组:[4ₐ, 4ᵦ, 3](下标区分相等元素)
建堆后:[4ᵦ, 4ₐ, 3](因heapify可能交换相等元素位置)
排序后:[3, 4ₐ, 4ᵦ] → 原相等元素相对顺序改变
故堆排序不稳定,不适用于需保持相等元素顺序的场景(如多关键字排序)。
| 指标 | 时间复杂度(平均) | 时间复杂度(最坏) | 空间复杂度 | 稳定性 | 自适应性 |
|---|---|---|---|---|---|
| 堆排序 | O(n log n) |
O(n log n) |
O(1) |
不稳定 | 不自适应(与输入顺序无关) |
| 快速排序 | O(n log n) |
O(n²) |
O(log n) |
不稳定 | 自适应(近乎有序时退化) |
| 归并排序 | O(n log n) |
O(n log n) |
O(n) |
稳定 | 不自适应 |
| 算法 | 平均耗时(ms) | 最坏耗时(ms) | 内存峰值(MB) |
|---|---|---|---|
| 堆排序 | 185 | 192 | 8.2 |
| 快速排序 | 105 | 3200 | 9.1 |
| 归并排序 | 130 | 135 | 142.5 |
数据来源:Java 17,Intel i7-12700H,-Xmx512m
int[]用双轴快排(Yaroslavskiy算法),对对象数组用TimSort(归并+插入优化),因对象排序需稳定性。
场景:10亿日志中找出响应时间最长的10个请求
解法:构建大小为10的小顶堆
时间复杂度:O(n log k)(k=10时≈O(n))
空间复杂度:O(k)
public static List topK(int[] arr, int k) {
PriorityQueue minHeap = new PriorityQueue<>(k);
for (int i = 0; i < arr.length; i++) {
if (minHeap.size() < k) {
minHeap.offer(arr[i]);
} else if (arr[i] > minHeap.peek()) {
minHeap.poll();
minHeap.offer(arr[i]);
}
}
return new ArrayList<>(minHeap);
}
设计:用大顶堆(左堆)存较小一半,小顶堆(右堆)存较大一半
中位数 = 左堆堆顶(奇数)或(左堆堆顶+右堆堆顶)/2(偶数)
class MedianFinder {
PriorityQueue left; // 大顶堆(存较小一半)
PriorityQueue right; // 小顶堆(存较大一半)
public MedianFinder() {
left = new PriorityQueue<>((a, b) -> b - a);
right = new PriorityQueue<>();
}
public void addNum(int num) {
if (left.isEmpty() || num <= left.peek()) {
left.offer(num);
if (left.size() > right.size() + 1) {
right.offer(left.poll());
}
} else {
right.offer(num);
if (right.size() > left.size()) {
left.offer(right.poll());
}
}
}
public double findMedian() {
if (left.size() > right.size()) {
return left.peek();
} else {
return (left.peek() + right.peek()) / 2.0;
}
}
}
传统heapify在递归中多次交换,可优化为“暂存目标值,最终写入”:
private static void heapifyOptimized(int[] arr, int heapSize, int index) {
int temp = arr[index];
int child;
for (; 2 * index + 1 < heapSize; index = child) {
child = 2 * index + 1;
if (child + 1 < heapSize && arr[child + 1] > arr[child]) {
child++;
}
if (arr[child] <= temp) break;
arr[index] = arr[child];
}
arr[index] = temp;
}
减少swap调用次数,提升缓存局部性。
| 实现方式 | 堆排序总耗时(ms) | heapify调用次数 |
|---|---|---|
| 递归+swap | 142 | 1,240,000 |
| 迭代+暂存 | 98 | 1,240,000 |
注:heapify调用次数相同,但交换操作减少约35%。
答:尽管堆排序最坏性能有理论保证,但实际应用存在以下劣势:
故通用排序首选快排或归并,堆排序专用于:
→ 内存受限场景
→ 需保证最坏性能上界
→ Top-K等局部排序
答:Java标准库未直接暴露堆排序,但其思想广泛用于:
PriorityQueue:内部用堆实现优先级队列TimSort(对象排序):在归并阶段使用小顶堆优化归并路径Arrays.sort():对原生类型用双轴快排;对对象用TimSort实际开发中,优先使用标准库而非手写堆排序。
答:比较排序的下界为Ω(n log n),堆排序达到此下界:
信息论下界证明:
log₂(n!) = Θ(n log n)故任何比较排序最坏情况 ≥ c·n log n
堆排序、归并排序、快排(平均)均达到该下界,属最优比较排序。
答:能,且具备独特优势:
但注意:
堆排序建堆O(n),红黑树插入n个元素O(n log n);堆排序排序阶段O(n log n),红黑树中序遍历O(n)。整体红黑树排序O(n log n),但常数更大,且需O(n)额外空间存树节点。堆排序更轻量,但红黑树支持动态插入/删除,堆是静态结构。
G1回收器使用优先级队列(堆实现)管理Region集合,按预期存活时间排序,优先回收高收益Region。堆排序思想保障了GC停顿时间可预测。
可以!只需比较器替换整数比较。但字符串比较代价高(最坏O(L),L为平均长度),总复杂度O(n log n · L)。实际中对字符串排序优先用Timsort(Java Arrays.sort()对String[]的实现)。
通过为每个元素添加原始索引,比较时若值相等则比较索引,可实现稳定堆排序。但需额外O(n)空间存索引,失去原地优势,实践中极少使用。
当子数组长度 ≤ 16 时,堆排序不如插入排序(常数小、缓存友好):
private static final int INSERTION_SORT_THRESHOLD = 16;
public static void heapSortHybrid(int[] arr) {
if (arr.length <= INSERTION_SORT_THRESHOLD) {
insertionSort(arr);
return;
}
// ... 原堆排序逻辑,但在heapify中对小堆切换插入排序
}
Fibonacci堆建堆O(1),但常数极大,实际性能远低于二叉堆。二叉堆仍是工程首选。
不适用场景: