考研笔记

板子：堆排序

下标从 1 开始（和教材、手算一致）：结点 的孩子是 、，双亲是 。建大根堆：从 往前逐个向下调整。排序：每趟把堆顶（最大）换到末尾，再把剩下的调整成堆。

代码

void HeadAdjust(int A[], int k, int len) {   // 把以 k 为根的子树调整成大根堆（它的左右子树已经是堆）
    A[0] = A[k];                             // A[0] 暂存要往下筛的元素
    for (int i = 2 * k; i <= len; i *= 2) {  // i 指向 k 的左孩子，沿较大的孩子一路往下
        if (i < len && A[i] < A[i + 1]) i++; // i < len 说明右孩子存在；取两个孩子中较大的
        if (A[0] >= A[i]) break;             // 不比较大的孩子小：位置找到了
        A[k] = A[i];                         // 较大的孩子上移，填到 k
        k = i;                               // k 下移，继续往下筛
    }
    A[k] = A[0];                             // 放到最终位置
}
 
void BuildMaxHeap(int A[], int len) {
    for (int i = len / 2; i >= 1; i--)       // 从最后一个分支结点 ⌊len/2⌋ 开始，往前逐个调整
        HeadAdjust(A, i, len);
}
 
void HeapSort(int A[], int len) {            // 堆排序：A[1..len] 排成升序
    BuildMaxHeap(A, len);
    for (int i = len; i > 1; i--) {          // 一共 len-1 趟
        int t = A[i]; A[i] = A[1]; A[1] = t; // 堆顶（最大）和堆底交换：最大的放到最终位置
        HeadAdjust(A, 1, i - 1);             // 剩下的 i-1 个重新调整成堆
    }
}
 
void HeapInsert(int A[], int &len, int x) {  // 大根堆插入：先放到堆底，再往上调
    A[++len] = x;
    for (int i = len; i > 1 && A[i / 2] < A[i]; i /= 2) {   // 比双亲大，就和双亲交换
        int t = A[i]; A[i] = A[i / 2]; A[i / 2] = t;
    }
}

复杂度：建堆 ；排序最好、平均、最坏都是 ；空间 。不稳定。

例（教材图 8.6）：53 17 78 09 45 65 87 32 建堆后是 87 45 78 32 17 65 53 09。输出堆顶 87 以后（把 09 换上来再调整），剩下的是 78 45 65 32 17 09 53。

关键边界

代码为什么
下标从 1 开始，A[0] 不存数据孩子是 2k、2k+1，公式最简单；A[0] 正好拿来暂存。下标从 0 开始的话，孩子是 2k+1、2k+2
i < len 才看右孩子i == len 时只有左孩子，A[i+1] 已经不在堆里了
建堆从 len / 2 开始大于 的都是叶子，本身就是堆
HeadAdjust(A, 1, i - 1)交换后 A[i] 已经是最终位置，堆的大小变成 i - 1
A[0] >= A[i] 就停相等时不用再往下换，少移动一次

易错点

  • 手算最容易漏的是连锁下沉：交换一次以后，被换下去的元素可能又比新位置的孩子小，要一路调到底。
  • 小根堆就是把比较全部反过来：A[i] > A[i + 1] 时 i++，A[0] <= A[i] 时停。
  • 三个 排序的空间：堆排序 、快排 、归并 ，选择题常考这一组对照。

链接

反向链接