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

堆与堆排序（Heap / Heap Sort）

堆是什么

这里讨论二叉堆：一棵完全二叉树，用数组紧凑表示。优先队列是按优先级取出元素的抽象接口，二叉堆是其常见实现，不是同一层概念；它也不同于运行时内存管理中的堆。

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

数组下标关系

对下标 i：

• parent = floor((i - 1) / 2)，只对 i > 0 求父节点
• 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 / 2 - 1; 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)，因为大多数节点靠近叶子，不是 n 个节点都需要下沉 log n 层

排序阶段

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

• 排序：$O(n\log n)$
• 本例全程迭代，额外空间 O(1)，会修改原数组
• 大根堆的堆顶依次放到末尾，最终得到升序数组；堆本身不保证兄弟节点或整个数组有序
• 常规堆排序不稳定，相等键的原顺序可能变化