数组堆化的递推和递归算法

package org.iSun.heisedeyueya;

public class Heap {

	public static void main(String args[]) {
		int[] array = new int[] { 24, 10, 90, 77, 16, 25, 33, 89, 67 };
		Heap.miniHeap(array, array.length);
		print(array);
	}

	/**
	 * 构造最小堆
	 * 
	 * @param array
	 * @param n
	 */
	public static void miniHeap(int[] array, int n) {

		int currentPos = (n - 2) >>> 1;// 计算第一个非叶子节点的位置
		while (currentPos >= 0) {// 递推循环直到堆顶位置
			recursionFilterDown(array, currentPos);
			// recurrenceFilterDown(array, currentPos);
			currentPos--;
		}
	}

	/**
	 * 交换
	 * 
	 * @param array
	 * @param i
	 * @param j
	 */
	public static void swap(int[] array, int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}

	/**
	 * 递归算法
	 * 
	 * @param array
	 * @param currentPos
	 *            当前的位置作为父亲节点
	 */
	public static void recursionFilterDown(int array[], int currentPos) {
		// 左孩子的位置
		int leftChild = currentPos * 2 + 1;
		// 右孩子的位置
		int rightChild = leftChild + 1;
		// 递归结束
		if (rightChild >= array.length || leftChild >= array.length)
			return;
		// 选择较小的孩子
		int minChild = array[leftChild] > array[rightChild] ? rightChild
				: leftChild;
		// 如果父亲节点的值大于较小的孩子那么交换
		if (array[currentPos] > array[minChild])
			swap(array, currentPos, minChild);
		// 递归调用，将孩子节点作为当前节点
		recursionFilterDown(array, minChild);
	}

	/**
	 * 递推算法
	 * 
	 * @param array
	 * @param currentPos
	 */
	public static void recurrenceFilterDown(int array[], int currentPos) {
		// 左孩子位置
		int child = currentPos * 2 + 1;
		while (child < array.length) {
			if (child + 1 < array.length && array[child + 1] < array[child])
				child++;
			// 已经满足小顶堆，直接跳出循环
			if (array[child] > array[currentPos])
				break;
			else {// 不满足就交换
				swap(array, child, currentPos);
				currentPos = child; // 改变当前节点为孩子节点
				child = 2 * currentPos + 1;// 计算孩子节点的位置
			}
		}
	}

	public static void print(int[] array) {
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + " ");
		}
	}
}