堆Heap

public class Heap {
	public static void siftUp(int[] array, int i) {
		if (array == null || array.length <= 1 || i < 0 || i > array.length) {
			return;
		}
		while (true) {
			if (array[(i - 1) / 2] < array[i]) {
				swap(array, i, (i - 1) / 2);
			} else {
				break;
			}
			i = (i - 1) / 2;
		}
	}

	public static void siftDown(int[] array, int i) {
		if (array == null || array.length <= 1 || i < 0 || i > array.length) {
			return;
		}
		while (true) {
			int left = 2 * i + 1;
			int right = 2 * i + 2;
			if (right >= array.length) {
				if (left < array.length && array[i] < array[left]) {
					swap(array, i, left);
				}
				break;
			}
			int target = array[left] > array[right] ? left : right;
			if (array[target] > array[i]) {
				swap(array, i, target);
			}
			i = target;
		}
	}

	public static void siftDown(int[] array, int end, int i) {
		if (array == null || i < 0 || i > end) {
			return;
		}
		while (true) {
			int left = 2 * i + 1;
			int right = 2 * i + 2;
			if (right > end) {
				if (left < end && array[i] < array[left]) {
					swap(array, i, left);
				}
				break;
			}
			int target = array[left] > array[right] ? left : right;
			if (array[target] > array[i]) {
				swap(array, i, target);
			}
			i = target;
		}
	}

	/**
	 * put the element to insert to the last
	 * 
	 * @param array
	 * @param i
	 */
	public static void insert(int[] array) {
		siftUp(array, array.length - 1);
	}

	public static void delete(int[] array, int i) {
		if (array == null || array.length <= 1 || i < 0 || i > array.length) {
			return;
		}
		int tmp = array[i];
		array[i] = -1;
		if (i == array.length) {
			return;
		}
		swap(array, i, array.length - 1);
		if (array[i] > tmp)
			siftUp(array, i);
		else
			siftDown(array, i);
	}

	public static int deleteMax(int[] array) {
		int result = array[0];
		delete(array, 0);
		return result;
	}

	public static void makeHeap(int[] array) {
		if (array == null || array.length <= 1) {
			return;
		}

		for (int i = (array.length - 2) / 2; i >= 0; i--) {
			siftDown(array, i);
		}
	}

	public static void heapSort(int[] array) {
		if (array == null || array.length <= 1) {
			return;
		}
		makeHeap(array);
		for (int i = array.length - 1; i >= 0; i--) {
			swap(array, 0, i);
			siftDown(array, i - 1, 0);
		}
	}

	public static void swap(int[] array, int i, int j) {
		int tmp = array[i];
		array[i] = array[j];
		array[j] = tmp;
	}

	public static void main(String[] args) {
		int[] array = { 20, 17, 9, 10, 31, 4, 5, 3, 7, 5 };
		Heap.siftUp(array, 4);
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + " ");
		}
		System.out.println();

		int[] array2 = { 2, 17, 9, 10, 11, 4, 5, 3, 7, 5 };
		Heap.siftDown(array2, 0);
		for (int i = 0; i < array2.length; i++) {
			System.out.print(array2[i] + " ");
		}
		System.out.println();

		int[] array3 = { 20, 17, 9, 10, 11, 4, 5, 3, 7, 5, 30 };
		Heap.insert(array3);
		for (int i = 0; i < array3.length; i++) {
			System.out.print(array3[i] + " ");
		}
		System.out.println();

		int[] array4 = { 20, 17, 9, 10, 11, 4, 5, 3, 7, 5 };
		Heap.delete(array4, 5);
		for (int i = 0; i < array4.length; i++) {
			System.out.print(array4[i] + " ");
		}
		System.out.println();

		int[] array5 = { 5, 6, 3, 7, 8, 1, 10 };
		Heap.heapSort(array5);
		for (int i = 0; i < array5.length; i++) {
			System.out.print(array5[i] + " ");
		}
		System.out.println();
	}
}