优先队列

      在堆排序基础上顺便实现下优先队列，纯粹为实现下优先队列的思想，也顾不上代码丑陋了，嘿嘿，自己学习。

 

public class PriorityQueue<T extends Comparable<T>> {

	/**
	 * 和对排序中一样，第零个元素不做用
	 */
	private T[] queue;
	
	private int heapSize;
	
    /**
     * 初始化队列
     * @param a
     */
	@SuppressWarnings("unchecked")
	public void initPriorityQueue(T[] a){
		HeapSortor.buildMaxHeap(a);
		heapSize = a.length - 1;
		queue = (T[]) Array.newInstance(Comparable.class, 100);
		for(int i = 1; i < a.length; ++i)
			queue[i] = a[i];
		a = null;
	}
	
	/**
	 * 获取优先多列中第一个元素
	 * @return
	 */
	public T maxItem(){
		return queue[1];
	}
	
	/**
	 * 从队列中删除并返回最大元素，同时通过HeapSortor.maxHeapify保持优先队列特性
	 * @return
	 */
	public T extractMax(){
		T max = queue[1];
		HeapSortor.swap(queue,1, heapSize);
		heapSize--;
		HeapSortor.maxHeapify(queue, 1, heapSize);
		return max;
	}
	
	/**
	 * 将队列的第i个元素增加到key，然后调整使得队列保持优先队列特性
	 * @param key
	 * @param i
	 */
	public void increaseKey(T key, int i){
		if( key.compareTo(queue[i]) < 0 )
			throw new RuntimeException("The key is not greater than queue[i]");
		queue[i] = key;
		int parent = i/2;
		while( parent > 0 && queue[parent].compareTo(queue[i]) < 0){
			HeapSortor.swap(queue, i, parent);
			i = parent;
		}
	}
	/**
	 * 插入关键字key到优先多列中
	 * @param key
	 */
	public void insert(T key){
		queue[++heapSize] = key;
		increaseKey(key, heapSize);
	}
}