手写堆

1. 插入一个数
2. 求集合中的最小值
3. 删除最小值
4. 删除任意元素
5. 修改任意元素

堆是一个完全二叉树

除了最后一层节点外，上面每层节点都是满的(都有左右儿子)

最后一层节点从左到右依次排列

小根堆性质：每个点小于等于左右儿子，根节点是整个树中最小值

堆的存储

1. down(x)将节点下移

从三个点里面找到一个最小值，交换6，3

```

```

1. up(x)一个数变小了，往上走

只需要比较父节点

1. 插入

   在堆最后一个位置插入x,不断上移

   c++ head[++ size] = x，up(x)

2. 求最小值

   heap[1]

3. 删除最小值

   堆顶等于最后一个节点，然后删除最后一个节点。

   因为删除随后一个节点很方便

   heap[1] = heap[size], size --; down(1)

4. 删除任意元素

   heap[k] = heap[size], size --; 法一 if(heap[k]变大) down if(heap[k]变小) up 法二 无脑 down(k)； up(k);//只会执行一个

5. 修改任意元素

   heap[k] = x; down(k); up(k);

O(n)建堆

最后一个非叶子节点的位置开始down

838. 堆排序 - AcWing题库

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], sizes;

void down(int u)
{
    int t = u;//t表示三个点里面的最小值
    if(u * 2 <= sizes && h[u * 2] < h[t]) t = u * 2;//左儿子小于t 
    if(u* 2 + 1 <= sizes && h[u * 2 + 1] < h[t]) t = u * 2 + 1;// 右儿子小于t
    if(u != t)//根节点不是最小值
    {
        swap(h[u], h[t]);
        down(t);
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        cin >> h[i];
    sizes = n;
    //建堆
    for(int i = n / 2; i; i --) down(i);
    while (m -- )
    {
        cout << h[1] << " \n"[m == 0];
        h[1] = h[sizes];
        sizes --;
        down(1);
    }
    return 0;
}

STL 堆

prioirty_queue默认大根堆

#include <bits/stdc++.h>
using namespace std;
priority_queue<int, vector<int>, greater<int>> hp;
int n, m;

int main()
{
    cin >> n >> m;
    while (n -- )
    {
        int x;
        cin >> x;
        hp.push(x);
    }

    while(m --)
    {
        cout << hp.top() << " ";
        hp.pop();
    }

    return 0;
}