[!info] related notes 算法面试题型 MOC

堆与堆排序（Heap / Heap Sort）

堆是什么

堆通常指“二叉堆”：一棵完全二叉树，用数组紧凑表示。

• 大根堆：父节点 >= 子节点（堆顶是最大值）
• 小根堆：父节点 <= 子节点（堆顶是最小值）

数组下标关系

对下标 i：

• parent = (i - 1) / 2
• left = i * 2 + 1
• right = i * 2 + 2

两个基本操作

heapInsert（向上调整）

当你在末尾插入新元素后，向上与 parent 交换，直到满足堆性质。

单次复杂度：$O(\log n)$。

heapify（向下调整）

当堆顶变小/变大导致堆性质破坏时，从根向下与更优的子节点交换，直到满足堆性质。

单次复杂度：$O(\log n)$。

Java Template (Max-Heap + Heap Sort)

import java.util.*;

public class HeapSort {
    static void heapInsert(int[] arr, int i) {
        while (i > 0 && arr[i] > arr[(i - 1) / 2]) {
            swap(arr, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    static void heapify(int[] arr, int i, int size) {
        int l = i * 2 + 1;
        while (l < size) {
            int best = (l + 1 < size && arr[l + 1] > arr[l]) ? (l + 1) : l;
            best = arr[best] > arr[i] ? best : i;
            if (best == i) break;
            swap(arr, best, i);
            i = best;
            l = i * 2 + 1;
        }
    }

    static void heapSortTopDown(int[] arr) {
        if (arr == null || arr.length < 2) return;
        for (int i = 0; i < arr.length; i++) heapInsert(arr, i);
        int size = arr.length;
        while (size > 1) {
            swap(arr, 0, --size);
            heapify(arr, 0, size);
        }
    }

    static void heapSortBottomUp(int[] arr) {
        if (arr == null || arr.length < 2) return;
        for (int i = (arr.length - 1) / 2; i >= 0; i--) heapify(arr, i, arr.length);
        int size = arr.length;
        while (size > 1) {
            swap(arr, 0, --size);
            heapify(arr, 0, size);
        }
    }

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

堆排序

方案 A：从顶到底插入建堆

依次插入元素，每次 heapInsert。

• 建堆：$O(n\log n)$

方案 B：从底到顶建堆（Floyd）

从最后一个非叶子节点开始，对每个节点 heapify。

• 建堆：$O(n)$

排序阶段

重复：交换堆顶与末尾，缩小 size，再 heapify。

• 排序：$O(n\log n)$
• 额外空间：$O(1)$（不算递归）