堆

1、性质

1.1 堆中某个节点的值总是不大于或不小于其父节点的值；(最小堆，最大堆)
1.2 是一棵完全二叉树。

2、基本操作

2.1 down操作：

void down(int x){
    int u=x;
    if(x*2<=n&&a[x*2]<a[x])
        u=2*x;
    if(x*2+1<=n&&a[x*2+1]<a[u])
        u=2*x+1;
    if(u!=x){
        swap(a[u],a[x]);
        down(u);
    }
}

2.2 up操作：

void up(int x){
    while(x/2&&b[x]<b[x/2]){
        heap_swap(x,x/2);
        x>>=1;
    }
}

3、例题

3.1 题目：堆排序

输入一个长度为n的整数数列，从小到大输出前m小的数。
输入格式
第一行包含整数n和m。
第二行包含n个整数，表示整数数列。
输出格式
共一行，包含m个整数，表示整数数列中前m小的数。

#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
int a[100010];

void down(int x){
    int u=x;
    if(x*2<=n&&a[x*2]<a[x])
        u=2*x;
    if(x*2+1<=n&&a[x*2+1]<a[u])
        u=2*x+1;
    if(u!=x){
        swap(a[u],a[x]);
        down(u);
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)   
        scanf("%d",&a[i]);
    
    for(int i=n/2;i;i--){
        down(i);
    }

    while(m--){
        cout<<a[1]<<" ";
        swap(a[1],a[n]);
        n--;
        down(1);
    }
    return 0;
}