堆 | 定义、操作、堆排序

参考：胡凡，曾磊《算法笔记》

定义

堆是一棵完全二叉树。

• 完全二叉树：结点数量n，叶子结点数ceiling（n/2）

树中每个结点的值都不小于（或不大于）其左右孩子结点的值。

• 若所有结点值都有父>=子，称为 大顶堆。这时每个结点都是以它本身为根的树的最大结点。
• 若所有结点值都有父<=子，称为 小顶堆。这时每个结点都是以它本身为根的树的最小结点。

应用

• 优先队列的实现
  默认使用 大顶堆

操作 & 实现

堆是一棵完全二叉树，用数组可实现。（下标【1，n】）

给定初始序列建堆 O（n）

• 将初始序列按照层序排成一棵完全二叉树。
• 从下往上，从右往左，找到第一个非叶子结点，自上而下调整，范围是下标【1，floor（n/2）】。追着这一个结点调整，每次调整后再检查他和孩子结点的大小是否还需调整，直到不需调整/没有孩子结点。
• 然后找下一个非叶子结点，重复第二步……
• 一直到完成根结点的调整。

⚠️倒着枚举、调整：保证每个结点都是以其为根结点的子树的权值最大结点。

删除堆顶元素 O（log n）

用最后一个结点覆盖堆顶元素，结点数减1，自上而下调整根结点。

添加一个元素x O（log n）

结点数加1，把x放在数组最后，从x自下而上调整。

• 向上调整的写法
  upAdjust(int low = 1, int high)
  low为1（堆顶下标），high是x下标。
  追着x，始终与父亲结点比较，若x比父亲结点大，则交换。
  直到到达堆顶或父亲结点权值较大。

堆排序

• 首先建堆，堆顶为最大元素。
• 倒着遍历数组，直到堆中剩下一个元素。
  当前遍历到下标i，交换堆顶元素与元素i，对堆顶作向下调整，范围【1，i - 1】，堆结点数减1。
  相当于不断去掉当前最大值—堆顶元素。

⚠️我实现时踩的坑

• ⚠️downAdjust函数的参数应该是当前调整的下标起点low和下标终点high。
• downAdjust函数中lc，rc都要及时更新！！！（只更新lc什么鬼啊，给自己跪了orzzzzzzzzz
• 建堆时调用向下调整，第二个参数始终是堆的结点数。但堆排序时，堆的结点数每次迭代减1。

例

1098 Insertion or Heap Sort (25 分)

判断排序的中间结果是使用插入排序还是堆排序得到的，并输出下一次迭代后的序列。
本题使用了最大堆。

#include <cstdio>
#include <algorithm>

using namespace std;
int origin[105], partial_sorted[105], temp_seq[105];
int nn;

bool isSame(const int a[], const int b[]) {
    for (int i = 1; i <= nn; ++i)
        if (a[i] != b[i]) return false;
    return true;
}

void downAdjust(int curr, int high) {
    int lc = 2 * curr, rc = 2 * curr + 1, larger_index;
    while (lc <= high) {
        if (rc <= high && origin[rc] > origin[lc]) { // has rc
            larger_index = rc;
        } else larger_index = lc;
        if (origin[larger_index] > origin[curr]) { //存在比自身大的孩子
            swap(origin[larger_index], origin[curr]);
            curr = larger_index;
            lc = 2 * curr;
            rc = lc + 1; // update lc,rc
        } else break; //curr就是以自己为根子树的最大结点
    }
}

void buildHeap() {
    for (int i = nn / 2; i >= 1; --i) {
        downAdjust(i, nn);
    }
}

int main() {
    scanf("%d", &nn);
    for (int i = 1; i <= nn; ++i) {
        scanf("%d", &origin[i]);
        temp_seq[i] = origin[i];
    }
    for (int i = 1; i <= nn; ++i) {
        scanf("%d", &partial_sorted[i]);
    }
    // InsertionSort or N
    for (int i = 2; i < nn; ++i) {
        sort(temp_seq + 1, temp_seq + i + 1);
        if (isSame(temp_seq, partial_sorted)) {
            puts("Insertion Sort");
            sort(temp_seq + 1, temp_seq + i + 2);
            for (int j = 1; j < nn; ++j)
                printf("%d ", temp_seq[j]);
            printf("%d\n", temp_seq[nn]);
            return 0;
        }
    }
    buildHeap();
    for (int i = nn; i >= 3; --i) {
        swap(origin[1], origin[i]);
        downAdjust(1, i - 1);
        if (isSame(origin, partial_sorted)) {
            puts("Heap Sort");
            swap(origin[1], origin[i - 1]);
            downAdjust(1, i - 2);
            for (int j = 1; j < nn; ++j)
                printf("%d ", origin[j]);
            printf("%d\n", origin[nn]);
            return 0;
        }
    }
    return 0;
}