二叉堆 - 老官童鞋gogo的博客

二叉堆简介

二叉堆是一种基础数据结构，对于其他数据结构来说，支持的操作有限，也就插入，查询，删除这一类。

二叉堆的结构

从二叉堆的结构说起，它是一棵二叉树，并且是完全二叉树，每个结点中存在一个权值。堆性质：父亲的权值不小于儿子的权值（大根堆）。同样的，我们可以定义小根堆。本文以大根堆为例。由堆性质，树根存的是最大值。对于堆的每个子树，它同样也是一个堆。

考虑使用一个序列h来表示堆，的两个儿子分别是和，是根节点：

h 的堆结构

来自于：OI Wiki

具体每个节点的对应关系如上图。

二叉堆的基本操作

插入操作

插入操作是指向二叉堆中插入一个元素，但是要保证插入这个元素后，这颗二叉树仍然满足堆的性质。最简单的实现方法就是从最下层的叶子节点插入，如果最下面一层已经满了，就新建一层，将插入的节点与他的父亲节点比较，如果当前节点的权值大于父亲节点的权值，那么就交换父亲节点与当前节点，直到符合二叉堆的要求或者是当前插入的节点转移到根节点。

二叉堆的插入操作

来自于：OI Wiki

1
void pushup(int x){
2
    if(x==1)
3
        return;
4
    if(h[x]>h[x>>1])
5
        swap(h[x],h[x>>1]);
6
    pushup(x>>1);
7
}
8
void push(int x){
9
    h[++cnt]=x;
10
    pushup(cnt);
11
}

删除操作

删除操作指的是删除根节点的操作，同样地，在删除根节点后，我们要保证这一个堆的完整性，并且使堆仍然保持原来的性质。如果直接删除根节点，那么整个堆会一分为二，不好处理，所以，我们考虑将插入操作倒序走一遍，首先将根节点与它权值最大的儿子交换，然后不停地像这样交换下去，最终到达叶子节点，被删除。

1
void pop(int x){
2
    if((x<<1)>cnt){
3
        h[x]=inf;
4
        return;
5
    }
6
    if(h[x<<1]>h[x<<1|1]){
7
        swap(h[x],h[x<<1]);
8
        pop(x<<1);
9
    }
10
    else{
11
        swap(h[x],h[x<<1|1]);
12
        pop(x<<1|1);
13
    }
14
}

查询操作

查询操作只限于查询一个堆的堆顶元素。直接输出二叉堆的根即可。

库中的优先队列

在中，有个存在priority_queue，翻译叫做优先队列，实际上就是二叉堆，它处于queue库中，下面是它的几种操作：

建立优先队列（大根堆）：priority_queue<int>q
建立优先队列（小根堆）：priority_queue<int,vector<int>,greater<int> >q;
插入一个数：q.push(x)
删除堆顶：q.pop()
查询堆顶：q.top()
判断堆是否为空：q.empty()
查询堆的元素个数：q.size()

代码

来源：洛谷：P3378 【模板】堆（小根堆，变换比较符号即为大根堆）

1
#include<iostream>
2
#include<cstdio>
3
#include<algorithm>
4
#include<cstring>
5
#include<cstdlib>
6
#include<cmath>
7
#include<vector>
8
#include<queue>
9
#include<map>
10
#include<set>
11
#include<ctime>
12
using namespace std;
13
typedef unsigned int uint;
14
typedef long long LL;
15
typedef unsigned long long uLL;
16
typedef __int128 int128;
17
typedef unsigned __int128 uint128;
18
typedef long double Ld;
19
#define reg register;
20
#define space putchar(' ')
21
#define enter putchar('\n')
22
#define PI 3.14159265358979323846
23
#define pb(x) push_back(x)
24
#define mp(a,b) make_pair(a,b)
25
#define fi first
26
#define se second
27
#define pr(x) cerr<<#x<<"="<<(x)<<endl
28
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
29
#define inf 1000000000
30
#define INF 1000000000000000000
31
#define N 1010
32
#define M 1000010
33
// void gettime(){
34
//   cerr<<"time:"<<(double)clock()<<"ms"<<endl;
35
// }
36
namespace Fast{
37
  template<typename T>inline void read(T &x){
38
    x=0;bool f=false;char c=getchar();
39
    while(c<'0'||c>'9'){if(c=='-')f=true;c=getchar();}
40
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
41
    if(f)x=~x+1;
42
  }
43
  template<typename T>inline void print(T x){
44
    int s[65],top=0;
45
    if(x<0)putchar('-'),x=~x+1;
46
    while(x)s[++top]=x%10,x/=10;
47
    if(!top)s[++top]=0;
48
    while(top)putchar(s[top--]+'0');
49
  }
50
  template<typename T,typename...Args>inline void read(T &x,Args&...others){
51
    read(x),read(others...);
52
  }
53
  template<typename T,typename...Args>inline void print(T x,Args...others){
54
    print(x),space,print(others...);
55
  }
56
  const double eps=1e-7;
57
  template<typename T>inline T Abs(T x){return x>0?x:-x;}
58
  template<typename T>inline T Max(T x,T y){return x>y?x:y;}
59
  template<typename T>inline T Min(T x,T y){return x<y?x:y;}
60
  template<typename T>inline T Fabs(T x){return x>eps?x:-x;}
61
  template<typename T>inline T Fmax(T x,T y){return x-y>eps?x:y;}
62
  template<typename T>inline T Fmin(T x,T y){return x-y<eps?x:y;}
63
  template<typename T>inline void addmod(T &x,T p){if(x>=p)x-=p;}
64
  template<typename T>inline void submod(T &x,T p){if(x<0)x+=p;}
65
}
66
using namespace Fast;
67
int h[M<<1],n,cnt;
68
void pushup(int x){
69
    if(x==1)
70
        return;
71
    if(h[x]<h[x>>1])
72
        swap(h[x],h[x>>1]);
73
    pushup(x>>1);
74
}
75
void push(int x){
76
    h[++cnt]=x;
77
    pushup(cnt);
78
}
79
void pop(int x){
80
    if((x<<1)>cnt){
81
        h[x]=inf;
82
        return;
83
    }
84
    if(h[x<<1]<h[x<<1|1]){
85
        swap(h[x],h[x<<1]);
86
        pop(x<<1);
87
    }
88
    else{
89
        swap(h[x],h[x<<1|1]);
90
        pop(x<<1|1);
91
    }
92
}
93
int main(){
94
  read(n);
95
    for(int i=1;i<=n;i++){
96
        h[i]=inf;
97
    }
98
    for(int i=1;i<=n;i++){
99
        int opt,x;
100
        read(opt);
101
        if(opt==1){
102
            read(x);
103
            push(x);
104
        }
105
        if(opt==2){
106
            print(h[1]);
107
            enter;
108
        }
109
        if(opt==3){
110
            pop(1);
111
        }
112
    }
113
  return 0;
114
}

老官童鞋gogo