堆排序

堆排序概述

我们当然可以用$stl$自带的优先队列写堆排序，不过我们这里采用数组模拟二叉堆运算

数组模拟树的缺点是容易造成空间浪费，不过二叉堆是完全二叉树，所以不会浪费特别多，最多浪费一半空间

下面写的都是小根堆

组成

$h$[ ]存数据,$cnt$表示堆的大小

    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);
    }
}

上滤

堆的某一个元素，从当前位置，不断向上调整，让沿路的子树都满足堆的性质

从当前结点溯流而上，遇到不满足的时候，就交换

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

常见操作

1. 堆的插入

在堆的最后补充一个元素，然后进行上滤操作

2. 删除最小值

将最后一个元素覆盖第一个元素，然后进行下滤操作

3. 堆的构造

我们当然可以去每一个元素挨个插入去构造，不过这样时间复杂度是$n log n$的

有一个$O(n)$的建堆方式，也就是从树的倒数第二层，依次向上执行下滤操作，每次操作都保证了以当前结点为根的子树满足堆的要求

for (int i = n / 2; i; i -- ) down(i);

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

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 -- ];
        down(1);
    }

    puts("");

    return 0;
}