文章

利用堆合并数组- Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
/**
 * 《算法导论》习题6.5-8: Give an θ(nlgk)-time algorithm to merge k sorted lists into
 * one sorted list, where n is the total number of elements in all the input
 * lists. (Hint: Use a min-heap for k-way merging.) 
 * @author lihzh(OneCoder)
 * @OneCoder-Blog http://www.coderli.com
 */
public class Exercice658 {

	// 给定3(k=3)个已排好序的数组,这里考虑简单情况,
	// 即所有数组包含的元素个数一致。
	// 注:因为已实现MaxHeapify算法,所以此处用最大到小排好序的数组举例
	private static int[] arrayOne = new int[] { 7, 4, 3, 1 };
	private static int[] arrayTwo = new int[] { 10, 9, 5, 2 };
	private static int[] arrayThree = new int[] { 12, 11, 8, 6 };
	
	// 已排好序中的数组中,元素的个数
	private static int length = arrayOne.length;
	// 已排好序的数组的个数
	private static int k = 3;
	// 所有数组中元素的总个数
	private static int n = length * k;
	// 合并后输出数组
	private static int[] output = new int[n];
	
	public static void main(String[] args) {
		mergeSortedArrays();
		// 打印数组
		printArray();
	}

	/**
	 * 合并已排序的数组,利用<code>;PriorityQueue</code>;中 的insert和extractMax算法实现
	 * 复杂度分析:
	 * 根据当前实现,复杂度应该为:θ(nk),并不满足题意。
	 * 但是所用思路,与习题参考中的思路一致,参考原文如下:
	 * Given k sorted lists with a total of n elements show how to merge them in O(n lg k) time. Insert
	 * all k elements a position 1 from each list into a heap. Use EXTRACT-MAX to obtain the rst element
	 * of the merged list. Insert element at position 2 from the list where the largest element originally
	 * came from into the heap. Continuing in this fashion yields the desired algorithm. Clearly the
	 * running time is θ(n lg k).
	 * 差异之处在于,当从堆中取出一个元素之后,需要知道这个元素原来所属数组,这里也需要去判断,这里耗时K。另外,在插入的时候,
	 * 也需要判断
	 */
	private static void mergeSortedArrays() {
		
		// 利用前面实现的优先级队列中的方法,构造一个容量为k=3的堆
		PriorityQueue priQueue = new PriorityQueue(k);
		int count = 0;
		//用于保存各数组当前插入元素索引位的数组
		int[] indexArray = new int[k];
		int arrayChoice = 0;
		//初始情况,向堆中插入各数组首位元素
		//复杂度:θ(klgk)
		priQueue.insert(arrayOne[0]);
		priQueue.insert(arrayTwo[0]);
		priQueue.insert(arrayThree[0]);
		for (int i = 0; i < n; i++) {// 该循环复杂度:θ(n)
			// 取出当前最大值,复杂度θ(lgk)
			int value = priQueue.extractMax();
			count++;
			// 赋值
			output[n-count] = value;
			// 判断当前取出的最大元素所在数组,硬编码:(疑惑:复杂度θ(k),因为最差会进行k次比较,此处如何优化)
			if (value == arrayOne[indexArray[0]]) {
				arrayChoice = 0;
			} else if (value == arrayTwo[indexArray[1]]) {
				arrayChoice = 1;
			} else {
				arrayChoice = 2;
			}
			// 相应的索引位+1
			indexArray[arrayChoice]++;
			// 向堆中插入元素,如果备选数组中还有元素,则继续从该数组选取(疑惑:采用switch语句,复杂度是否降到θ(lgk)以下)
			// 根据:http://hi.baidu.com/software_one/blog/item/254990dfd96aee205982ddcb.html 中介绍,似乎可以。
			// 望高手指导!
			switch (arrayChoice) {
			case 0 :
				if (indexArray[0] < length) {
					priQueue.insert(arrayOne[indexArray[0]]);
				}
				break;
			case 1 :
				if (indexArray[1] < length) {
					priQueue.insert(arrayTwo[indexArray[1]]);
				}
				break;
			case 2 :
				if (indexArray[2] < length) {
					priQueue.insert(arrayThree[indexArray[2]]);
				} 
				break;
			}
		}
	}

	private static void printArray() {
		for (int i : output) {
			System.out.print(i + " ");
		}
	}
}
本文由作者按照 CC BY 4.0 进行授权