概览：

前置知识：无

堆结构

完全二叉树和数组前缀范围来对应，大小，单独的变量size来控制

i的父亲节点：(i-1)/2，i的左孩子：i*2 + 1，i的右孩子：i*2 + 2

堆的定义（大根堆、小根堆），本节课讲解按照大根堆来讲解，小根堆是同理的。

堆的调整：heapInsert（向上调整）、heapify（向下调整）

heapInsert、heapify方法的单次调用，时间复杂度O(log n)，完全二叉树的结构决定的

堆排序

A. 从顶到底建堆，时间复杂度O(n * log n)，log1 + log2 + log3 + … + logn -> O(n*logn)

或者用增倍分析法：建堆的复杂度分析+子矩阵数量的复杂度分析

B. 从底到顶建堆，时间复杂度O(n)，总代价就是简单的等比数列关系，为啥会有差异？简单图解一下

C. 建好堆之后的调整阶段，从最大值到最小值依次归位，时间复杂度O(n * log n)

时间复杂度O(n * log n)，不管以什么方式建堆，调整阶段的时间复杂度都是这个，所以整体复杂度也是这个

额外空间复杂度是O(1)，因为堆直接建立在了要排序的数组上，所以没有什么额外空间

注意：堆结构比堆排序有用的多，尤其是和比较器结合之后。后面几节课会重点讲述。

堆结构

大根堆定义

完全二叉树和数组前缀范围来对应，大小是由单独的变量size来控制

如下，有一个预先准备的数组：

[                        --值   ]  size = 0
 0 1 2 3 4 5 6 7 8 9 10  --下标

例如：

[a b c d e f g                     ]  size = 7
 0 1 2 3 4 5 6 7 8 9 10

          0:a
        /     \
     1:b        2:c
     /  \      /   \
    3:d  4:e  5:f  6:g 

对于每一个节点（其索引是i），计算其父节点的索引就是(i - 1) / 2，其中0位置的父亲根据这个公式计算得到：(0 - 1) / 2 = -1/2 =0(注意在Java中等于0)，所以认为0节点的父亲也就是他自己。

同理，每个节点左孩子是2*i+1，右孩子是2*i+2，但是这些计算出来的左右孩子的索引值，必须收size管控，否则size就没有意义了

堆的定义（大根堆、小根堆），本节课讲解按照大根堆来讲解，小根堆是同理的。

大根堆定义：任何一个子结构，最大值在顶部

例如初始状态下，数组size= 1，有一个元素5

[ 5                ]  size = 1
  0 1 2 3 4 5 6

插入一个元素6

[ 5 6               ]  size = 1
  0 1 2 3 4 5 6

此时，完全二叉树长这样：

          0:5
        /     
     1:6        

显然此时不满足大根堆的定义，需要进行heapInsert()操作

所以，需要每次新进来一个节点，和其父节点比较（其中父节点索引就是(i - 1) / 2）

如果比父节点大，就需要进行交换，而且交换完之后需要再往上对比，一直到自己不比自己的父亲大（相等也不用交换）。

heapInsert向上操作

下面是heapInsert()的代码：

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

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

上面代码如果来到0位置也会停止，因为0位置的数不比0位置的数大。

这就是向上调整的过程。

heapify向下调整

还有向下调整：heapify()操作。heapify 是从某个节点开始向下调整，确保该子树满足大根堆性质。

举例：初始数组为 [4, 10, 3, 5, 1]，我们要将其转化为大根堆。数组下标从 0 开始：

数组: [4, 10, 3, 5, 1]
下标:  0   1  2  3  4
对应的树:
       4
      / \
     10  3
    /  \
   5    1

索引 0 (4)：左子节点 = 2×0+1=1 (10)，右子节点 = 2×0+2=2 (3)

这不是大根堆，因为 4 < 10。

所以10与4交换（注意要比较4的两个孩子，哪个更大哪个和4交换）

数组: [10, 4, 3, 5, 1]
下标:  0   1  2  3  4
       10[0]
      /    \
     4[1]  3[2]
    /    \
  5[3]   1[4]

此时4的左子节点：2×1+1=3 (5)，右子节点：2×1+2=4 (1)

所以4和自己更大的孩子交换

数组: [10, 5, 3, 4, 1]
下标:  0   1  2  3  4
       10[0]
      /    \
     5[1]  3[2]
    /    \
   4[3]  1[4]

这最终是一个大根堆。

所以：heapify 从上向下调整，每次将当前节点与其子节点比较，交换到更大的子节点位置。

任意i位置的数只要变小了都可以用heapify功能，向下调整，最终满足大根堆的定义。

heapify代码如下

public void heapify(int[] arr, int i, int size) {
    int l = i * 2 + 1;
    while (l < size) { // l < size 有左孩子
        int best = i + 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;
    }
}

时间复杂度分析

如果是1层，就是1个节点

如果是2层，就是3个节点

如果是3层，就是7个节点

如果是4层，就是15个节点

以此类推

如果是n个节点应该是\(log_2(n + 1)\)向上取整，得到层数

简单来说，就是logN，如果是N个节点的话。

对于一个堆来说，如果一个堆节点一共是N个，得到其高度是logN，那么不管是向上调整还是向下调整，都是logN的时间复杂度。

即上面两个方法heapInsert(向上调整)和heapify(向下调整)都是logN的时间复杂度。这个时间复杂度是完全二叉树的结构决定的

上述提到的堆结构都是由数组实现的。

堆排序

从顶到底建立大根堆

首先按照heapInsert操作，将大根堆建立好：比如有下面的数组

int[] arr = [5, 6, 3, 1, 9, 2, 4, 6];

依次画出整个建立大根堆的过程：

现在建立完大根堆之后，数组变成了：

[9, 6, 4, 6, 5, 2, 3, 1]
 0  1  2  3  4  5  6  7   下标

但是这肯定不是最终有序的状态。还需要其他操作。

首先数组最大的元素肯定是大根堆的顶部，即0位置的数。

然后将索引7和索引0位置的数交换位置，并且size--

[1, 6, 4, 6, 5, 2, 3, 9]  size = 7
 0  1  2  3  4  5  6     下标

此时在堆中的数只有数组中下标0～6的数。

将剩余的 n-1 个元素重新调整为堆，即执行向下调整操作（heapify操作），直到堆的大小为 1。

即，堆排序的步骤是将根节点（最大元素）与堆的最后一个元素交换，然后减少堆的有效大小 (size--)，再通过 heapify 操作恢复堆的性质。

对于上面整个过程，建堆过程是由上至下（从顶到底建立大根堆），时间复杂度是O(NlogN)，而每次弹出最大值之后，调整堆的时间复杂度为 O(Nlog n)，整体时间复杂度O(N * log N)。

空间复杂度是O(1)。堆排序是一种原地排序算法，只需要常数级别的额外空间。

代码如下：

// 从顶到底建立大根堆O(NlogN)
// 依次弹出最大值，然后排好序O(NlogN)
// 总的时间复杂度O(NlogN)
public void heapSort1(int[] arr, int n) {
    for (int i = 0; i < n; i++) {
        heapInsert(arr, i);
    }
    int size = n;
    while (size > 1) {
        swap(arr, 0, --size);
        heapify(arr, 0, size);
    }
}

从底到顶建立大根堆

从底到顶建立大根堆O(N)，依次弹出堆内最大值并排好序O(N * log N)，整体时间复杂度O(N * log N)

代码如下：

// 自底到顶建立大根堆O(N)
// 依次弹出最大值，然后排好序O(NlogN)
// 总的时间复杂度O(NlogN)
public void heapSort2(int[] arr, int n) {
    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://www.luogu.com.cn/problem/P1177

注意处理输入与输出：

import java.io.*;

public class HeapOperation1 {

    // 向上调整大根堆
    public static void heapInsert(int[] arr, int i) {
        while (arr[i] > arr[(i - 1) / 2]) {
            swap(arr, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    // 向下调整大根堆,当前堆的大小为size
    public 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, i, best);
            i = best;
            l = i * 2 + 1;
        }
    }

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

    // 从顶到底建立大根堆O(NlogN)
    // 依次弹出最大值，然后排好序O(NlogN)
    // 总的时间复杂度O(NlogN)
    public static void heapSort1() {
        for (int i = 0; i < n; i++) {
            heapInsert(arr, i);
        }
        int size = n;
        while (size > 1) {
            swap(arr, 0, --size);
            heapify(arr, 0, size);
        }
    }

    // 自底到顶建立大根堆O(N)
    // 依次弹出最大值，然后排好序O(NlogN)
    // 总的时间复杂度O(NlogN)
    public static void heapSort2() {
        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);
        }
    }




    public static int MAXN = 100001;

    public static int[] arr = new int[MAXN];

    public static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        n = (int) in.nval;
        for (int i = 0; i < n; i++) {
            in.nextToken();
            arr[i] = (int) in.nval;
        }
        //heapSort1();
        heapSort2();
        for (int i = 0; i < n - 1; i++) {
            out.print(arr[i] + " ");
        }
        out.println(arr[n - 1]);
        out.flush();
        out.close();
        br.close();
    }
}

倍增分析法

“增倍分析法”（也叫倍增分析法，英文常称为 doubling analysis 或 amortized analysis with doubling）是一种分析算法时间复杂度的技术，通常用于评估动态数据结构（如动态数组、摊还分析中的某些操作）的性能。它通过观察输入规模（或某种关键参数）增加一倍时，算法运行时间的变化来推导出复杂度。

增倍分析法基于一个核心思想：通过分析当问题规模（比如输入大小 n）翻倍时，算法的总运行时间如何变化，从而推导出平均或摊还时间复杂度。

以下是一个经典例子：动态数组的插入操作。

假设有一个动态数组，初始容量为 1，每次容量不足时，将数组大小翻倍（即 1, 2, 4, 8, …），然后将旧数组元素复制到新数组中，最后插入新元素。

如果数组未满，插入一个元素代价为 O(1)。

如果数组已满，需要：

分配新数组（大小翻倍）。
复制当前所有元素到新数组（代价与当前元素个数成正比）。
插入新元素。

初始容量 = 1，第 1 次插入：直接插入，代价 = 1。

第 2 次插入：容量满，扩展到 2，复制 1 个元素，插入新元素，代价 = 1 + 1 = 2。

第 3 次插入：容量未满，直接插入，代价 = 1。

第 4 次插入：容量满，扩展到 4，复制 2 个元素，插入新元素，代价 = 2 + 1 = 3。

第 5 次插入：容量未满，直接插入，代价 = 1。

…

第 8 次插入：容量满，扩展到 8，复制 4 个元素，插入新元素，代价 = 4 + 1 = 5。

扩展发生的时间点是插入第 2, 4, 8, 16, … 个元素时（\(2^k\)）。
每次扩展的复制代价分别是：1, 2, 4, 8, …。
总扩展代价 = \(1 + 2 + 4 + 8 + ... + 2^(k-1)\)，其中 \(2^k ≈ n\)。
这是一个等比数列，总和为：
\[S = 1 + 2 + 4 + \dots + 2^{k-1} = 2^k - 1 < 2n\]
加上 n 次插入本身的代价（每次 O(1)），总代价 < 2n + n = 3n。

通过增倍分析法，动态数组的每次插入操作的摊还时间复杂度是 O(1)，尽管单次最坏情况可能是 O(n)。

回到堆排序，假设我们分析自底向上建堆的时间复杂度，也可以用类似思路：

堆高度 h = log n。
每层节点数翻倍（从顶部到根部：1, 2, 4, …），但每层调整的代价随高度减少。
总代价 = Σ (层节点数 × 单节点调整代价) ≈ O(n)，这虽然不是直接的增倍分析，但体现了类似思想。

但堆排序的建堆通常直接用数学推导（O(n)），而动态数组这种场景更适合用增倍分析法。

025 堆结构与堆排序

堆是数组实现的完全二叉树，核心操作为向上(heapInsert)和向下(heapify)调整(O(log n))。堆排序先建堆（O(n)或O(n log n)），再交换堆顶并调整。整体时间复杂度O(n log n)，空间O(1)。堆结构本身比堆排序更有用。

堆结构