1 优先队列是至少允许下列两种操作的数据结构：insert和deleteMin操作，insert相当于入队，deleteMin则相当于在优先队列中的出队。
2 我们使用二叉堆（这里也就叫做堆），来实现这种数据结构。堆有两个重要性质，，其一是结构性，是一颗完全二叉树（高为h的二叉树 有2exp(h)到2exp(h+1)-1个节点）
其二是对序性质，如果我们考虑任意一个字树也是一个堆，那么任意节点应该<它的所有孩子
上代码：
package com.itany.binarydui;public class BinaryHeap<T extends Comparable<? super T>>{//堆实际上是通过一个数组容器来实现的 每个元素的下标十分有意义private static final int DEFAULT_CAPACITY=10;private int currentSize;//堆中的元素个数private T[] array;//堆数组public int getCurrentSize(){return currentSize;}public BinaryHeap(){this(DEFAULT_CAPACITY);}public BinaryHeap(int capacity){array=(T[])new Comparable[capacity];}//直接初始化时候就放入一个数组 不一个个insertpublic BinaryHeap(T[] arrayT){currentSize=arrayT.length;array=(T[])new Comparable[(currentSize+2)*11/10];int i=1;for(T t:arrayT)array[i++]=t;buildHeap();//把这些数组传进来的数据 优化成二叉堆}public void makeEmpty(){currentSize=0;array=null;}public boolean isEmpty(){return currentSize==0;}public void insert(T t){if(currentSize==array.length-1)enlargeArray(2*array.length+1);int hole=++currentSize;//创建一个空穴 再把空穴上浮//array[hole/2]就是array[hole]的父亲 不管hole是左儿子还是右儿子for(;hole>1 && t.compareTo(array[hole/2])<0;hole=hole/2){//把大的父亲 拿到下面来 使hole变成父亲的大小 这样就避免了三个式子来进行交换array[hole]=array[hole/2];}array[hole]=t;//把空穴填上值}public T findMin(){return array[1];}public T deleteMin() throws Exception{if(isEmpty())throw new Exception();T minItem=findMin();//找出最小之后 还需要对堆的结构根据堆序进行调整//因为删除了一个 所以多出了一个空位子 我们把最后一个值 放到最上面去 然后再从数组序号1(原来的最后一个值)开始进行相应的比大小调整array[1]=array[currentSize–];percolateDown(1);return minItem;}//向下过滤 调整堆结构 使之满足堆序性要求private void percolateDown(int hole){int child=0;//设置孩子的序号 child序号会不断改变//把 最上面的元素（不一定是最小的）先存储起来，因为如果它小的话 顶部的值会被下面的值给取代 等到Hole找到合适的位子时候 再把temp放到Hole里面去T temp=array[1];//currentSize>=2*hole表示当前hole有孩子时候就会继续进行下沉比较 如果没有孩子了 则比较结束 再给hole赋值for(;currentSize>=2*hole;hole=child){//每循环一次 child都要至少*2child=2*hole;//child!=currentSize表示还有右孩子 且右孩子比较小 那么 此时应该array[hole]和右孩子进行比较 否则就和左孩子比较if(child!=currentSize && array[child].compareTo(array[child+1])>0)child++;if(array[hole].compareTo(array[child])>0)array[hole]=array[child];elsebreak;}array[hole]=temp;}//建造一个堆private void buildHeap(){for(int i=currentSize/2;i>=1;i–){percolateDown(i);//对每一个父节点进行堆序优化}}//扩大数组private void enlargeArray(int newSize){T[] newArray=(T[])new Comparable[newSize];for(int i=0;i<array.length;i++){newArray[i]=array[i];}array=newArray;}}package com.itany.binarydui;public class Test{public static void main(String[] args){//BinaryHeap<Integer> bh=new BinaryHeap<Integer>();//bh.insert(50);//bh.insert(30);//bh.insert(40);Integer[] it={50,30,40};BinaryHeap<Integer> bh=new BinaryHeap<Integer>(it);System.out.println(bh.getCurrentSize());try{System.out.print(bh.deleteMin()+" ");System.out.print(bh.deleteMin()+" ");System.out.print(bh.deleteMin()+" ");}catch (Exception e){e.printStackTrace();}}}
时间慢慢的流淌，人生有风雨阳光，
