《算法》第二章部分程序 part 5

▶ 书中第二章部分程序，加上自己补充的代码，包括利用优先队列进行多路归并和堆排序

● 利用优先队列进行多路归并

 package package01;

 import edu.princeton.cs.algs4.IndexMinPQ;

 import edu.princeton.cs.algs4.In;

 import edu.princeton.cs.algs4.StdOut;

 public class class01

 {

     private class01() {}

     private static void merge(In[] streams)

     {

         int n = streams.length;

         IndexMinPQ<String> pq = new IndexMinPQ<String>(n);

         for (int i = 0; i < n; i++)                     // 初始化队列，每个流输入一个元素

         {

             if (!streams[i].isEmpty())

                 pq.insert(i, streams[i].readString());

         }

         for (;!pq.isEmpty();)

         {

             StdOut.print(pq.minKey() + " ");            // 每当输出来自某个流的元素，就从该流插入一个元素

             int i = pq.delMin();

             if (!streams[i].isEmpty())

                 pq.insert(i, streams[i].readString());

         }

         StdOut.println();

     }

     public static void main(String[] args)

     {

         int n = args.length;

         In[] streams = new In[n];                       // 初始化输入流，输入多个文件

         for (int i = 0; i < n; i++)

             streams[i] = new In(args[i]);

         merge(streams);

     }

 }

● 堆排序

 package package01;

 import edu.princeton.cs.algs4.StdIn;

 import edu.princeton.cs.algs4.StdOut;

 public class class01

 {

     private class01() {}

     public static void sort(Comparable[] pq)

     {

         int n = pq.length;

         for (int k = n / 2; k >= 1; k--)  // 建堆

             sink(pq, k, n);

         for (; n > 1;)                    // 每次将最大元素交换到最后，重新调整前面的部分

         {

             exch(pq, 1, n--);

             sink(pq, 1, n);

         }

     }

     private static void sink(Comparable[] pq, int k, int n)

     {

         for (int j = k << 1; j <= n; exch(pq, k, j), k = j, j = k << 1)

         {

             if (j < n && less(pq, j, j + 1))

                 j++;

             if (!less(pq, k, j))

                 break;

         }

     }

     private static boolean less(Comparable[] pq, int i, int j)

     {

         return pq[i - 1].compareTo(pq[j - 1]) < 0;

     }

     private static void exch(Object[] pq, int i, int j)

     {

         Object swap = pq[i - 1];

         pq[i - 1] = pq[j - 1];

         pq[j - 1] = swap;

     }

     private static void show(Comparable[] a)

     {

         for (int i = 0; i < a.length; i++)

             StdOut.println(a[i]);

     }

     public static void main(String[] args)

     {

         String[] a = StdIn.readAllStrings();

         class01.sort(a);

         show(a);

     }

 }