什么是堆

堆是一种数据结构。而且堆可以表示为一棵树。当然，堆也有不同种类的堆，分别为小根堆与大根堆。

• 小根堆：子节点比父节点大
  
• 大根堆：子节点比父节点小
  

堆的维护

我们需要维护堆，才能保证堆的性质。由于堆是一种数据结构。所以我们要考虑他的存入，读取，与弹出。

存入

首先，我们需要将我们的信息存入到我们的堆中。这个时候思考的问题应该是我该存到哪里，怎样存才能不破坏堆的性质？

最好的方式是就是从下往上调堆，从而做到不破坏堆的性质。这样的时间复杂度就是$O(logn)$。我们来实践一下。我们举大根堆为例。我们先定义$tree$数组存储每个节点上的数值，并且其中已经包含了一个已经定义好了的堆。我们要插入一个值x。首先，我们要将这个值x插入到堆的最后一个位置。其次，我们要知道二叉树的性质-每个子节点($children$)的父节点($parent$)就应为$\lfloor children / 2 \rfloor$。然后，找到了父节点。比较这两个节点上的值，若$tree[children]$大于（小根堆为小于）$tree[parent]$，证明此时不符合要求。所以交换两个节点并继续向上找不符合堆的性质的位置关系。此时，我们也可能发现$tree[children]$与$tree[parent]$的值符合性质(与上面不符合性质的原因正好相反)。这个时候我们可以直接跳出整个调堆过程。因为不会再存在不符合要求的了。原因：因为我们一开始的堆就是一个满足性质的堆，而每次插入一个值，只会影响部分区域并不会全部影响。所以当满足性质时。再往上找就没意义了。

读取

正常情况下，我们只需要读取整个堆的根节点的数值就行了，（其他数值取出来也没啥用）所以这个就比较简单，我们直接读出第一个数值就行。即$tree[1]$。时间复杂度$O(1)$

弹出

从堆顶弹出一个数的方法是将堆顶与堆尾交换。然后从第一个开始向下进行调堆操作。这个时候我们的孩子节点就是$parent * 2$(二叉树性质)。其次我们需要特判，看一下右子树是否满足要求。然后再往下进行调堆。如果已经符合要求就停止。详细可以看例题的代码。

堆这个东西的细节还是挺多的。一定要注意，否则容易失去笑容。

代码

我们以Luogu-P3378为例。

手写堆 代码：

#include <iostream>
#include <cstring>
#include <stack>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

int tree[1000001];

int number = 0;

void push(int x)
{
    number ++;
    tree[number] = x;
    int nb = number;
    while(nb > 1)
    {
        int nxt = nb / 2;
        if(tree[nxt] > tree[nb])
        {
            swap(tree[nxt], tree[nb]);
            nb = nxt;
        }
        else
        {
            return ;
        }
    }
}

int top()
{
    return tree[1];
}

int pop()
{
    swap(tree[1], tree[number]);
    number --;
    int tis = 1, nxt = 0;
    while(tis * 2 <= number)
    {
        nxt = tis * 2;
        if(nxt + 1 <= number &&  tree[nxt + 1] < tree[nxt] )
        {
            nxt ++;
        }
        if(tree[nxt] < tree[tis])
        {
            swap(tree[nxt], tree[tis]);
            tis = nxt;
        }
        else
        {
            break;
        }
        
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    int t = n;
    while(t -- )
    {
        int opt;
        scanf("%d", &opt);
        push(opt);
    }
    for(int i = 1; i <= n; i ++ )
    {
        printf("%d ", top());
        pop();
    }
    return 0;
}

当然，STL里有很多函数以及类。优先队列不能否认是可以使用的。

STL-优先队列:

#include <iostream>
#include <queue>
using namespace std;
priority_queue <int,vector<int> ,greater<int>> q;
int main()
{
   int n;
   cin>>n;
   for(int i=1;i<=n;i++)
   {
       int x,y;
       cin>>x;
       if(x==1)cin>>y;
       if(x==1)q.push(y);
       if(x==2)cout<<q.top()<<endl;
       if(x==3)q.pop();
   }
    return 0;
}

当然，STL-algorithm里面还有一个heap的东西，也是可以实现的，不过没试过，就不写了（简称咕咕咕）

关于事件复杂度 2020.08.10

所以、手写堆可能会更快一点。

感谢您的阅读~