package lhz.algorithm.chapter.six;
/**
 * "优先级队列"，《算法导论》6.5章节
 * 原文摘要：
 * A priority queue is a data structure for maintaining a set S of elements, each with an
 * associated value called a key. A max-priority queue supports the following operations.
 * ・ INSERT(S, x) inserts the element x into the set S. This operation could be written as S← S{x}.
 * ・ MAXIMUM(S) returns the element of S with the largest key.
 * ・ EXTRACT-MAX(S) removes and returns the element of S with the largest key.
 * ・ INCREASE-KEY(S, x, k) increases the value of element x‘s key to the new value k,
 * which is assumed to be at least as large as x‘s current key value.
 * 堆的一种实际应用，可用于任务调度队列等。包含四个操作方法。
 * @author lihzh(OneCoder)
 * @blog http://www.coderli.com
 */
public class PriorityQueue {
	
	private static final int DEFAULT_CAPACITY_VALUE = 16;
	//初始化一个长度为16的队列（可作为构造参数)，此处选择16参考HashMap的初始化值
	private int[] queue;
	//堆大小
	private int heapSize = 0;

	public static void main(String[] args) {
		PriorityQueue q = new PriorityQueue();
		q.insert(2);
		q.insert(6);
		q.insert(3);
		q.insert(8);
		q.insert(7);
		q.insert(9);
		q.insert(1);
		q.insert(10);
		q.insert(9);
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
		q.insert(9);
		q.insert(1);
		q.insert(10);
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
	}
	
	public PriorityQueue(int capacity) {
		this.queue = new int[capacity];
	}
	
	public PriorityQueue() {
		this(DEFAULT_CAPACITY_VALUE);
	}
	
	/**
	 * 返回当前最大值
	 * @return
	 */
	public int maximum() {
		return queue[0];
	}
	
	/**
	 * 往优先级队列出，插入一个元素
	 * 利用INCREASE-Key方法，从堆的最后增加元素
	 * 伪代码：
	 * MAX-HEAP-INSERT(A, key)
	 * 1 heap-size[A] ← heap-size[A] + 1
	 * 2 A[heap-size[A]] ← -∞
	 * 3 HEAP-INCREASE-KEY(A, heap-size[A], key)
	 * 时间复杂度：O(lg n)
	 * @param value 待插入元素
	 */
	public void insert(int value) {
		//注意堆容量和数组索引的错位 1
		queue[heapSize] = value;
		heapSize++;
		increaceKey(heapSize, value);
	}
	
	/**
	 * 增加给定索引位元素的值，并重新构成MaxHeap。
	 * 新值必须大于等于原有值
	 * 伪代码：
	 * HEAP-INCREASE-KEY(A, i, key)
	 * 1 if key < A[i]
	 * 2 then error "new key is smaller than current key"
	 * 3 A[i] ← key
	 * 4 while i > 1 and A[PARENT(i)] < A[i]
	 * 5 do exchange A[i] &harr; A[PARENT(i)]
	 * 6 i ← PARENT(i)
	 * 时间复杂度：O(lg n)
	 * @param index 索引位
	 * @param newValue 新值
	 */
	public void increaceKey (int heapIndex, int newValue) {
		if (newValue < queue[heapIndex-1]) {
			System.err.println("错误：新值小于原有值！");
			return;
		}
		queue[heapIndex-1] = newValue;
		int parentIndex = heapIndex / 2;
		while (parentIndex > 0 && queue[parentIndex-1] < newValue ) {
			int temp = queue[parentIndex-1];
			queue[parentIndex-1] = newValue;
			queue[heapIndex-1] = temp;
			heapIndex = parentIndex;
			parentIndex = parentIndex / 2;
		}
	}
	
	/**
	 * 返回堆顶元素（最大值），并且将堆顶元素移除
	 * 伪代码：
	 * HEAP-EXTRACT-MAX(A)
	 * 1 if heap-size[A] < 1
	 * 2 then error "heap underflow"
	 * 3 max ← A[1]
	 * 4 A[1] ← A[heap-size[A]]
	 * 5 heap-size[A] ← heap-size[A] - 1
	 * 6 MAX-HEAPIFY(A, 1)
	 * 7 return max
	 * 时间复杂度：O(lg n),
	 * @return
	 */
	public int extractMax() {
		if (heapSize < 1) {
			System.err.println("堆中已经没有元素!");
			return -1;
		}
		int max = queue[0];
		queue[0] = queue[heapSize-1];
		heapSize--;
		maxHeapify(queue, 1);
		return max;
	}
	
	
	/**
	 * 之前介绍的保持最大堆的算法
	 * @param array
	 * @param index
	 */
	private  void maxHeapify(int[] array, int index) {
		int l = index * 2;
		int r = l + 1;
		int largest;
		//如果左叶子节点索引小于堆大小，比较当前值和左叶子节点的值，取值大的索引值
		if (l <= heapSize && array[l-1] > array[index-1]) {
			largest = l;
		} else {
			largest = index;
		}
		//如果右叶子节点索引小于堆大小，比较右叶子节点和之前比较得出的较大值，取大的索引值
		if (r <= heapSize && array[r-1] > array[largest-1]) {
			largest = r;
		}
		//交换位置，并继续递归调用该方法调整位置。
		if (largest != index) {
			int temp = array[index-1];
			array[index-1] = array[largest-1];
			array[largest-1] = temp;
			maxHeapify(array, largest);
		}
	}
	
	public int[] getQueue() {
		return queue;
	}
}

package lhz.algorithm.chapter.six;
/**
 * "优先级队列"，《算法导论》6.5章节
 * 原文摘要：
 * A priority queue is a data structure for maintaining a set S of elements, each with an
 * associated value called a key. A max-priority queue supports the following operations.
 * ・INSERT(S, x) inserts the element x into the set S. This operation could be written as S←S{x}.
 * ・MAXIMUM(S) returns the element of S with the largest key.
 * ・EXTRACT-MAX(S) removes and returns the element of S with the largest key.
 * ・INCREASE-KEY(S, x, k) increases the value of element x's key to the new value k,
 * which is assumed to be at least as large as x's current key value.
 * 堆的一种实际应用，可用于任务调度队列等。包含四个操作方法。
 * @author lihzh(OneCoder)
 * @blog http://www.coderli.com
 */
public class PriorityQueue {
	
	private static final int DEFAULT_CAPACITY_VALUE = 16;
	//初始化一个长度为16的队列（可作为构造参数)，此处选择16参考HashMap的初始化值
	private int[] queue;
	//堆大小
	private int heapSize = 0;

	public static void main(String[] args) {
		PriorityQueue q = new PriorityQueue();
		q.insert(2);
		q.insert(6);
		q.insert(3);
		q.insert(8);
		q.insert(7);
		q.insert(9);
		q.insert(1);
		q.insert(10);
		q.insert(9);
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
		q.insert(9);
		q.insert(1);
		q.insert(10);
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
	}
	
	public PriorityQueue(int capacity) {
		this.queue = new int[capacity];
	}
	
	public PriorityQueue() {
		this(DEFAULT_CAPACITY_VALUE);
	}
	
	/**
	 * 返回当前最大值
	 * @return
	 */
	public int maximum() {
		return queue[0];
	}
	
	/**
	 * 往优先级队列出，插入一个元素
	 * 利用INCREASE-Key方法，从堆的最后增加元素
	 * 伪代码：
	 * MAX-HEAP-INSERT(A, key)
	 * 1 heap-size[A] ← heap-size[A] + 1
	 * 2 A[heap-size[A]] ← -∞
	 * 3 HEAP-INCREASE-KEY(A, heap-size[A], key)
	 * 时间复杂度：O(lg n)
	 * @param value 待插入元素
	 */
	public void insert(int value) {
		//注意堆容量和数组索引的错位 1
		queue[heapSize] = value;
		heapSize++;
		increaceKey(heapSize, value);
	}
	
	/**
	 * 增加给定索引位元素的值，并重新构成MaxHeap。
	 * 新值必须大于等于原有值
	 * 伪代码：
	 * HEAP-INCREASE-KEY(A, i, key)
	 * 1 if key < A[i]
	 * 2 then error "new key is smaller than current key"
	 * 3 A[i] ← key
	 * 4 while i > 1 and A[PARENT(i)] < A[i]
	 * 5 do exchange A[i] ⟷ A[PARENT(i)]
	 * 6 i ← PARENT(i)
	 * 时间复杂度：O(lg n)
	 * @param index 索引位
	 * @param newValue 新值
	 */
	public void increaceKey (int heapIndex, int newValue) {
		if (newValue < queue[heapIndex-1]) {
			System.err.println("错误：新值小于原有值！");
			return;
		}
		queue[heapIndex-1] = newValue;
		int parentIndex = heapIndex / 2;
		while (parentIndex > 0 && queue[parentIndex-1] < newValue ) {
			int temp = queue[parentIndex-1];
			queue[parentIndex-1] = newValue;
			queue[heapIndex-1] = temp;
			heapIndex = parentIndex;
			parentIndex = parentIndex / 2;
		}
	}
	
	/**
	 * 返回堆顶元素（最大值），并且将堆顶元素移除
	 * 伪代码：
	 * HEAP-EXTRACT-MAX(A)
	 * 1 if heap-size[A] < 1
	 * 2 then error "heap underflow"
	 * 3 max ← A[1]
	 * 4 A[1] ← A[heap-size[A]]
	 * 5 heap-size[A] ← heap-size[A] - 1
	 * 6 MAX-HEAPIFY(A, 1)
	 * 7 return max
	 * 时间复杂度：O(lg n),
	 * @return
	 */
	public int extractMax() {
		if (heapSize < 1) {
			System.err.println("堆中已经没有元素!");
			return -1;
		}
		int max = queue[0];
		queue[0] = queue[heapSize-1];
		heapSize--;
		maxHeapify(queue, 1);
		return max;
	}
	
	
	/**
	 * 之前介绍的保持最大堆的算法
	 * @param array
	 * @param index
	 */
	private  void maxHeapify(int[] array, int index) {
		int l = index * 2;
		int r = l + 1;
		int largest;
		//如果左叶子节点索引小于堆大小，比较当前值和左叶子节点的值，取值大的索引值
		if (l <= heapSize && array[l-1] > array[index-1]) {
			largest = l;
		} else {
			largest = index;
		}
		//如果右叶子节点索引小于堆大小，比较右叶子节点和之前比较得出的较大值，取大的索引值
		if (r <= heapSize && array[r-1] > array[largest-1]) {
			largest = r;
		}
		//交换位置，并继续递归调用该方法调整位置。
		if (largest != index) {
			int temp = array[index-1];
			array[index-1] = array[largest-1];
			array[largest-1] = temp;
			maxHeapify(array, largest);
		}
	}
	
	public int[] getQueue() {
		return queue;
	}
}

package lhz.algorithm.chapter.six;
/**
 * "排序"，《算法导论》6.4章节
 * 利用之前实现的构建MaxHeap和MaxHeapify算法完成排序。
 * 伪代码：
 * HEAPSORT(A)
 * 1 BUILD-MAX-HEAP(A)
 * 2 for i <- length[A] downto 2
 * 3 do exchange A[1] <-> A[i]
 * 4 heap-size[A] <- heap-size[A] - 1
 * 5 MAX-HEAPIFY(A, 1)
 * @author lihzh(OneCoder)
 * @OneCoder-Blog http://www.coderli.com
 */
public class HeapSort {
	
	private static int[] input = new int[] {16, 14, 10, 8, 7, 9, 3, 2, 4, 1};

	public static void main(String[] args) {
		//堆排序
		heapSort();
		//打印数组
		printArray();
	}
	
	/**
	 * 堆排序，《算法导论》原文摘要：
	 * The heapsort algorithm starts by using BUILD-MAX-HEAP to build a max-heap on the input
	 * array A[1 - n], where n = length[A]. Since the maximum element of the array is stored at the
	 * root A[1], it can be put into its correct final position by exchanging it with A[n]. 
	 * If we now &quot;discard&quot; node n from the heap (by decrementing heap-size[A]), we observe that 
	 * A[1 , (n -1)] can easily be made into a max-heap. The children of the root remain max-heaps, 
	 * but the new root element may violate the max-heap property. All that is needed to restore 
	 * the maxheap property, however, is one call to MAX-HEAPIFY(A, 1), which leaves a max-heap 
	 * in A[1, (n - 1)]. The heapsort algorithm then repeats this process for the max-heap of size 
	 * n - 1 down to a heap of size 2.
	 * 复杂度：
	 * 由之前分析可知，buildMaxHeap复杂度为O(n lg n)，运行一次。
	 * maxHeapify的复杂度为O(lg n)，运行n-1次。
	 * 综上，复杂度为O(n lg n)。
	 */
	private static void heapSort() {
		int length = input.length;
		//构造max-heap
		buildMaxHeap(input, length);//交换位置
		for (int i = length - 1; i > 0; i--) {
			int temp = input[i];
			input[i] = input[0];
			input[0] = temp;
			maxHeapify(input, 1, i);
		}
	}

	private static void buildMaxHeap(int[] array, int heapSize) {
		for (int i = heapSize / 2; i > 0; i--) {
			maxHeapify(array, i, heapSize);
		}
	}
	
	private static void maxHeapify(int[] array, int index, int heapSize) {
		int l = index * 2;
		int r = l + 1;
		int largest;
		//如果左叶子节点索引小于堆大小，比较当前值和左叶子节点的值，取值大的索引值
		if (l <= heapSize && array[l-1] > array[index-1]) {
			largest = l;
		} else {
			largest = index;
		}
		//如果右叶子节点索引小于堆大小，比较右叶子节点和之前比较得出的较大值，取大的索引值
		if (r <= heapSize && array[r-1] > array[largest-1]) {
			largest = r;
		}
		//交换位置，并继续递归调用该方法调整位置。
		if (largest != index) {
			int temp = array[index-1];
			array[index-1] = array[largest-1];
			array[largest-1] = temp;
			maxHeapify(array, largest, heapSize);
		}
	}
	
	private static void printArray() {
		for (int i : input) {
			System.out.print(i + " ");
		}
	}
}

/**
 * "选择排序"，《算法导论》习题2.2-2 
 * Consider sorting n numbers stored in array A by first
 * finding the smallest element of A and exchanging it with the element in A[1].
 * Then find the second smallest element of A, and exchange it with A[2].
 * Continue in this manner for the first n - 1 elements of A. Write pseudocode
 * for this algorithm, which is known as selection sort . What loop invariant
 * does this algorithm maintain? Why does it need to run for only the first n -
 * 1 elements, rather than for all n elements? Give the best-case and worst-
 * case running times of selection sort in θ- notation. 
 * 伪代码：
 * 	for i <- 1 to length[A]-1
 * 		key <- A[i]
 * 		index <- i
 * 		for j <- 2 to length[A]
 * 			key = key < A[j] ? key : A[j];
			index = key < A[j] ? index : j;
 * 		A[index] = A[i];
		A[i] = key;	
 * @author lihzh(OneCoder)
 * @OneCoder-Blog http://www.coderli.com
 */
public class SelectionSort {
	
	private static int[] input = new int[] { 2, 1, 5, 4, 9, 8, 6, 7, 10, 3 };

	public static void main(String[] args) {
		for (int i=0; i<input.length-1; i++) {//复杂度：n
			int key = input[i];
			int index = i;
			//比较当前值和下一个值的关系，记录下较小值的值和索引数，用于交换。
			for (int j=i+1; j<input.length; j++) {//复杂度：1+2+...+(n-1)=θ(n^2)
				key = key < input[j] ? key : input[j];
				index = key < input[j] ? index : j;
			}
			input[index] = input[i];
			input[i] = key;
		}
		/*
		 * 复杂度分析：
		 * 最坏情况下，复杂度为：n*n=n^2(若略微精确的计算即为：n-1+1+2+...+n-1=(2+n)*(n-1)/2,
		 * 所以复杂度仍为n^2。
		 * 最优情况下，由于不论原数组是否排序好，均需要全部遍历以确定当前的最小值，所以复杂度不变仍未n^2。
		 * 
		 */
		//打印数组
		printArray();
	}
	
	private static void printArray() {
		for (int i : input) {
			System.out.print(i + " ");
		}
	}

}

/**
 *  "插入排序 "，对少量元素进行排序的有效算法。
 *  《算法导论》原文摘要：
 * Insertion sort works the way many people sort a hand
 * of playing cards. We start with an empty left hand and the cards face down on
 * the table. We then remove one card at a time from the table and insert it
 * into the correct position in the left hand. To find the correct position for
 * a card, we compare it with each of the cards already in the hand, from right
 * to left, as illustrated in Figure 2.1. At all times, the cards held in the
 * left hand are sorted, and these cards were originally the top cards of the
 * pile on the table. 
 * 伪代码如下： 
 * for j<- 2 to length[A] 
 * 	do key <- A[j] 
 * 		>Insert A[j] into the sorted sequence A[1..j-1] （>符号代表后面的部分是注释）
 * 		i <- j-1 
 * 		while i>0 and A[i]>key 
 * 			do A[i+1] <- A[i] 
 * 			i <- i-1 
 * 		A[i+1] <- key 
 * 算法复杂度：n^2
 * @author lihzh(OneCoder)
 * @OneCoder-Blog http://www.coderli.com
 */
public class InsertionSort {

	private static int[] input = new int[] { 2, 1, 5, 4, 9, 8, 6, 7, 10, 3 };

	public static void main(String[] args) {
		//从数组第二个元素开始排序，因为第一个元素本身肯定是已经排好序的
		for (int j = 1; j < input.length; j++) {// 复杂度 n
			int key = input[j];
			int i = j - 1;
			//依次跟之前的元素进行比较，如果发现比前面的原素小，则交换位置，最终完成排序。
			while (i >= 0 && input[i] > key) {//复杂度：1+2+...+(n-1)=&Theta;(n^2)
				input[i + 1] = input[i];
				input[i] = key;
				i--;
			}
		}
		/*
		 * 所以最终复杂度为n*n=n^2。最优情况下（即都已经排列好的情况下），第二个n=1， 所以在最优情况下，复杂度为n。
		 */
		// 打印数组
		printArray();
	}

	private static void printArray() {
		for (int i : input) {
			System.out.print(i + " ");
		}
	}
}

/**
 * 《算法导论》习题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 + " ");
		}
	}
}

/**
 * 快速排序，《算法导论》第七章
 * @author lihzh(OneCoder)
 * @OneCoder-Blog http://www.coderli.com
 */
public class QuickSort {
	
	//待排数组
	private static int[] input = new int[] { 2, 1, 5, 4, 9, 8, 6, 7, 10, 3 };

	public static void main(String[] args) {
		//快速排序
		quickSort(input, 0, input.length - 1);
		//打印数组
		printArray();
	}
	
	/**
	 * 快速排序，伪代码：
	 * QUICKSORT(A, p, r)
	 * 1 if p < r
	 * 2 	then q → PARTITION(A, p, r)
	 * 3 		QUICKSORT(A, p, q - 1)
	 * 4 		QUICKSORT(A, q + 1, r)
	 * 
	 * PARTITION(A, p, r)
	 * 1 x → A[r]
	 * 2 i → p - 1
	 * 3 for j → p to r - 1
	 * 4 	do if A[j] <= x
	 * 5 		then i → i + 1
	 * 6 			exchange A[i] ⟷ A[j]
	 * 7 exchange A[i + 1] ⟷ A[r]
	 * 8 return i + 1
	 * 复杂度，最坏情况下：θ(n^2)
	 * 一般平衡情况：θ(nlgn)
	 * @param array 待排数组
	 * @param from 起始位置
	 * @param to 终止位置
	 */
	private static void quickSort(int[] array, int from, int to) {
		if (from < to) {
			int temp = array[to];
			int i = from - 1;
			for (int j = from; j < to; j++) {
				if (array[j] <= temp) {
					i++;
					int tempValue = array[j];
					array[j] = array[i];
					array[i] = tempValue;
				}
			}
			array[to] = array[i+1];
			array[i+1] = temp;
			quickSort(array, from, i);
			quickSort(array, i + 1, to);
		}
	}

	private static void printArray() {
		for (int i : input) {
			System.out.print(i + &quot; &quot;);
		}
	}
}