..堆..

堆

堆是完全二叉树，即除了最后一列之外，上面的每一层都是满的（左右严格对称且每个节点都满子节点）
最后一列从左向右排序。

默认大根堆：每一个节点都大于其左右儿子，根节点就是整个数据结构的最大值
priority_queue<int, vector<int>, less<int>> q;或者priority_queue<int> q;
小根堆：每一个节点都小于其左右儿子，根节点就是整个数据结构的最小值
priority_queue<int, vector<int>, greater<int>> q;

题目：838. 堆排序 - AcWing题库

题解：

本题使用使用小根堆。
heap[]表示模拟整个树的数组，size表示整个数组的长度
up(x),down(x)来维护整个二叉树。up将小的值上浮，down将大的值下沉；（都是递归的思想）
1.插入一个数heap[ ++ size] = x ;up(size)。先将其插入到最后一列，然后向上上浮

2.求集合当中的最小值 heap[1]

3.删除最小值 heap[1]=heap[size];size--;down(1)
4.删除任意一个元素 heap[k]=heap[size];size--;up(k);down(k)。（不是上升就是下沉，堆只会执行一个操作。当执行up(）操作时说明k代表的数值较小，所以会上浮，那么就一定不会down()（下沉））;
5.修改任意一个元素heap[k]=x;down[k];up[k];
（4、5。stl（优先队列）不可直接实现）
用一维数组来存，下标从1开始。（左右节点2x，2x+1。若从0开始，那一开始的左节点等于根节点了）

代码：

本体的暴力解法可以直接sort( )，在这里不再给出。

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;
int heap[N],ans;

void down(int x)
{
    int u=x;
    if(x*2<=ans && heap[u]>heap[2*x]) u=2*x;
    if(2*x+1<=ans && heap[u]>heap[2*x+1]) u=2*x+1;
    //如果不相等就代表根节点不是最小的（此时根节点数组对应的下标已经被子节点的下标覆盖）
    if(u!=x)
    {
        //交换值，使根节点变成最小的
        swap(heap[x],heap[u]);
        down(u);
    }
}
int main()
{
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> heap[i];
    ans=n;
    //构建二叉树
    for(int i=n/2;i;i--) down(i);

    while(m--)
    {
        cout << heap[1] << " ";
//输出完后，依照本题，根节点就没用了，需要删掉，然后输出下一次的根节点
//让根节点等于本二叉树中最大的值
        heap[1]=heap[ans];
//整个二叉树的长度减一
        ans--;
//让根节点下沉
        down(1);
    }
}