学步园

优先级队列，数值越小，优先级越高。优先级越高的最新被删除，区别于普通的队列先进先出。

算法如下：

定义结点：

class Node {

	private int iData;

	public Node(int iData) {
		this.iData = iData;
	}

	public int getIData() {
		return iData;
	}

	public void setIData(int data) {
		iData = data;
	}
}

public class PriorityQueue_Heap {

	private Node[] heapNode;

	private static final int max_size = 50;// 最大结点数

	private int current_index = 0;

	private static final int max_Value = 50;//结点最大值

	public PriorityQueue_Heap(int size) throws InterruptedException {
		current_index = 0;
		heapNode = new Node[max_size];
		Random random = new Random();
		for (int i = 0; i < size; i++) {
			int value = random.nextInt(max_Value);
			buildMinHeap(value);
		}
	}

	/**
	 * 构造最小堆
	 * 
	 * @param value
	 * @return
	 */
	public boolean buildMinHeap(int value) {
		Node node = new Node(value);
		if (current_index == max_size) {
			return false;
		} else {
			heapNode[current_index] = node;
			tickleUp(current_index);
			current_index++;
			return true;
		}
	}

	/**
	 * 向上调整
	 * 
	 * @param current_index
	 */
	public void tickleUp(int current_index) {
		int parent = (current_index - 1) / 2;// 找到当前节点的父节点
		// 暂存当前节点值
		Node bottom = new Node(heapNode[current_index].getIData());
		while (current_index > 0
				&& heapNode[parent].getIData() > bottom.getIData()) {
			// 父节点下移
			heapNode[current_index].setIData(heapNode[parent].getIData());
			current_index = parent;
			parent = (current_index - 1) / 2;
		}
		heapNode[current_index] = bottom;
	}

	/**
	 * 向下调整
	 * 
	 * @param index
	 */
	public void tickleDown(int index) {
		int minChild;//当前结点两个孩子结点中大的那个下标
		Node top = heapNode[index];
		while (index < current_index / 2) {
			int leftChild = 2 * index + 1;
			int rightChild = leftChild + 1;
			// 如果右节点存在，并且由节点大于左节点。则右节点就是最大的节点
			if (rightChild < current_index
					&& heapNode[rightChild].getIData() < heapNode[leftChild]
							.getIData()) {
				minChild = rightChild;
			} else {
				minChild = leftChild;
			}
			// 找到了这样的节点比字节的还小
			if (top.getIData() < heapNode[minChild].getIData()) {
				break;
			} else {
				heapNode[index] = heapNode[minChild];
				index = minChild;
			}
		}// end while
		heapNode[index] = top;
	}

	/**
	 * 取优先级最高的节点
	 * 
	 * @return
	 */
	public int min() {
		return heapNode[0].getIData();
	}

	/**
	 * 往大堆中插入一个新节点
	 * 
	 * @param key
	 */
	public void insert(int key) {
		buildMinHeap(key);
	}

	/**
	 * 从大堆中删除优先级最高的节点，同时把最后一个节点放入到根节点，然后调整
	 * 
	 * @param key
	 */
	public Node delMin() {
		Node root = heapNode[0];
		if (current_index == 0) {
			return null;
		}
		heapNode[0] = heapNode[--current_index];
		// 向下刷新
		tickleDown(0);
		return root;
	}

	/**
	 * 显示大堆
	 */
	public void disHeap() {
		System.out.print("heapArray:");
		for (int i = 0; i < heapNode.length; i++) {
			if (heapNode[i] != null) {
				System.out.print(heapNode[i].getIData() + ",");
			} else
				break;
		}
		System.out.println(" ");
	}

	public static void main(String[] args) throws InterruptedException {
		PriorityQueue_Heap ph = new PriorityQueue_Heap(10);
		ph.disHeap();
		System.out.println("min:" + ph.min());
		int inValue = 20;
		System.out.println("insert value:"+inValue);
		ph.insert(inValue);
		ph.disHeap();
		System.out.println("del  value:"+inValue);
		System.out.println("the min="+ph.delMin().getIData());
		ph.disHeap();
	}