[数据结构与算法]数据结构：堆排序—堆

简单版堆C++模板：

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
int h[N], size;

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

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

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

简单版堆理解：

堆其实是完全二叉树的形状，但是我们用一维数组来保存（注意下标从1开始）
这样就有一个性质：
x的左儿子就是x*2 x的右儿子就是x*2+1

堆的作用就是头节点就是最小值（小根堆）
手写堆有哪些操作：
1.插入一个数：h[++size]=x,up(size);
2.求最小值：h[1]
3.删除最小值：h[1]=h[size–] , down(1);
4.删除任意值：h[k]=h[size–] , down(k),up(k)
5.修改任意值：h[k]=x,down(k),up(k)

建堆为啥从n/2的位置开始down？
因为n/2到1都是非叶子结点，如果是叶子结点，那么就是最底层则不需要down，那么从倒数第二层开始down就会将整个堆进行排序了。

题目： AcWing 838. 堆排序
输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。

输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数，表示整数数列。

输出格式
共一行，包含 m 个整数，表示整数数列中前 m 小的数。

数据范围
1≤m≤n≤10⁵，
1≤数列中元素≤10⁹

输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010;
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()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>h[i];
    cnt=n;
    
    for(int i=n/2;i>=1;i--)down(i);
    
    while(m--)
    {
        cout<<h[1]<<' ';
        h[1]=h[cnt--];
        down(1);
    }
    return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖