当前位置：首页 > article >正文

算法基础之模拟堆

article 2024/11/15 15:26:55

模拟堆

核心思想:用数组模拟堆并实现STL堆没有的操作

  #include<iostream>
  #include<algorithm>
  #include<string.h>
  using namespace std;
  
  const int N=100010;
  
  //用ph[N]存储第k个输入,用hp[N]映射元素下标
  int h[N],cnt,ph[N],hp[N];
  int n,m=0;
  
  //三个都要交换
  void heap_swap(int a,int b){
      swap(ph[hp[a]],ph[hp[b]]);  //hp[]返回映射后下标
      swap(hp[a],hp[b]);
      swap(h[a],h[b]);
  }
  void down(int x){
      int t=x;
      if(x*2<=cnt && h[x*2]<h[t]) t=x*2;
      if(x*2+1 <=cnt && h[x*2+1]<h[t]) t=x*2+1;
      if( x!=t ){
          heap_swap(t,x);
          down(t);
      }
  }
  
  void up(int x){
      while(x/2 && h[x] < h[x/2]){  //多次交换
          heap_swap(x,x/2);
          x/=2;
      }
  }
  
  int main(){
      cin>>n;
      while(n--){
          string op;
          cin>>op;
          int k,x;
          if (op=="I")
          {
              cin>>x;
              cnt ++ ;
              m ++ ;
              ph[m] = cnt, hp[cnt] = m;  //添加元素
              h[cnt] = x;
              up(cnt);
          }
          else if (op=="PM") cout<<h[1]<<endl;
          else if (op=="DM")
          {
              heap_swap(1, cnt);
              cnt -- ;
              down(1);
          }
          else if (op=="D")
          {
              cin>>k;
              k = ph[k];  //ph[k]返回第k个添加元素的下标
              heap_swap(k, cnt);
              cnt -- ;
              up(k);  //up一遍down一遍 找到合适位置
              down(k);  //一定会有一个直接返回 不操作的
          }
          else
          {
              cin>>k>>x;
              k = ph[k];
              h[k] = x;
              up(k);
              down(k);
          }
      }
      return 0;
  }