[关闭]
@zzzc18 2017-11-09T11:46:04.000000Z 字数 773 阅读 939

模板库


地址

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. int n;
  6. const int MAXN = 1000000;
  7. class Smaller_Heap{
  8. private:
  9. int size;
  10. int tree[MAXN<<1];
  11. public:
  12. void INIT(){
  13. memset(tree,0x7f,sizeof(tree));
  14. }
  15. int top(){
  16. return tree[1];
  17. }
  18. void push(int x){
  19. tree[++size]=x;
  20. int now=size;
  21. while(now>1){
  22. int fa=now>>1;
  23. if(tree[fa]>tree[now])
  24. swap(tree[fa],tree[now]);
  25. now>>=1;
  26. }
  27. }
  28. void pop(){
  29. int now=1;
  30. tree[now]=tree[size--];
  31. while((now<<1)<=size){
  32. int lson=now<<1;int rson=now<<1|1;
  33. int son=lson;
  34. if(rson<=size && tree[son]>tree[rson])
  35. son=rson;
  36. if(tree[son]<tree[now]){
  37. swap(tree[now],tree[son]);
  38. now=son;
  39. }
  40. else
  41. break;
  42. }
  43. }
  44. }heap;
  45. int main(){
  46. scanf("%d",&n);
  47. heap.INIT();
  48. for(int i=1;i<=n;i++){
  49. int opt,x;
  50. scanf("%d",&opt);
  51. if(opt==1){
  52. scanf("%d",&x);
  53. heap.push(x);
  54. }
  55. else if(opt==2){
  56. printf("%d\n",heap.top());
  57. }
  58. else
  59. heap.pop();
  60. }
  61. return 0;
  62. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注