AcWing 838. 堆排序

堆排序

# 堆是一棵二叉树 或是一棵 [[完全二叉树]]

这里是小根堆（性质：每一个点都是小于等于左右儿子的）

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int n, m;
int h[N], cnt;

void down(int u){
    int t = u;
    if(u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(u != t){
        swap(h[u], h[t]);
        down(t);
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &h[i]);
    cnt = n;
    for(int i = n / 2; i; i--) down(i);
    while(m--){
        printf("%d ", h[1]);
        h[1] = h[cnt];
        cnt--;
        down(1);
    }
    return 0;
}

![[Pasted image 20221221111241.png]]
![[Pasted image 20221221111338.png]]

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int n, m;
int h[N], si;

void down(int u){
    int t = u;
    if(u * 2 <= si && h[u * 2] < h[t]) t = u * 2;//和左下节点比较
    if(u * 2 + 1 <= si && h[u * 2 + 1] < h[t]) t = u * 2 + 1;//和右下节点比较
    if(u != t){
        swap(h[u], h[t]);
        down(t);//递归循环down
    }//此时判断堆顶是不是最小值
}

void up(int u){
    while(u / 2 && h[u / 2] > h[u]){
        swap(h[u / 2], h[u]);
        u /= 2;
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &h[i]);
    si = n;
    
    for(int i = n / 2; i; i--) down(i);
    
    while(m--){
        printf("%d ", h[1]);
        h[1] = h[si];
        si--;
        down(1);
    }
    
    return 0;
}

# i 为什么从 n/2 开始 down？

我认为从 n/2 开始，还有一个角度可以理解，因为 n 是最大值，n/2 是 n 的父节点，因为 n 是最大，所以 n/2 是最大的有子节点的父节点，所以从 n/2 往前遍历，就可以把整个数组遍历一遍
1.n/2:就是从最后一个有儿子节点的父节点向前遍历，依次让每个结点找到其合适的位置
2.down(x)是一个递归函数，其含义是为一个相对‘大’的数向下找到其在树中合适的位置，递归式理解的关键

# 首先要明确要进行 down 操作时必须满足左儿子和右儿子已经是个堆。

开始创建堆的时候，元素是随机插入的，所以不能从根节点开始 down，而是要找到满足下面三个性质的结点：
1. 左右儿子满足堆的性质。
2. 下标最大（因为要往上遍历）
3. 不是叶结点（叶节点一定满足堆的性质）
那这个点为什么时 n/2？看图。

![[Pasted image 20221221114731.png]]