1.5.24适用于Erdos-Renyi模型的快速算法。在练习1.5.23的测试中增加加权quick-union算法和使用路径压缩的加权quick-union算法。你能分辨出这两种算法的区别吗？

答：加权quick-union最坏情况下树深度为lgN,N为节点数，路径压缩的加权quick-union算法最坏情况下树深度为1。

public class E1d5d24

{

     public static class Connection

    {

        int p;

        int q;

        public Connection(int p,int q)

        {this.p=p; this.q=q;}

       

        public int P()

        {return p;}

   

        public int Q()

        {return q;}

    }

        //

    public static int[][]  Generate(int N)

    {

        Queue<Connection> cnns=new Queue();

        WeightedQuickUnionUF uf=new WeightedQuickUnionUF(N);

         while (uf.count()>1)

           {

               int p=StdRandom.uniform(N);

               int q=StdRandom.uniform(N);

               uf.union(p,q);

               cnns.enqueue(new Connection(p,q));

            }//end while

       //

         int[][] cnnsOfArray=new int[cnns.size()][2];

         int i=0;

         while(!cnns.isEmpty())

         {

             Connection item=cnns.dequeue();

             cnnsOfArray[i][0]=item.P();

             cnnsOfArray[i][1]=item.Q();

             i++;

         }

         return cnnsOfArray;

    }

   

   public static double QuickFindElapsedTime(int[][] cnns,int T,int N)

   {

        Stopwatch timer=new Stopwatch();

        for (int t=1;t<=T;t++)

        {

             QuickFindUF uf=new QuickFindUF(N);

             int i=0;

             while(uf.count()>1)

             {

                 uf.union(cnns[i][0],cnns[i][1]);

                 i++;

             }

        }

         return timer.elapsedTime();

   }

     

     

  public static double QuickUnionElapsedTime(int[][] cnns,int T,int N)

   {

        Stopwatch timer=new Stopwatch();

        for (int t=1;t<=T;t++)

        {

             QuickUnionUF uf=new QuickUnionUF(N);

             int i=0;

             while(uf.count()>1)

             {

                 uf.union(cnns[i][0],cnns[i][1]);

                 i++;

             }

        }

         return timer.elapsedTime();

   }

  

    public static double WeightedQuickUnionElapsedTime(int[][] cnns,int T,int N)

   {

        Stopwatch timer=new Stopwatch();

        for (int t=1;t<=T;t++)

        {

             WeightedQuickUnionUF uf=new WeightedQuickUnionUF(N);

             int i=0;

             while(uf.count()>1)

             {

                 uf.union(cnns[i][0],cnns[i][1]);

                 i++;

             }

        }

         return timer.elapsedTime();

   }

   

        public static double CompressPathQuickUnionElapsedTime(int[][] cnns,int T,int N)

   {

        Stopwatch timer=new Stopwatch();

        for (int t=1;t<=T;t++)

        {

             E1d5d12 uf=new E1d5d12(N);

             int i=0;

             while(uf.count()>1)

             {

                 uf.union(cnns[i][0],cnns[i][1]);

                 i++;

             }

        }

         return timer.elapsedTime();

   }

      

    public static void main(String[] args)

    {

        int T=Integer.parseInt(args[0]);

        for (int N=2;N<=Math.pow(2,15);N=N+N)

        {

            int[][] cnns=Generate(N);

            double QuickFindTime=QuickFindElapsedTime(cnns,T,N);

            double QuickUnionTime= QuickUnionElapsedTime(cnns,T,N);

            double WeightedQuickUnionTime=WeightedQuickUnionElapsedTime(cnns,T,N);

            double CompressPathQuickUnionTime=CompressPathQuickUnionElapsedTime(cnns,T,N);

             StdOut.printf("N=%6d T=%3d  QF=%6.2f QU=%6.2f WQU=%6.2f  CPQU=%6.2f QF/QU=%10.2f QF/WQU=%10.2f QF/CPQU=%10.2f \n",  N,  T,QuickFindTime,QuickUnionTime,WeightedQuickUnionTime,CompressPathQuickUnionTime,QuickFindTime/QuickUnionTime,QuickFindTime/WeightedQuickUnionTime,QuickFindTime/CompressPathQuickUnionTime);

       }

       

    }

}