面试官追问的堆排序细节-这篇讲透2种建堆方式

本文用大根堆来实现升序排序。

大根堆其实是一种特殊的“完全二叉树”，要求 “父节点的值大于子节点的值”。

在使用数组存储时有以下索引关系：

若父节点索引为i，则左孩子索引是2i+1，右孩子索引是2i+2；
若子节点索引为i，则父节点索引是(i-1)/2（整数除法，向下取整）。

heapInsert：向上调整

不断和父节点比较，若比父节点大就交换，直到父节点更大或到堆顶（索引 0）。

1
2
3
4
5
6
7


public static void heapInsert(int[] arr, int i) {
    // 父节点索引=(i-1)/2，只要当前元素>父节点，就交换
    while (arr[i] > arr[(i - 1) / 2]) {
        swap(arr, i, (i - 1) / 2);
        i = (i - 1) / 2; // 交换后，当前元素跑到父节点位置，继续向上比
    }
}

heapify：向下调整

先找左右孩子里的 “最大值”，再和当前元素比较，若孩子更大就交换，直到当前元素更大或没有孩子。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


public static void heapify(int[] arr, int i, int size) {
    int l = i * 2 + 1; // 左孩子索引
    while (l < size) { // 只要有左孩子，就继续循环
        // 1. 选左右孩子中的最大值（若有右孩子，且右孩子>左孩子，则选右）
        int best = (l + 1 < size && arr[l + 1] > arr[l]) ? l + 1 : l;
        // 2. 比较“最大值”和当前元素，选更大的那个
        best = arr[best] > arr[i] ? best : i;
        // 3. 若当前元素已是最大，说明堆结构ok，退出
        if (best == i) break;
        // 4. 否则交换，继续向下沉
        swap(arr, best, i);
        i = best; 
        l = i * 2 + 1; 
    }
}

方式一：heapSort（从顶到底建堆）

把数组当 “空堆”，逐个元素插入堆尾，用 heapInsert 向上调整

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


public static void heapSort(int[] arr) {
    int n = arr.length;
    // 从顶到底建堆
    for (int i = 0; i < n; i++) {
        heapInsert(arr, i); 
    }
    // 排序（反复交换堆顶和堆尾，向下调整）
    int size = n; 
    while (size > 1) {
        // 交换堆顶（最大值）和堆尾元素，最大值放到最终位置
        swap(arr, 0, --size);
        // 堆顶元素变了，向下调整维持大根堆
        heapify(arr, 0, size);
    }
}

方式二：heapSort（从底到顶建堆）

从 “最后一个非叶子节点” 开始，用 heapify 向下调整，直到堆顶。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


public static void heapSort2(int[] arr) {
    int n = arr.length;
    // 从底到顶建堆（从最后一个节点开始，向下调整）
    for (int i = n - 1; i >= 0; i--) {
        heapify(arr, i, n); 
    }
    // 排序
    int size = n;
    while (size > 1) {
        swap(arr, 0, --size);
        heapify(arr, 0, size);
    }
}

代码

链接：https://pan.quark.cn/s/d943e41053e1

提取码：XzdV