简单_二叉堆

堆是一种比较有用的数据结构，是二叉树的一种数组的表示形式。

最大堆和最小堆是二叉堆的两种形式。
　　最大堆：根结点的键值是所有堆结点键值中最大者。
　　最小堆：根结点的键值是所有堆结点键值中最小者。
　　而最大-最小堆集结了最大堆和最小堆的优点，这也是其名字的由来。
　　最大-最小堆是最大层和最小层交替出现的二叉树，即最大层结点的儿子属于最小层，最小层结点的儿子属于最大层。
　　以最大（小）层结点为根结点的子树保有最大（小）堆性质：根结点的键值为该子树结点键值中最大（小）项。

堆的实现代码如下：

package sunfa;

import java.util.Arrays;
import java.util.Random;

/**
 * 堆的性质： 在起始索引为 0 的“堆”中： <br>
 * 1) 堆的根节点将存放在位置 0 <br>
 * 2) 节点 i 的左子节点在位置 2 * i + 1 <br>
 * 3) 节点 i的右子节点在位置 2 * i + 2 <br>
 * 4) 节点 i 的父节点在位置 floor( (i - 1) / 2 ) : 注 floor 表示“取整”操作
 * 
 * 在起始索引为 1 的“堆”中： <br>
 * 1) 堆的根节点将存放在位置 1 <br>
 * 2) 节点 i 的左子节点在位置 2 * i <br>
 * 3) 节点 i 的右子节点在位置 2 *i + 1 <br>
 * 4) 节点 i 的父节点在位置 floor( i / 2 ) : 注 floor 表示“取整”操作
 * 
 * 以起始索引为1的堆比较好算
 * 
 * 可以参考：http://wxg6203.iteye.com/blog/668968
 */
public class MyHeap2 {
	private Integer[] heap;
	private int size = 0;
	private int DEFAULT_SIZE = 10;

	public MyHeap2(int n) {
		if (n > DEFAULT_SIZE) {
			DEFAULT_SIZE = n;
		}
		heap = new Integer[DEFAULT_SIZE];
	}

	/**
	 * 对整个堆进行堆化
	 */
	public void heapify() {
		for (int i = size / 2; i >= 1; i--) {
			fixDown(i);
		}
	}

	/** 获取根节点 */
	public Integer first() {
		return heap[1];
	}

	/** 获取最后一个节点 ,不保证最后一个节点是最大的,只能保证根节点是最大或最小的 */
	public Integer last() {
		return heap[size];
	}

	public int removeFirst() {
		int f = heap[1];
		heap[1] = heap[size];
		heap[size--] = null;
		fixDown(1);
		return f;
	}

	/**
	 * 下移
	 * 
	 * @param k
	 *            目标节点的索引
	 */
	private void fixDown(int k) {
		int j;// 目标节点的(左/右)子节点索引
		while ((j = k << 1) <= size && j > 0) {
			// 如果目标节点k的左子节点大于目标节点k的右子节点，那么重置子节点索引为较小的那个
			if (j < size && heap[j] > heap[j + 1])
				j++;
			if (heap[k] <= heap[j])
				break;
			swap(heap, k, j);
			k = j;// 非递归式下移搜索
		}
	}

	private void swap(Integer[] a, int i, int j) {
		Integer tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	// 向堆中添加元素,堆的根节点的索引是从1开始的
	public void add(Integer o) {
		if (size + 1 == heap.length)
			heap = Arrays.copyOf(heap, heap.length << 1);
		heap[++size] = o;// 堆根节点的索引从1开始,保留数组的第一个值为NULL
		// 每次新增元素后可能会破坏堆的性质，所以要进行上移操作。
		// 如果当前新增的元素比它的父节点要大，那么就要把当前元素和它的父节点进行交换，这么反复的直到根节点位置。这就是上移。
		fixUp(size);
	}

	/**
	 * 上移:即我们把该节点移动到它的父节点的位置，而让它的父节点到它的位置上，然后我们继续判断该节点，直到该节点不再大于它的父节点为止才停止“上移”。
	 * 
	 * @param k
	 *            父节点的位置
	 */
	private void fixUp(int k) {
		while (k > 1) {
			int j = k >> 1;// 根据堆的性质，每次根据当前节点的索引得到父节点的索引
			if (heap[j] <= heap[k])
				break;
			swap(heap, k, j);
			k = j;// 非递归式上移搜索
		}
	}

	public static void main(String[] args) {
		Random ran = new Random();
		int n = 20;
		Integer[] arr = new Integer[n];
		for (int i = 0; i < n; i++) {
			arr[i] = ran.nextInt(100);
		}
		System.out.println("arr:" + Arrays.toString(arr));
		MyHeap2 myheap2 = new MyHeap2(arr.length);
		for (int i = 0; i < arr.length; i++) {
			myheap2.add(arr[i]);
			System.out.println(Arrays.toString(myheap2.heap) + ",i:" + arr[i]
					+ ",size:" + myheap2.size);
		}

		System.out.println("removeFirst:");
		while (myheap2.size > 0) {
			System.out.println("remove:" + myheap2.removeFirst() + ",heap:"
					+ Arrays.toString(myheap2.heap));
		}
	}
}