堆（heap）详解

Jr_Zlw · 2020-01-17 21:45:46 · 个人记录

堆就是一棵完全二叉树

堆算法的简介：

堆的主要作用就是是排序，分了大根堆和小根堆，大根堆顾名思义就是任何父节点都比\large{\text{它的}}子节点大的完全二叉树，小根堆反之。堆是为了能够很方便第找出或者更新一个一维数组的最大/小值。在一些找最大/小值的算法里就特别好用，而堆的算法的核心当然就是维护这个性质了（当然也可以使用STL中自带的函数，当然这个后面ge也会说）：

维护堆的操作：

\text{以小根堆为例}

1.上浮（push_up/float）

上浮指的是将任意一个节点从下向上挪并且保证小根堆性质不改变（即保证任何父节点都比\large{\text{它的}}子节点小），过程很简单，就是\large{\text{一步步}}地从下往上挪。注意：一定是一步步的，不能一下子从叶子节点变成根节点（不能一口吃个胖子）。既然是一步步的，交换当前的父节点和子节点即可完成！

\text{很简单吧，但还是证明一下不然我会怀疑}

那么为什么一步步挪就能满足条件呢，因为一个小根堆是肯定满足父节点比\large{\text{它的}}子节点小，所以如果新的节点A需要上浮(比如 A 是一个新插入的叶子节点）那么当它的父节点 B 比它大时，将 B 换为叶子节点，此时 B 没有儿子，满足条件。然后现在 A 的父节点是 C 那么肯定有 C<B，（因为 B 之前当子节点时是满足父节点比它的子节点小的），如果此时 A 有另一个子节点D，（即原来B的子节点）所以B<D，又因C<B，所以C<D，所以此时如果是 C 做它们的父节点不会破坏这一部分的性质，而 A 也是如此，因为 A<B,B<D，所以A<D。那么此时就可以随意地去比较 A,C 了，因此只要一步步地往上爬就能保留堆的原有性质不变。（~~我要一步一步往上爬~~~）

\text{只要不急，随你挪啦！}

那么上浮就很容易搞定了，完全二叉树最好的地方就是可以直接用int(\frac{i}{2})来表示一个点的父节点，在程序里就更方便了，自动帮你取整，所以代码就很容易实现了！

void push_up(int i)//将i点上浮 
{
     while(i>1)
     {
         if(heap[i]<heap[i>>1])
         {
            swap(heap[i],heap[i>>1]);
            i>>=1; 
         }
         else
         {
            return;
         }
     }
}

2.下沉（push_down/sink)

下沉一般是用来删除节点用的，比如你想要迫害一个中间的节点，你就可以让它下沉到底部，然后一刀剪掉(R.I.P)。这个比上浮还简单，因为下沉只要比较子节点中较小的一个并交换即可。

\text{还是证明一下：}

我们假设要迫害点 A，我们看到 A 有俩儿子BC且 B<C，因为此时如果用 C 来顶替 A 就会导致 C作为父节点应当比 B 小，然后我们已知B<C，所以我们只能选B，于是我们将 A 与 B 交换即可。然后设此时B有儿子 DE ,而我们选 min(D,E) 与 A 交换（设 D<E），那么因为 B 原本是它们的父亲，所以 B<D，将 D 换上去是毫无问题的。由此可得，只要选两个儿子中最小的那个交换即可满足咯！代码实现：

void push_down(int i)//将i点下沉 
{
    while((i<<1)<=n)
    {
        int next=(i<<1);
        if(heap[next]>heap[next+1]&&next+1<=n)next++;
        if(heap[next]<heap[i])swap(heap[i],heap[next]);
        else break;
        i=next;
    }
}

那么基本操作就到这里咯，然后还有STL的做法值得参考，先上代码（洛谷的堆模板）：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int heap[5000005],n;
void push_up(int i)//将i点上浮 
{
     while(i>1)
     {
         if(heap[i]<heap[i>>1])
         {
            swap(heap[i],heap[i>>1]);
            i>>=1; 
         }
         else
         {
            return;
         }
     }
}
void push_down(int i)//将i点下沉 
{
    while((i<<1)<=n)
    {
        int next=(i<<1);
        if(heap[next]>heap[next+1]&&next+1<=n)next++;
        if(heap[next]<heap[i])swap(heap[i],heap[next]);
        else break;
        i=next;
    }
}

void add(int i)//加值为i的点 
{
    heap[++n]=i;
    push_up(n);
}

void pop(int i)//删除处于i位置的点 
{
    swap(heap[i],heap[n--]);
    push_down(i);
}
//上面是堆操作，下面根据题目自行改变 
int main()
{
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        int ope,num;
        scanf("%d",&ope);
        switch(ope)
        {
            case 1:
                scanf("%d",&num);
                add(num);
                break;
            case 2:
                printf("%d\n",heap[1]);
                break;
            case 3:
                if(n>0)
                pop(1);
                break;
        }
    }
    return 0;
}

\large{\text{然后我们来看一下$STL$：}}

//优先队列身份证：

I.住址（头文件）：<queue>

II.座机电话（调用）：priority_queue<int>a;（大根堆）

III.手机电话（调用）：priority_queue<int,vector<int>,greater<int> > a;（小根堆）

IV.不动产（基本操作）：

  a.size():返回堆内元素个数;
  a.empty():如果堆为空，返回true，否则返回false;
  a.top():返回堆顶元素。
  a.pop():删除堆顶元素，保姆STL自动帮忙整理;
  a.push(x):插入一个元素x，同上自动整理。

注意！！！：

\text{结构体中比较某一变量}

struct node
{
    int compare,another;
    bool operator<(const node &x)const
    {
        return x.compare<compare
    }//小根堆，大根堆则将'<'改成'>'即可
};
priority_queue<node>q;

那么我们用优先队列来 A 一下模板（真的是......非常非常非常简单啊QAQ）：

#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
priority_queue<int,vector<int>,greater<int> > heap;//> >之间注意空格 
int main()
{
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        int ope,num;
        scanf("%d",&ope);
        switch(ope)
        {
            case 1:
                scanf("%d",&num);
                heap.push(num);
                break;
            case 2:
                printf("%d\n",heap.top());
                break;
            case 3:
                if(!heap.empty())
                heap.pop();
                break;
        }
    }
    return 0;
}

\text{诶，早知道就不手打了QAQ}

填坑第\huge{4}站完成！！！