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

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

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

 1 package package01;
 2 
 3 import edu.princeton.cs.algs4.IndexMinPQ;
 4 import edu.princeton.cs.algs4.In;
 5 import edu.princeton.cs.algs4.StdOut;
 6 
 7 public class class01
 8 {
 9     private class01() {}
10 
11     private static void merge(In[] streams)
12     {
13         int n = streams.length;
14         IndexMinPQ<String> pq = new IndexMinPQ<String>(n);
15         for (int i = 0; i < n; i++)                     // 初始化队列，每个流输入一个元素
16         {
17             if (!streams[i].isEmpty())
18                 pq.insert(i, streams[i].readString());
19         }
20         for (;!pq.isEmpty();)
21         {
22             StdOut.print(pq.minKey() + " ");            // 每当输出来自某个流的元素，就从该流插入一个元素
23             int i = pq.delMin();
24             if (!streams[i].isEmpty())
25                 pq.insert(i, streams[i].readString());
26         }
27         StdOut.println();
28     }
29 
30     public static void main(String[] args)
31     {
32         int n = args.length;
33         In[] streams = new In[n];                       // 初始化输入流，输入多个文件
34         for (int i = 0; i < n; i++)
35             streams[i] = new In(args[i]);
36         merge(streams);
37     }
38 }

● 堆排序

 1 package package01;
 2 
 3 import edu.princeton.cs.algs4.StdIn;
 4 import edu.princeton.cs.algs4.StdOut;
 5 
 6 public class class01
 7 {
 8     private class01() {}
 9 
10     public static void sort(Comparable[] pq)
11     {
12         int n = pq.length;
13         for (int k = n / 2; k >= 1; k--)  // 建堆
14             sink(pq, k, n);
15         for (; n > 1;)                    // 每次将最大元素交换到最后，重新调整前面的部分
16         {
17             exch(pq, 1, n--);
18             sink(pq, 1, n);
19         }
20     }
21 
22     private static void sink(Comparable[] pq, int k, int n)
23     {
24         for (int j = k << 1; j <= n; exch(pq, k, j), k = j, j = k << 1)
25         {
26             if (j < n && less(pq, j, j + 1))
27                 j++;
28             if (!less(pq, k, j))
29                 break;
30         }
31     }
32 
33     private static boolean less(Comparable[] pq, int i, int j)
34     {
35         return pq[i - 1].compareTo(pq[j - 1]) < 0;
36     }
37 
38     private static void exch(Object[] pq, int i, int j)
39     {
40         Object swap = pq[i - 1];
41         pq[i - 1] = pq[j - 1];
42         pq[j - 1] = swap;
43     }
44 
45     private static void show(Comparable[] a)
46     {
47         for (int i = 0; i < a.length; i++)
48             StdOut.println(a[i]);
49     }
50 
51     public static void main(String[] args)
52     {
53         String[] a = StdIn.readAllStrings();
54         class01.sort(a);
55         show(a);
56     }
57 }