package jxau.blueDot.lyx;/** *  * @author lyx *	@下午7:59:36 * @TODO: * 	堆排序算法 *//** * 堆定义： * 	堆是有如下特点的二叉树： * 		（1）完全二叉树 * 		（2）常常用一个数组实现 * 		（3）堆中的每一个节点都满足堆的条件——每一个节点的关键字都大于（或等于） * 														    这个节点的子节点的关键字 *  *  堆分为最大堆和最小堆 *  	 最大堆：设数组a中存放了n个数据元素，数组下标从0开始 *  如果当数组下标2i+1(左子节点)
    
     = a[2i+1].key *  	  当数组下标2i+2(右子节点)
     
      = a[2i+2].key *  --说白了就是父节点的关键字大于左右子节点 *  则这样的数据结构称为最大堆。 *  	 *  	如果把有n个数据元素的数组a中的元素看作一棵完全二叉树，则a[0]对应着 *  该完全二叉树的根节点，a[1]对应着树根的左孩子节点，a[2]对应着树根的右孩子节点 *  以此类推。 *  	在此基础上，只需再调整所有非叶子节点的数组元素满足 *  	父节点的关键字大于左右子节点 这样的完全二叉树就是一个最大堆。 *   *  	最小堆：同理，父节点的关键字小于左右子节点 这样的完全二叉树就是一个最小堆。 *   *  堆的两个性质： *  	（1）最大堆的根结点是堆中值最大的数组元素，最小堆的根结点是堆中值最小的数据 *  元素，称堆的根结点元素为堆顶元素。 *  	（2）对于最大堆，从根结点到每个叶结点的路径上，数据元素组成的序列都是递减有 *  序的；对于最小堆，从根结点到每个叶结点的路径上，数据元素组成的序列都是递增有 *  序的 *   */  /** * 算法时间代价： * 	将待排数据元素集合构成一个完全二叉树结构，则每次选择出一个最大（或最小） * 的数据元素只需比较完全二叉树的数值为高度的次数，即log2n次，所以排序算法 * 的时间复杂度为O(nlog2n) * T(n) <= O(n)  + (n - 1)*O(log2(n))	 *     即等于第一次构造最大堆操作 加上  后面n-1次构造堆操作   其实由于n的减小，后面的O(log2(n))中的n也会减 * 小，所以这里用小于等于号 。最后得到的T(n) =O(nlog2(n)) */public class HeapSort {	 public static void swap(int[] data, int i, int j) {  	        if (i == j) {  	            return;  	        }  	        data[i] = data[i] + data[j];  	        data[j] = data[i] - data[j];  	        data[i] = data[i] - data[j];  	    }  	  	    public static void heapSort(int[] data) {  	        for (int i = 0; i < data.length; i++) {  	            createMaxdHeap(data, data.length - 1 - i);  	            swap(data, 0, data.length - 1 - i);  	            print(data);  	        }  	    }  	  	    /**	     * 	     * @void	     * @param data 	     * @param lastIndex：	     * 	创建堆	     */	    public static void createMaxdHeap(int[] data, int lastIndex) { 	    		    	//从根节点开始	        for (int i = (lastIndex - 1) / 2; i >= 0; i--) {  	            // 保存当前正在判断的节点  	            int k = i;  	            // 若当前节点的子节点存在  	            while (2 * k + 1 <= lastIndex) {  	                // biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点  	                int biggerIndex = 2 * k + 1;  	                if (biggerIndex < lastIndex) {  	                    // 若右子节点存在，否则此时biggerIndex应该等于 lastIndex  	                    if (data[biggerIndex] < data[biggerIndex + 1]) {  	                        // 若右子节点值比左子节点值大，则biggerIndex记录的是右子节点的值  	                        biggerIndex++;  	                    }  	                }  	                	                if (data[k] < data[biggerIndex]) {  	                    // 若当前节点值比子节点最大值小，则交换两者的值，交换后将biggerIndex值赋值给k  	                    swap(data, k, biggerIndex);  	                    k = biggerIndex;  	                    	                } else {  	                    break;  	                }  	            }  	        }  	    }  	  	    public static void print(int[] data) {  	        for (int i = 0; i < data.length; i++) {  	            System.out.print(data[i] + "\t");  	        }  	        System.out.println();  	    }  	    }