二叉堆实现优先队列

• 适用范围：

  许多应用程序都需要处理有序的元素，但不一定要求它们全部有序，或是不一定要一次就将它们排序。很多情况下我们会搜集一些元素，处理当前键值最大的元素等操作。

• 优先队列实现原理：

  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;
	}
}