华师一附中OI组

标题: P3378 【模板】堆 [打印本页]
作者: admin    时间: 2018-5-4 09:49
标题: P3378 【模板】堆
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    时间: 2020-3-23 21:47
典型的基本堆的使用，堆是一个完全二叉树，每一个根结点比它的左右儿子都小（或者大），我们利用这种数据结构来做此题：
用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;

  6.         if (yr>tot)  y=yl;///没有右儿子那就只能看左儿子了
  7.         else if (a[yl]>a[yr]) y=yr;else y=yl;///选择左右儿子的较小

  9.         if (a[x]>a[y])  ///和最小的儿子交换
  10.         {
  11.                 swap(a[x],a[y]);
  12.                 pushdown(y);
  13.         }
  14. }
复制代码


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

作者: admin    时间: 2020-3-23 22:34
  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;

  25.         if (yr>tot)  y=yl;///没有右儿子那就只能看左儿子了
  26.         else if (a[yl]>a[yr]) y=yr;else y=yl;///选择左右儿子的较小

  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.                 }

  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. */
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2