1. 简介
在本教程中，我们将深入探讨 堆排序（Heap Sort） 的工作原理，并给出其在 Java 中的具体实现。
堆排序依赖于一种名为“堆（Heap）”的数据结构。要理解堆排序的本质，我们首先得搞清楚什么是堆，以及它是如何实现的。
2. 堆（Heap）数据结构
堆是一种基于树的特殊数据结构，由节点组成。每个节点存储一个元素，并且可以拥有子节点。如果某个节点没有子节点，则称其为叶子节点。
堆的特殊之处在于以下两点：
- 每个节点的值必须 小于或等于其所有子节点的值
- 它是一棵 完全二叉树（Complete Binary Tree），即树的高度最小
由于第一条规则，堆顶（根节点）总是最小的元素。
堆的实现方式多种多样，常见的有最小堆（Min-Heap）和最大堆（Max-Heap）。我们这里以 最小堆 为例进行讲解，即父节点的值始终小于其子节点。
2.1. 堆的不同类型
堆有多个变体，主要区别在于实现细节。
例如，我们前面描述的是 最小堆（Min-Heap），因为父节点总是小于其子节点。如果我们定义父节点大于子节点，则称为 最大堆（Max-Heap），此时堆顶是最大的元素。
在实现上，堆通常采用 二叉树结构，即每个节点最多有两个子节点：左子节点 和 右子节点。
为了便于维护完全二叉树结构，堆通常采用数组实现。在数组中，节点索引遵循以下规律：
- 父节点索引：
(index - 1) / 2 - 左子节点索引：
2 * index + 1 - 右子节点索引：
2 * index + 2
让我们通过几个示意图来直观理解这些规则：
1 2 3 4 5 6 7 8 9 10
() () () () () () () () () ()
/ \ / \ / \ / \ / \ / / / \
() () () () () () () () () () () () () ()
/ \ / \ / \ / / \
() () () () () () () () ()
/
()
✅ 树 1、2、4、5 和 7 是合法的
❌ 树 3 和 6 违反了第一条规则
❌ 树 8 和 9 违反了第二条规则
❌ 树 10 违反了第三条规则
本教程将聚焦于 使用二叉树实现的最小堆（Min-Heap）。
2.2. 插入元素
堆的插入操作必须保证堆的两个不变性：
- 节点值小于等于子节点值
- 树结构为完全二叉树
插入新元素的步骤如下：
- 在最深层的最右侧插入新节点
- 如果该节点值小于其父节点，交换两者
- 继续向上比较并交换，直到满足堆性质或到达根节点
✅ 这种“上浮”操作不会破坏堆结构，因为交换后父节点仍小于子节点。
我们来看一个插入 4 的示例：
2
/ \
/ \
3 6
/ \
5 7
插入 4 后：
2
/ \
/ \
3 6
/ \ /
5 7 4
4 < 6，交换：
2
/ \
/ \
3 4
/ \ /
5 7 6
继续比较，4 > 2，结束。
再插入 1：
2
/ \
/ \
3 4
/ \ / \
5 7 6 1
交换 1 和 4：
2
/ \
/ \
3 1
/ \ / \
5 7 6 4
再交换 1 和 2：
1
/ \
/ \
3 2
/ \ / \
5 7 6 4
1 成为根节点，结束。
3. Java 中的堆实现
由于堆是完全二叉树，我们可以使用数组来高效实现。每个节点的索引关系如下：
0
/ \
/ \
1 2
/ \ /
3 4 5
下面是基础的二叉树实现：
class BinaryTree<E> {
List<E> elements = new ArrayList<>();
void add(E e) {
elements.add(e);
}
boolean isEmpty() {
return elements.isEmpty();
}
E elementAt(int index) {
return elements.get(index);
}
int parentIndex(int index) {
return (index - 1) / 2;
}
int leftChildIndex(int index) {
return 2 * index + 1;
}
int rightChildIndex(int index) {
return 2 * index + 2;
}
}
接下来，我们实现堆的“上浮”逻辑，确保插入后仍满足堆性质：
class Heap<E extends Comparable<E>> {
// ...
void add(E e) {
elements.add(e);
int elementIndex = elements.size() - 1;
while (!isRoot(elementIndex) && !isCorrectChild(elementIndex)) {
int parentIndex = parentIndex(elementIndex);
swap(elementIndex, parentIndex);
elementIndex = parentIndex;
}
}
boolean isRoot(int index) {
return index == 0;
}
boolean isCorrectChild(int index) {
return isCorrect(parentIndex(index), index);
}
boolean isCorrect(int parentIndex, int childIndex) {
if (!isValidIndex(parentIndex) || !isValidIndex(childIndex)) {
return true;
}
return elementAt(parentIndex).compareTo(elementAt(childIndex)) < 0;
}
boolean isValidIndex(int index) {
return index < elements.size();
}
void swap(int index1, int index2) {
E element1 = elementAt(index1);
E element2 = elementAt(index2);
elements.set(index1, element2);
elements.set(index2, element1);
}
// ...
}
⚠️ 注意：为了支持比较，泛型 E 必须实现 Comparable 接口。
4. 堆排序的核心思想
堆排序的思路很简单：
不断移除堆顶元素，直到堆为空
关键在于如何“移除”堆顶元素，同时保持堆的结构和性质。
✅ 正确做法是：
- 将堆顶元素与最后一个叶子节点交换
- 删除最后一个节点（即原堆顶）
- 对新堆顶执行“下沉”操作，恢复堆性质
我们来看一个示例：
1
/ \
/ \
3 2
/ \ / \
5 7 6 4
移除 1 后，将 4 移到堆顶：
4
/ \
/ \
3 2
/ \ /
5 7 6
4 > 2，交换：
2
/ \
/ \
3 4
/ \ /
5 7 6
4 < 6，停止。
5. Java 实现堆排序
下面是完整的堆排序实现，包括 pop() 方法和排序方法：
class Heap<E extends Comparable<E>> {
// ...
E pop() {
if (isEmpty()) {
throw new IllegalStateException("You cannot pop from an empty heap");
}
E result = elementAt(0);
int lasElementIndex = elements.size() - 1;
swap(0, lasElementIndex);
elements.remove(lasElementIndex);
int elementIndex = 0;
while (!isLeaf(elementIndex) && !isCorrectParent(elementIndex)) {
int smallerChildIndex = smallerChildIndex(elementIndex);
swap(elementIndex, smallerChildIndex);
elementIndex = smallerChildIndex;
}
return result;
}
boolean isLeaf(int index) {
return !isValidIndex(leftChildIndex(index));
}
boolean isCorrectParent(int index) {
return isCorrect(index, leftChildIndex(index)) && isCorrect(index, rightChildIndex(index));
}
int smallerChildIndex(int index) {
int leftChildIndex = leftChildIndex(index);
int rightChildIndex = rightChildIndex(index);
if (!isValidIndex(rightChildIndex)) {
return leftChildIndex;
}
if (elementAt(leftChildIndex).compareTo(elementAt(rightChildIndex)) < 0) {
return leftChildIndex;
}
return rightChildIndex;
}
// ...
}
排序方法如下：
class Heap<E extends Comparable<E>> {
// ...
static <E extends Comparable<E>> List<E> sort(Iterable<E> elements) {
Heap<E> heap = of(elements);
List<E> result = new ArrayList<>();
while (!heap.isEmpty()) {
result.add(heap.pop());
}
return result;
}
static <E extends Comparable<E>> Heap<E> of(Iterable<E> elements) {
Heap<E> result = new Heap<>();
for (E element : elements) {
result.add(element);
}
return result;
}
// ...
}
测试代码：
@Test
void givenNotEmptyIterable_whenSortCalled_thenItShouldReturnElementsInSortedList() {
// given
List<Integer> elements = Arrays.asList(3, 5, 1, 4, 2);
// when
List<Integer> sortedElements = Heap.sort(elements);
// then
assertThat(sortedElements).isEqualTo(Arrays.asList(1, 2, 3, 4, 5));
}
✅ 可以进一步优化为 原地排序 版本，避免额外空间分配。
6. 时间复杂度分析
堆排序主要由两个操作组成：
- 插入元素：
O(log n) - 弹出堆顶：
O(log n)
✅ 由于这两个操作都要执行 n 次，因此整体时间复杂度为 **O(n log n)**。
⚠️ 值得注意的是：
- 数组扩容的代价是
O(n)，但不影响总体复杂度 - 50% 的节点是叶子节点，插入操作通常只需 1~2 次上浮
- 最坏情况下，堆排序始终是 **O(n log n)**，优于快速排序在极端情况下的 O(n²)
7. 总结
本文介绍了二叉堆的实现以及堆排序算法。虽然堆排序的时间复杂度稳定在 O(n log n)，但在实际应用中，快速排序往往表现更好。
✅ 优势：
- 稳定的最坏时间复杂度
- 不依赖数据分布
❌ 劣势：
- 常数因子较大
- 不是原地排序（除非特别优化）
如需完整代码，请访问 GitHub 示例。