package com.csdhsm.sort;

/** 
 * @Title: HeapSort.java
 * @Package: com.csdhsm.sort
 * @Description 堆排序
 * @author Han
 * @date 2016-4-3 下午3:55:18 
 * @version V1.0
 */ 
  	
public class HeapSort {
	 
	/** 
	 * @Description 调整堆
	 * @author Han
	 * @param arr
	 * @param i
	 * @param size  
	 */
	  	
	private void heapAdjust(int[] arr,int i,int size){
		
		int lchild = i*2+1;//i节点的左子节点
		int rchild = i*2+2;//i节点的右子节点
		
		/**
		 * 右子节点大于左子节点
		 */
		if(rchild < size && arr[rchild] > arr[lchild]){
			
			swap(arr,lchild,rchild);
		}
		
		/**
		 * 左子节点大于根节点
		 */
		if(lchild < size && arr[lchild] > arr[i]){
			
			swap(arr,lchild,i);
		}
	}
	
	/** 
	 * @Description 建立堆
	 * @author Han  
	 */
	  	
	private void buildHeap(int[] arr,int size){
		
		int i = 0;
		//依次调整各个堆
		for(i = size/2;i>=1;i--){
			
			heapAdjust(arr,i-1,size);
		}
	}
	
	public void sort(int[] arr,int len){
		
		buildHeap(arr,len);
		for(int i = len-1 ; i>=1;i--){
			
			//将有序堆中的第一个元素和最后一个元素交换，取出最后一个元素
			swap(arr,0,i);
			//将无序堆重新构造为有许多
			buildHeap(arr,i);
		}
	}
	 
	/** 
	 * @Description 自定义交换方法
	 * @author Han
	 * @param arr
	 * @param firstIndex
	 * @param secondIndex  
	 */
	  	
	private void swap(int arr[],int firstIndex,int secondIndex){
		
		int temp = arr[firstIndex];
		arr[firstIndex] = arr[secondIndex];
		arr[secondIndex] = temp;
	}
}