IT评测·应用市场-qidao123.com

标题: P3378 【模板】二叉堆 [打印本页]

作者: 徐锦洪    时间: 2023-7-8 11:50
标题: P3378 【模板】二叉堆
[洛谷]P3378 【模板】堆

方法一  手写堆

  1. void siftdown(int i) //传入一个需要向下调整的结点编号i,这里传入1,即从堆的顶点开始向下调整
  2. {
  3.     int t,flag=0;//flag用来标记是否需要继续向下调整
  4.     //当i结点有儿子的时候(其实是至少有左儿子的情况下)并且有需要继续调整的时候循环窒执行
  5.     while( i*2<=n && flag==0 )
  6.     {      
  7.         //首先判断他和他左儿子的关系,并用t记录值较小的结点编号
  8.         if( h[ i] > h[ i*2] )
  9.             t=i*2;
  10.         else
  11.             t=i;
  12.         //如果他有右儿子的情况下,再对右儿子进行讨论
  13.         if(i*2+1 <= n)
  14.         {
  15.             //如果右儿子的值更小,更新较小的结点编号
  16.             if(h[ t] > h[ i*2+1])
  17.                 t=i*2+1;
  18.         }
  19.         //如果发现最小的结点编号不是自己,说明子结点中有比父结点更小的
  20.         if(t!=i)
  21.         {
  22.             swap(t,i);//交换它们,注意swap函数需要自己来写
  23.             i=t;//更新i为刚才与它交换的儿子结点的编号,便于接下来继续向下调整
  24.         }
  25.         else
  26.             flag=1;//则否说明当前的父结点已经比两个子结点都要小了,不需要在进行调整了
  27.     }
  28. }
复制代码
  1. void siftdown(int i) //传入一个需要向下调整的结点编号i,这里传入1,即从堆的顶点开始向下调整
  2. {
  3.     int t,flag=0;//flag用来标记是否需要继续向下调整
  4.     //当i结点有儿子的时候(其实是至少有左儿子的情况下)并且有需要继续调整的时候循环窒执行
  5.     while( i*2<=n && flag==0 )
  6.     {      
  7.         //首先判断他和他左儿子的关系,并用t记录值较小的结点编号
  8.         if( h[ i] > h[ i*2] )
  9.             t=i*2;
  10.         else
  11.             t=i;
  12.         //如果他有右儿子的情况下,再对右儿子进行讨论
  13.         if(i*2+1 <= n)
  14.         {
  15.             //如果右儿子的值更小,更新较小的结点编号
  16.             if(h[ t] > h[ i*2+1])
  17.                 t=i*2+1;
  18.         }
  19.         //如果发现最小的结点编号不是自己,说明子结点中有比父结点更小的
  20.         if(t!=i)
  21.         {
  22.             swap(t,i);//交换它们,注意swap函数需要自己来写
  23.             i=t;//更新i为刚才与它交换的儿子结点的编号,便于接下来继续向下调整
  24.         }
  25.         else
  26.             flag=1;//则否说明当前的父结点已经比两个子结点都要小了,不需要在进行调整了
  27.     }
  28. }//删除最小数void del(){        dui[1]=dui[d];        d--;        shitdown(1);}
复制代码
方法二  STL

c++优先队列(priority_queue)用法详解
[code]#includeusing namespace std;int n,d;int main(){        priority_queue dui;        cin>>n;        for(int i=1;i>op;                if(op==1){                        int num;                        cin>>num;                        dui.push(num);                                        }                else if(op==2)                        cout




欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/) Powered by Discuz! X3.4