《算法导论》习题6.5-8的实现，在时间复杂度方面，存在疑惑，望指教。具体问题写在代码的注释中。主要有两个方面：判断取出元素所在数组耗时问题和Java中switch语句的耗时问题。

本人菜鸟，欢迎讨论。

1. package lhz.algorithm.chapter.six; 
2.  
3.  
4. /** 
5.  * 《算法导论》习题6.5-8: Give an Θ(nlgk)-time algorithm to merge k sorted lists into 
6.  * one sorted list, where n is the total number of elements in all the input 
7.  * lists. (Hint: Use a min-heap for k-way merging.)  
8. * 本文地址：http://mushiqianmeng.blog.51cto.com/3970029/747716
9.  * @author lihzh(苦逼coder) 
10.  */ 
11. public class Exercice658 { 
12.  
13.     // 给定3（k=3）个已排好序的数组，这里考虑简单情况， 
14.     // 即所有数组包含的元素个数一致。 
15.     // 注：因为已实现MaxHeapify算法，所以此处用最大到小排好序的数组举例 
16.     private static int[] arrayOne = new int[] { 7, 4, 3, 1 }; 
17.     private static int[] arrayTwo = new int[] { 10, 9, 5, 2 }; 
18.     private static int[] arrayThree = new int[] { 12, 11, 8, 6 }; 
19.      
20.     // 已排好序中的数组中，元素的个数 
21.     private static int length = arrayOne.length; 
22.     // 已排好序的数组的个数 
23.     private static int k = 3; 
24.     // 所有数组中元素的总个数 
25.     private static int n = length * k; 
26.     // 合并后输出数组 
27.     private static int[] output = new int[n]; 
28.      
29.     public static void main(String[] args) { 
30.         mergeSortedArrays(); 
31.         // 打印数组 
32.         printArray(); 
33.     } 
34.  
35.     /** 
36.      * 合并已排序的数组，利用<code>PriorityQueue</code>中 的insert和extractMax算法实现 
37.      * 复杂度分析： 
38.      * 根据当前实现，复杂度应该为：Θ(nk)，并不满足题意。 
39.      * 但是所用思路，与习题参考中的思路一致，参考原文如下： 
40.      * Given k sorted lists with a total of n elements show how to merge them in O(n lg k) time. Insert 
41.      * all k elements a position 1 from each list into a heap. Use EXTRACT-MAX to obtain the _rst element 
42.      * of the merged list. Insert element at position 2 from the list where the largest element originally 
43.      * came from into the heap. Continuing in this fashion yields the desired algorithm. Clearly the 
44.      * running time is O(n lg k). 
45.      * 差异之处在于，当从堆中取出一个元素之后，需要知道这个元素原来所属数组，这里也需要去判断，这里耗时K。另外，在插入的时候， 
46.      * 也需要判断 
47.      */ 
48.     private static void mergeSortedArrays() { 
49.          
50.         // 利用前面实现的优先级队列中的方法，构造一个容量为k=3的堆 
51.         PriorityQueue priQueue = new PriorityQueue(k); 
52.         int count = 0; 
53.         //用于保存各数组当前插入元素索引位的数组 
54.         int[] indexArray = new int[k]; 
55.         int arrayChoice = 0; 
56.         //初始情况，向堆中插入各数组首位元素 
57.         //复杂度：Θ(klgk) 
58.         priQueue.insert(arrayOne[0]); 
59.         priQueue.insert(arrayTwo[0]); 
60.         priQueue.insert(arrayThree[0]); 
61.         for (int i = 0; i < n; i++) {// 该循环复杂度：Θ(n) 
62.             // 取出当前最大值，复杂度Θ(lgk) 
63.             int value = priQueue.extractMax(); 
64.             count++; 
65.             // 赋值 
66.             output[n-count] = value; 
67.             // 判断当前取出的最大元素所在数组，硬编码：(疑惑：复杂度Θ(k),因为最差会进行k次比较，此处如何优化) 
68.             if (value == arrayOne[indexArray[0]]) { 
69.                 arrayChoice = 0; 
70.             } else if (value == arrayTwo[indexArray[1]]) { 
71.                 arrayChoice = 1; 
72.             } else { 
73.                 arrayChoice = 2; 
74.             } 
75.             // 相应的索引位+1 
76.             indexArray[arrayChoice]++; 
77.             // 向堆中插入元素,如果备选数组中还有元素，则继续从该数组选取(疑惑：采用switch语句，复杂度是否降到Θ(lgk)以下) 
78.             // 根据:http://hi.baidu.com/software_one/blog/item/254990dfd96aee205982ddcb.html 中介绍，似乎可以。 
79.             // 望高手指导！ 
80.             switch (arrayChoice) { 
81.             case 0 : 
82.                 if (indexArray[0] < length) { 
83.                     priQueue.insert(arrayOne[indexArray[0]]); 
84.                 } 
85.                 break; 
86.             case 1 : 
87.                 if (indexArray[1] < length) { 
88.                     priQueue.insert(arrayTwo[indexArray[1]]); 
89.                 } 
90.                 break; 
91.             case 2 : 
92.                 if (indexArray[2] < length) { 
93.                     priQueue.insert(arrayThree[indexArray[2]]); 
94.                 }  
95.                 break; 
96.             } 
97.         } 
98.     } 
99.  
100.     private static void printArray() { 
101.         for (int i : output) { 
102.             System.out.print(i + " "); 
103.         } 
104.     } 
105. } 

本例中使用到了之前实现的优先级队列中的方法，修改之前PriorityQueue类，增加构造函数：

1. public PriorityQueue(int capacity) { 
2.         this.queue = new int[capacity]; 
3.     } 
4.      
5.     public PriorityQueue() { 
6.         this(DEFAULT_CAPACITY_VALUE); 
7.     }