二叉堆實作優先隊列

• 适用範圍：

  許多應用程式都需要處理有序的元素，但不一定要求它們全部有序，或是不一定要一次就将它們排序。很多情況下我們會搜集一些元素，處理目前鍵值最大的元素等操作。

• 優先隊列實作原理：

  1.資料結構二叉堆能夠很好地實作優先隊列的基本操作。在二叉堆的數組中，每個元素都要保證大于等于另兩個特定位置的元素。相應的，這些位置的元素又至少要大于等于數組中的另外兩個元素。

  2.根節點是堆有序的二叉樹中的最大節點。

  3.我們使用一個數組來存儲資料，為了友善起見，根節點存儲在下标為1的位置，它需要大于等于21和21+1下标的節點，一次類推。

  4.在優先隊列中主要涉及到兩個操作，一個是上浮，一個是下沉，它們是用來維護堆結構。上浮就是當插入一個節點時把它放入數組的最後一個位置，然後通過上浮來把它移到正确的位置，下沉是當我們删除最大的節點（根節點）時，把根節點與最後一個節點交換，然後讓最後一個節點下沉來維護堆有序。

• 具體實作:

public class MaxPQ{
	private Integer[] pq;
	private int N=0;
	//構造方法，建立一個大小為cap+1的數組，存儲從1~cap下标的資料
	public MaxPQ(int cap){
		pq = new Integer[cap+1];
	}
	//判斷優先隊列是否為空
	public boolean isEmpty(){
		return N==0;
	}
	//擷取存儲的資料個數
	public int size(){
		return N;
	}
	//插入資料
	public void add(int v){
		pq[++N] = v;
		//上浮操作
		swim(N);
	}
	//删除并擷取最大的資料
	public int delMax(){
		int max = pq[1];
		exch(1,N--);
		pq[N+1] = null;
		//下沉操作
		sink(1)
		return max;
	}
	//下沉
	public void sink(int k){
		while(2*k<=N){
			int j = 2*k;
			if(pq[j]<pq[j+1]) j++;
			if(pq[j]<=pq[k]) break;
			//交換下标j,k的值
			exch(j,k);
			k = j;
		}
	}
	//上浮
	public void swim(int k){
		while(k>1&&pq[k]>pq[k/2]){
			exch(k,k/2);
			k = k/2;
		}
	}
	//交換兩個值
	public void exch(int i,int j){
		int temp = pq[i];
		pq[i] = pq[j];
		pq[j] = temp;
	}
}