P3378 【模板】堆

admin

https://www.luogu.org/problemnew/show/P3378
题目描述
如题，初始小根堆为空，我们需要支持以下3种操作：
操作1： 1 x 表示将x插入到堆中
操作2： 2 输出该小根堆内的最小数
操作3： 3 删除该小根堆内的最小数

输入输出格式
输入格式：
第一行包含一个整数N，表示操作的个数

接下来N行，每行包含1个或2个正整数，表示三种操作，格式如下：
操作1： 1 x
操作2： 2
操作3： 3

输出格式：
包含若干行正整数，每行依次对应一个操作2的结果。

输入输出样例
输入样例#1：
5
1 2
1 5
2
3
2
输出样例#1：
2
5
说明
时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=15
对于70%的数据：N<=10000
对于100%的数据：N<=1000000（注意是6个0。。。不过不要害怕，经过编者实测，堆是可以AC的）

admin

典型的基本堆的使用，堆是一个完全二叉树，每一个根结点比它的左右儿子都小（或者大），我们利用这种数据结构来做此题：
用a(1)-a(n)表示这个堆，那么i的左儿子是2*i右儿子是2*i+1

每次新来一个结点，设为y=a(x)，若x是偶数，则它是x/2的左儿子，若是奇数，则它是x/2的右儿子；
比较a(x)和a(x/2) ，若<，则要将y上移，然后递归，我喜欢用递归好理解。

1. void pushup(int x)  /// 把a(x)向上调整到合适的位置
   
2. {
   
3.         if (x==1) return ;
   
4.         int y=x/2; ///x的儿子
   
5.         if (a[y]>a[x])
   
6.         {
   
7.                 swap(a[x],a[y]); ///交换一下
   
8.                 pushup(y);
   
9.         }
   
10. }

复制代码

删除顶上的最小结点后，一般是把他和最后一个元素交换，然后比较，先算出左右儿子的那个最小值，然后和他比较，若比它小，就交换位置，然后递归。

1. void pushdown(int x)  /// 把a(x)向下调整到合适的位置
   
2. {
   
3.         if (2*x>tot)  return ;/// 已经是叶子
   
4.         int y,yl=x*2,yr=x*2+1;
   
5. 
   
6.         if (yr>tot)  y=yl;///没有右儿子那就只能看左儿子了
   
7.         else if (a[yl]>a[yr]) y=yr;else y=yl;///选择左右儿子的较小
   
8. 
   
9.         if (a[x]>a[y])  ///和最小的儿子交换
   
10.         {
    
11.                 swap(a[x],a[y]);
    
12.                 pushdown(y);
    
13.         }
    
14. }

复制代码

递归好理解，但是速度有损失，牛人可以自己理解后写成递推。

admin

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const int mm=1000100;
   
4. int a[mm],tot,x,n;
   
5. void ArrayPr()
   
6. {
   
7.         for(int i=1; i<=tot; i++)  cout<<setw(3)<<a[i];
   
8.         cout<<endl;
   
9. }
   
10. void pushup(int x)  /// 把a(x)向上调整到合适的位置
    
11. {
    
12.         if (x==1) return ;
    
13.         int y=x/2; ///x的儿子
    
14.         if (a[y]>a[x])
    
15.         {
    
16.                 swap(a[x],a[y]); ///交换一下
    
17.                 pushup(y);
    
18.         }
    
19. }
    
20. void pushdown(int x)  /// 把a(x)向下调整到合适的位置
    
21. {
    
22.         if (2*x>tot)  return ;/// 已经是叶子
    
23.         int y,yl=x*2,yr=x*2+1;
    
24. 
    
25.         if (yr>tot)  y=yl;///没有右儿子那就只能看左儿子了
    
26.         else if (a[yl]>a[yr]) y=yr;else y=yl;///选择左右儿子的较小
    
27. 
    
28.         if (a[x]>a[y])  ///和最小的儿子交换
    
29.         {
    
30.                 swap(a[x],a[y]);
    
31.                 pushdown(y);
    
32.         }
    
33. }
    
34. int main()
    
35. {
    
36.         cin>>n;
    
37.         tot=0;
    
38.         int opt,x;
    
39.         while (n--)
    
40.         {
    
41.                 cin>>opt;
    
42.                 if (opt==1)
    
43.                 {
    
44.                         cin>>x;
    
45.                         a[++tot]=x;
    
46.                         pushup(tot);
    
47.                 }
    
48. 
    
49.                 if (opt==2) cout<<a[1]<<endl;
    
50.                 if (opt==3)
    
51.                 {
    
52.                         swap(a[1],a[tot]);
    
53.                         tot--;
    
54.                         pushdown(1);
    
55.                 }
    
56.                 ///ArrayPr();
    
57.         }
    
58.         return 0;
    
59. }
    
60. /*
    
61. 10
    
62. 50 25 75 18 38 66 80 10 16 11
    
63. */
    

复制代码