Java堆排序：用二叉树思维排序

Java 堆排序：用二叉树思维排序

借优先级队列的壳，排最大最小的序

引言

堆排序（Heap Sort）把数组当作完全二叉树，通过不断”堆化”把最大/最小元素顶到根，然后扔到末尾。

完美结合了快排的速度和归并的空间优势：

时间复杂度稳定 O(n log n)
空间复杂度 O(1)，原地排序
代价是不稳定，常数比快排大

它是 TopK 问题的最优解（无需全排序），也是 Java PriorityQueue 的底层数据结构。

这篇文章，我会把堆排序讲透：

用 ASCII 图演示堆化（heapify）和堆排序的完整过程
推导为什么 siftDown 是核心操作
列出 5 个高频易错点（尤其是建堆起始下标）
配套 LeetCode 215（TopK）和 347（前 K 个高频元素）

1. 核心思想：用数组模拟完全二叉树

1.1 堆的定义

堆是一种完全二叉树，满足：

大顶堆：父节点 ≥ 子节点（堆顶是最大值）
小顶堆：父节点 ≤ 子节点（堆顶是最小值）

1.2 数组存储完全二叉树

数组：[10, 7, 8, 9, 1, 5]
下标：  0  1  2  3  4  5

对应的完全二叉树：
              10(0)
            /     \
          7(1)    8(2)
         /  \     /
       9(3) 1(4) 5(5)

关键公式（0-indexed）：

左子节点：2 * i + 1
右子节点：2 * i + 2
父节点：(i - 1) / 2
最后一个非叶子节点：n / 2 - 1

1.3 ASCII 图解：堆排序完整过程

以数组 [12, 11, 13, 5, 6, 7] 为例，目标是升序：

第 1 步：建大顶堆

初始：[12, 11, 13, 5, 6, 7]

从 i = n/2 - 1 = 1 开始自底向上堆化：

i=1（节点 11）：左子 5(3)，右子 6(4)
  最大是 11，不变

i=0（节点 12）：左子 11(1)，右子 13(2)
  最大是 13，交换 12 和 13
  → [13, 11, 12, 5, 6, 7]
  继续堆化被交换的位置 2：
    节点 12，叶子，结束

建堆结果：[13, 11, 12, 5, 6, 7]
              13
            /    \
          11      12
         /  \     /
        5    6   7

第 2 步：排序

堆：[13, 11, 12, 5, 6, 7]   heapSize = 6

第 1 趟：交换堆顶 13 和末尾 7
  → [7, 11, 12, 5, 6, 13]   heapSize = 5
  对 7 执行 siftDown(0)
  → 7 < 12，交换
  → [12, 11, 7, 5, 6, 13]
  
第 2 趟：交换堆顶 12 和末尾 6
  → [6, 11, 7, 5, 12, 13]   heapSize = 4
  对 6 执行 siftDown(0)
  → 6 < 11，交换
  → [11, 6, 7, 5, 12, 13]

第 3 趟：交换堆顶 11 和末尾 5
  → [5, 6, 7, 11, 12, 13]   heapSize = 3
  对 5 执行 siftDown(0)
  → 5 < 7，交换
  → [7, 6, 5, 11, 12, 13]

第 4 趟：交换堆顶 7 和末尾 6
  → [6, 7, 5, 11, 12, 13]   heapSize = 2
  对 6 执行 siftDown(0)
  → 6 < 7，交换
  → [7, 6, 5, 11, 12, 13]

第 5 趟：交换堆顶 7 和末尾 5
  → [5, 6, 7, 11, 12, 13]   heapSize = 1
  结束

最终：[5, 6, 7, 11, 12, 13] ✓

1.4 三个关键观察

**建堆是 O(n)**——不是直觉的 O(n log n)（自底向上的均摊复杂度更低）
**排序是 O(n log n)**——n 趟交换 + 每趟 siftDown 是 O(log n)
要排升序必须用大顶堆——堆顶是最大值，扔到末尾正好是最大

2. 完整 Java 实现

import java.util.Arrays;

public class HeapSort {
    /**
     * 堆排序入口
     */
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int n = arr.length;
        // 第 1 步：建大顶堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            siftDown(arr, n, i);
        }
        // 第 2 步：排序
        for (int i = n - 1; i > 0; i--) {
            // 交换堆顶和末尾
            swap(arr, 0, i);
            // 对新的堆顶执行 siftDown，堆大小减 1
            siftDown(arr, i, 0);
        }
    }

    /**
     * 下沉操作（堆化的核心）
     */
    private static void siftDown(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);
            siftDown(arr, heapSize, largest);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("排序前: " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

3. 复杂度证明

3.1 建堆复杂度：O(n)（不是 O(n log n)）

直觉上建堆是 O(n log n)，但实际上更精确：

节点层	节点数	siftDown 最大深度
倒数第 1 层（叶子）	n/2	0
倒数第 2 层	n/4	1
倒数第 3 层	n/8	2
…	…	…
根	1	log n

总比较次数：

T(n) = Σ (每层节点数 × 每节点下沉深度)
     ≤ n/4 × 1 + n/8 × 2 + n/16 × 3 + ...
     = n × Σ (k / 2^(k+2))  （k 从 1 到 log n）
     < n × 1
     = O(n)

3.2 排序复杂度：O(n log n)

n 趟交换
每趟 siftDown 最坏下沉 log n 层
总：O(n log n)

3.3 总复杂度：O(n log n)

建堆 O(n) + 排序 O(n log n) = O(n log n)

3.4 空间复杂度

**O(1)**，原地排序（siftDown 用的 largest/left/right 是常数变量）

3.5 稳定性：不稳定

siftDown 时的交换会破坏相同元素的相对顺序
不稳定排序

4. 五个高频易错点

易错点 1：建堆起始下标写成 `n - 1`

// ❌ 错误：从叶子开始堆化，没有意义（叶子已经是堆）
for (int i = n - 1; i >= 0; i--) {
    siftDown(arr, n, i);
}

// ✅ 正确：从最后一个非叶子节点开始
for (int i = n / 2 - 1; i >= 0; i--) {
    siftDown(arr, n, i);
}

原理：叶子节点（i ≥ n/2）没有子节点，已经是堆。

易错点 2：用小顶堆排升序

// ❌ 错误：小顶堆的堆顶是最小值，扔到末尾后剩下的还是无序
// 排出来的结果是：堆顶（最小）放末尾 → 降序

// ✅ 正确：要排升序必须用大顶堆
// 堆顶（最大）放末尾 → 升序

记忆口诀：升序用大顶堆，降序用小顶堆。

易错点 3：siftDown 里忘记传 heapSize

// ❌ 错误：排序过程中 heapSize 在递减，但 siftDown 用了 n
private static void siftDown(int[] arr, int index) {
    int left = 2 * index + 1;
    if (left < arr.length && arr[left] > arr[arr[index]]) { ... }
}

// ✅ 正确：siftDown 必须知道当前的堆边界
private static void siftDown(int[] arr, int heapSize, int index) {
    int left = 2 * index + 1;
    if (left < heapSize && arr[left] > arr[index]) { ... }
}

易错点 4：siftDown 写成迭代版时漏掉递归

// ❌ 错误：迭代版漏写 while 循环
private static void siftDownIterative(int[] arr, int heapSize, int index) {
    int largest = index;
    int left = 2 * index + 1;
    if (left < heapSize && arr[left] > arr[largest]) largest = left;
    // 漏了 while 循环，没有继续下沉
}

// ✅ 正确：迭代版
private static void siftDownIterative(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;
    }
}

易错点 5：左右子节点比较时漏掉等号

// ❌ 错误：相同元素会破坏稳定性
if (left < heapSize && arr[left] >= arr[largest]) largest = left;

// ✅ 正确：严格大于，保持原相对顺序
if (left < heapSize && arr[left] > arr[largest]) largest = left;

5. TopK 问题：堆排序的最强战场

堆排序的真正价值不是全排序，而是 TopK 问题——找最大/最小的 K 个元素，无需全排序。

5.1 求前 K 大元素（小顶堆解法）

思路：维护大小为 K 的小顶堆，堆顶是最小的；遍历数组时，如果当前元素比堆顶大，就替换堆顶。

public int[] topKFrequent(int[] nums, int k) {
    // 维护大小为 k 的小顶堆
    PriorityQueue<Integer> heap = new PriorityQueue<>(k);
    for (int num : nums) {
        if (heap.size() < k) {
            heap.offer(num);
        } else if (num > heap.peek()) {
            heap.poll();
            heap.offer(num);
        }
    }
    // 堆里就是前 k 大
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = heap.poll();
    }
    return result;
}

复杂度：O(n log k)，比全排序 O(n log n) 快得多。

5.2 求前 K 大元素（大顶堆解法）

思路：把所有元素放入大顶堆，弹出 K 次。

public int[] topKFrequent(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.reverseOrder());
    for (int num : nums) {
        heap.offer(num);
    }
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = heap.poll();
    }
    return result;
}

复杂度：O(n log n)，没有利用 K 小的优势。

5.3 两种解法对比

解法	时间	适用场景
小顶堆（size=K）	O(n log k)	K 较小（k << n）
大顶堆（size=n）	O(n log n)	K 接近 n

工程首选：小顶堆。

6. 适用场景与禁区

6.1 适用场景

TopK 问题：小顶堆 O(n log k) 是最优解
**需要 O(1) 空间的 O(n log n)**：堆排序的独特优势
优先级队列底层：Java PriorityQueue 用的就是堆
数据流中的中位数：维护两个堆（大顶堆 + 小顶堆）

6.2 不适用场景

要求稳定排序：堆排序不稳定
数据基本有序：堆排序对有序数据没优势，反而比插入排序慢
小数据量：常数大，不如插入排序

7. 面试常见变形

变形 1：siftUp（上浮，用于插入）

private static void siftUp(int[] arr, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (arr[index] <= arr[parent]) break;
        swap(arr, index, parent);
        index = parent;
    }
}

适用：往堆里插入新元素。

变形 2：数据流中的中位数（Hard）

思路：维护两个堆——大顶堆存较小的一半，小顶堆存较大的一半

class MedianFinder {
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    public void addNum(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) return maxHeap.peek();
        return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}

复杂度：addNum O(log n)，findMedian O(1)。

变形 3：堆化字符串（LeetCode 767）

思路：字符频率统计 + 大顶堆 + 贪心插入

8. LeetCode 真题实战

题目 1：215. 数组中的第 K 个最大元素（中等）

解法 1：堆排序解法（全排序）

public int findKthLargest(int[] nums, int k) {
    heapSort(nums);
    return nums[nums.length - k];
}

结果：n=10000 时能 AC（O(n log n) 比快排的 O(n²) 稳定）。

解法 2：小顶堆解法（推荐）

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>(k);
    for (int num : nums) {
        if (heap.size() < k) {
            heap.offer(num);
        } else if (num > heap.peek()) {
            heap.poll();
            heap.offer(num);
        }
    }
    return heap.peek();
}

复杂度：O(n log k)，比全排序快得多。

题目 2：347. 前 K 个高频元素（中等）

解法：哈希表统计频率 + 小顶堆选 TopK

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int num : nums) {
        count.merge(num, 1, Integer::sum);
    }
    // 小顶堆：堆顶是当前最小的频率
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
        if (heap.size() < k) {
            heap.offer(new int[]{entry.getKey(), entry.getValue()});
        } else if (entry.getValue() > heap.peek()[1]) {
            heap.poll();
            heap.offer(new int[]{entry.getKey(), entry.getValue()});
        }
    }
    return heap.stream().mapToInt(a -> a[0]).toArray();
}

复杂度：O(n log k)。

题目 3：295. 数据流的中位数（困难）

解法：套用变形 2。

总结

一句话精髓

堆排序 = 建大顶堆 + 堆顶扔末尾 + siftDown 维护堆。

三个关键洞察

TopK 问题才是堆的主战场——全排序用堆排不如快排
升序用大顶堆，降序用小顶堆——反了排出来是反的
siftDown 是核心——理解了下沉，TopK/中位数/优先级队列都通了

下一步行动

手写小顶堆解 TopK（变形 1），体会 O(n log k) 的优势
实现数据流中位数（变形 2），这是大厂常考 Hard 题
在 JDK 源码搜索 PriorityQueue，看 siftDown 的工业实现

本文由 AI 对话整理精炼而成
整理时间：2026-06-18
原文来源：DeepSeek

技术

#Java #算法 #排序 #堆排序 #数据结构

0 次浏览

Java堆排序：用二叉树思维排序

https://easyscreen.icu/2026/06/18/java-dui-pai-xu-yong-er-cha-shu-si-wei-pai-xu/

作者

杰哥

发布于

2026年6月18日

许可协议

Java 归并排序：稳定排序的"秩序守护者" 上一篇

GLM-5.2 发布：中国 AI 的「Opus 级」时刻下一篇

Java堆排序：用二叉树思维排序

Java 堆排序：用二叉树思维排序

引言

1. 核心思想：用数组模拟完全二叉树

1.1 堆的定义

1.2 数组存储完全二叉树

1.3 ASCII 图解：堆排序完整过程

1.4 三个关键观察

2. 完整 Java 实现

3. 复杂度证明

3.1 建堆复杂度：O(n)（不是 O(n log n)）

3.2 排序复杂度：O(n log n)

3.3 总复杂度：O(n log n)

3.4 空间复杂度

3.5 稳定性：不稳定

4. 五个高频易错点

易错点 1：建堆起始下标写成 n - 1

易错点 2：用小顶堆排升序

易错点 3：siftDown 里忘记传 heapSize

易错点 4：siftDown 写成迭代版时漏掉递归

易错点 5：左右子节点比较时漏掉等号

5. TopK 问题：堆排序的最强战场

5.1 求前 K 大元素（小顶堆解法）

5.2 求前 K 大元素（大顶堆解法）

5.3 两种解法对比

6. 适用场景与禁区

6.1 适用场景

6.2 不适用场景

7. 面试常见变形

变形 1：siftUp（上浮，用于插入）

变形 2：数据流中的中位数（Hard）

变形 3：堆化字符串（LeetCode 767）

8. LeetCode 真题实战

题目 1：215. 数组中的第 K 个最大元素（中等）

题目 2：347. 前 K 个高频元素（中等）

题目 3：295. 数据流的中位数（困难）

总结

一句话精髓

三个关键洞察

下一步行动

易错点 1：建堆起始下标写成 `n - 1`