堆

sLMxf · 2023-09-01 10:19:36 · 个人记录

1. 放在前面

这里会先讲手打模板，可以直接翻到最后（所以本篇博客不长）。

2. 什么是堆

优先队列是堆！
堆就是用来维护序列中最“大”的一个数据结构。注意这里的“大”指的是最怎么样的数据，而不是意义上的“最大”。例如最大、最小。

3. 堆的性质

• 堆是一棵完全二叉树
• 这棵完全二叉树的根节点（或称堆的顶点）就是最“大”的那个数据结构。

4. 手写【模板】堆

先奉上例题：【模板】堆
题目要求维护查询、插入、删除三种操作。分别来写：

• 定义
  由于是一棵完全二叉树，可以使用数组存储法。
  定义就是：

  int a[1000001],w=0;

  w是用来存储树的长度的。

  • 查询
    根据堆的性质二，堆的根节点为a[1]，注意判断有没有根节点。
    代码：

    int find()
    {
        return a[1];
    }

    同理，返回长度可以直接返回w

  • 插入
    为了维护堆的性质一的性质，我们将新插入的点插到最后。
    然而，这样很有可能会破坏堆的性质二。
    所以每次将它和父亲节点比较一下，是不是比父亲节点小，是就交换。
    注意：根节点不用再交换了
    代码：

    void pushx(int x)
    {
        if(x==1||a[x/2]<a[x]) return;
        swap(a[x/2],a[x]);
        pushx(x/2);
    }
    void push(int x)
    {
         a[++w]=x;
         pushx(w);
    }

  • 删除
    为了保证堆是一棵完全二叉树，我们不能直接删除根，得先将其与最后一个节点交换。
    然后你会发现它又不是堆，因为破坏了堆的性质二。
    所以你得将根节点一路“下沉”，直到它小于他的两个儿子。
    代码：

    void popx(int x)
    {
        if(x*2>w) return;
        int now=2*x;
        if(x*2+1<=w)
            now=a[x*2]<a[x*2+1]?x*2:x*2+1;
        if(a[x]>a[now])
        {
            swap(a[x],a[now]);
            popx(now);
        }
    }
    void pop()
    {
        swap(a[1],a[w--]);
        popx(1); 
    }

  • 完整代码

    #include<bits/stdc++.h>
    using namespace std;
    int a[1000001],w=0;
    //查询，代码略
    //插入，代码略
    //删除，代码略
    int main()
    {
           int n;
           cin>>n;
           for(int i=1;i<=n;i++)
           {
               int op;
               cin>>op;
               if(op==1)
               {
                   int x;
                   cin>>x;
                   push(x);
               }
               if(op==2) cout<<find()<<endl;
               if(op==3) pop();
           }
           return 0;
    }

5. 时间复杂度

查询时间复杂度必定为 O(1)。
插入和删除最坏情况下要爬一遍树，但因为堆是完全二叉树，所以时间复杂度为 O(\log n)。

6. 堆排序

堆排序很简单：先将所有数字压入堆，再将所有数字踢出去并输出。
代码：

#include<bits/stdc++.h>
using namespace std;
int a[1000001],w=0;
//此处为find,pop,push,popx,pushx，代码略
int main()
{
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            push(x);
        }
        for(int j=1;j<=n;j++)
        {
            cout<<find();
            pop();
        }
}

堆排序时间复杂度 O(n \log n)

7. STL【模板】堆

例题不变，我们用STL的话就是priority_queue。
专门有一篇博客哦！link