算法导论中堆相关算法的java实现

转自http://topic.csdn.net/u/20110518/09/6021fd63-3084-4fda-a4b6-da2fe58de367.html?seed=1655503227&r=73523235#r_73523235

对原贴的代码进行整理并做一些修改
import java.util.Comparator;

/**
 * 将堆调整成最大堆
 * 
 * @author Administrator
 * 
 */
public class Heap {

	/**
	 * 返回值为i/2
	 * @param i
	 * @return
	 */
	public static int parent(int i) {
		return (i - 1) >> 1;
	}

	/**
	 * 返回值为2*i
	 * @param i
	 * @return
	 */
	public static int left(int i) {
		return ((i + 1) << 1) - 1;
	}

	/**
	 * 返回值为2*i+1
	 * @param i
	 * @return
	 */
	public static int right(int i) {
		return (i + 1) << 1;
	}

	public static <T> void heapify(T[] a, int i, Comparator<? super T> c) {
		heapify(a, i, c, a.length);
	}
	
   public static <T> void heapify(T[] a, int i, Comparator<? super T> c, int size) {
      int l = left(i);
      int r = right(i);
      int next = i;
      if (l < size && c.compare(a[l], a[i]) > 0)
          next = l;
      if (r < size && c.compare(a[r], a[next]) > 0)
          next = r;
      if (i == next)
          return;
      swap(a, i, next);
      heapify(a, next, c, size);
  }

	
	 /**
	  * 对堆进行排序
	 * @param <T>
	 * @param a
	 * @param c
	 */
	public static <T> void heapSort(T[] a, Comparator<? super T> c) {
       buildHeap(a, c);
       for (int i = a.length - 1; i > 0; i--) {
           swap(a, 0, i);
           heapify(a, 0, c, i);
       }
   }
	 /**
	  * 交换数组值
	 * @param arr
	 * @param i
	 * @param j
	 */
	private static void swap(Object[] arr, int i, int j) {
		 Object tmp = arr[i];
		 arr[i] = arr[j];
		 arr[j] = tmp;
	 }
	 
	 /**
	  * 创建堆
	 * @param <T>
	 * @param a
	 * @param c
	 */
	public static <T> void buildHeap(T[] a, Comparator<? super T> c) {
		 for (int i = (a.length ) / 2 - 1; i >= 0; i--) {
			 heapify(a, i, c);
		 }
	 }

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// heapify test
		Integer[] temp  = null;
		temp = new Integer[] { 5, 2, 4, 6, 1, 3, 2, 6 };
		temp = new Integer[] { 16, 14, 8, 7, 9, 3, 2, 4,1 };

		Comparator<Integer> comp = new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {

				return o1 - o2;
			}
		};
		buildHeap(temp, comp);
		for (int i : temp) {
			System.out.print(i + " ");
		}
		System.out.println();
		heapSort(temp, comp);

		for (int i : temp) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

}