1、优先级队列的底层是一个小根堆，故取队顶元素时，取的是最小的元素 它应该有两个基本的操作：一是返回最高优先级对象，二是添加新的对象 （需注意： 根据优先级队列输出的数组相当于用优先级队列将数组中的元素从小到大排了个序，但是与小根堆是不一样，优先级队列底层的小根堆是特殊的小根堆，但是所有的小根堆不一定都是像优先级队列那样的从小到大排序，小根堆只是根结点的数比左右孩子小罢了） PriorityQueue的特性： PriorityQueue是线程不安全的、PriorityBlockingQueue(另一种优先级队列)是线程安全的。 （1）在使用PriorityQueue时，必须导入PriorityQueue所在的包，即import java.util.PriorityQueue;； （2）PriorityQueue中放置的元素必须能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常； （3）不能插入null对象，否则会抛出NullPointerException异常； （4）没有容量限制，可以任意插入多个元素，其内部可以自动扩容； （5）插入和删除元素的时间复杂度为O(log2^N)；（实际是一棵二叉树） （6）PriorityQueue底层使用了堆数据结构。
2、常用接口介绍
3、插入/删除/获取优先级最高的元素
4、优先级队列的扩容说明：
如果容量小于64时，是按照oldCapacity*2+2的方式扩容的；如果容量大于等于64，是按照oldCapacity*1.5的方式扩容的；如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来进行扩容。 private void grow(int minCapacity{ int oldCapacity=queue.length; //Double size if small;else grow by 50% int newCapacity=oldCapacity+((oldCapacity<64)? (oldCapacity+2): (oldCapacity>>1)); //overflow-conscious code if(newCapacity-MAX_ARRAY_SIZE>0) newCapacity=hugeCapacity(minCapacity); queue=Arrays.copyOf(queue,newCapacity); }重要！！！ 5. 堆：一棵顺序(层序)存储的完全二叉树。(堆是一棵完全二叉树，可以层序的采用顺序的方式来高效存储，非完全二叉树不能用顺序的方式存储，会浪费空间 ) （1）大根堆：根结点的值大于左右孩子 （2）小根堆：根结点的值小于左右孩子
知道父亲结点i，求左右孩子结点：左孩子：(2i+1)；右孩子：(2i+2)知道孩子结点求父亲结点的公式：(n-1)/2 ,n是孩子结点6、建大、小根堆： 建堆的时间复杂度：O(n)；调整一次的时间复杂度：O(log2^n) 思路： （用大根堆举例）建立大根堆，需要进行：向下调整。从一棵完全二叉树的最后一棵子树开始调整，使根结点与左右孩子进行比较，哪个比较大，就把哪个调整为根结点；建立小根堆，需要进行：向上调整，其思路和建大根堆差不多。
插入一个元素调整前后状态比较：
import java.util.Arrays; public class TestHeap { public int[] elem;//将数组中的元素放到elem中是为了，确定该数组中有多少个元素，将元素的个数再放进usedSize中保存 public int usedSize; public TestHeap() { this.elem = new int[10]; } //---------------------------------------------------------------------------------------------------------------------- //1、创建大根堆 //在不需要返回值时，可以不用返回值，不一定非得用具有返回值的函数，用void也很好啊 public void creatHeap(int[] array){ for(int i=0;i<array.length;i++){ this.elem[i]=array[i]; this.usedSize++; } //经过这个循环的调整，自然堆就变成了大根堆 // i：每棵子树的根结点下标 for(int i=(this.usedSize-1-1)/2;i>=0;i--){ adjustDown(i,this.usedSize); } } //root：每棵子树开始的位置；len：结束位置 public void adjustDown(int root,int len){ //向下调整的函数。（建立小根堆需要向上调整，只用改变下面注释的部分就可以了） int parent=root; int child=2*parent+1; while(child<len){ //1、child+1是当前子树右孩子的下标，该条件的意思是满足有右孩子并且该子树的左孩子小于右孩子时，需要调整的下标就改为右孩子，所以child++ if(child+1<len&&this.elem[child]<this.elem[child+1]){ //if(child+1<len&&this.elem[child]>this.elem[child+1]){ //小根堆（小的数往上调整） child++; } //代码指向这里，c表示最大值下标 if(this.elem[child]>this.elem[parent]){ //if(this.elem[child]<this.elem[parent]){ //小根堆（小的数往上调整） //交换 int temp=this.elem[parent]; this.elem[parent]=this.elem[child]; this.elem[child]=temp; parent=child; child=2*parent+1; }else{ break; } } } //---------------------------------------------------------------------------------------------------------------------- //2、堆的插入数据 //思路：将要插入的数据放在堆的最后一个元素，然后通过向上调整，将该数据调整到合适的位置 //首先判断堆(用数组存储的)是否是满的 public boolean isFull(){ return this.usedSize==this.elem.length; } public void push(int val){ //判断堆是否是满的，满了就扩容 if(isFull()){ this.elem=Arrays.copyOf(this.elem,2*this.elem.length);//扩容 } //放到数组的最后一个位置，进行调整 this.elem[this.usedSize]=val; this.usedSize++;// usedSize是11 adjustUp(this.usedSize-1); } //向上调整 public void adjustUp(int child){ int parent=(child-1)/2; while(child>0){ if(this.elem[child]>this.elem[parent]){ int temp=this.elem[parent]; this.elem[parent]=this.elem[child]; this.elem[child]=temp; child=parent; parent=(child-1)/2; }else{ break; } } } //------------------------------------------------------------------------------------------------------------------ //3、堆的删除数据，删除的是堆顶元素 //思路：删除的肯定是堆(这个堆一定是一个大堆或者小堆)顶元素，那么就需要用数组的最后一个元素替换堆顶元素，然后通过向下调整的方式重新调整成堆 public void pop(){ //没有参数是因为默认删除的是堆顶元素，所以不用传参 //数组是否为空 if(isEmpty()){ return; } //交换最后一个元素和堆顶元素（或者直接将最后一个元素赋值给堆顶元素，将堆顶元素覆盖也可以） int tmp=this.elem[0]; this.elem[0]=this.elem[this.usedSize-1]; this.elem[this.usedSize-1]=tmp; //this.elem[0]=this.elem[this.usedSize-1]; this.usedSize--; //调整0号下标位置的元素 adjustDown(0,this.usedSize);//不用再减1，是因为adjustDown函数里while(child<len)是小于号，没有= } public boolean isEmpty(){ //判断堆是否为空 return this.usedSize==0; } //---------------------------------------------------------------------------------------------------------------------- //4、取堆顶元素 public int peek(){ if(isEmpty()){ return -1; }else{ return this.elem[0]; } } //---------------------------------------------------------------------------------------------------------------------- //5、堆排序（时间复杂度：O(n*log2^n)；空间复杂度：O(1)） //思路：应该建立的是大根堆(若是建立小根堆，只知道最顶端元素是最小的，其余的元素无法知道其排序)， //最顶端的元素肯定是最大的，每次将顶端元素和最后一位元素(使最后一位元素的下标为end)交换， //交换完之后要向下调整，使第二(三、四、五、、、)大的元素成为堆顶元素，再使end--，循环，直至end=0） //这时候的堆就是从大到小的排序了 public void heapSort(){//进行这一步时，大堆已经建立好了，需要将大堆转换为特殊的小堆，就是使元素从小到大的排序 int end=this.usedSize-1; while(end>0){ //交换0号和end的位置 int temp1=this.elem[end]; this.elem[end]=this.elem[0]; this.elem[0]=temp1; //然后调整 adjustDown(0,end);//这里是end的原因是：第一次交换完，end在9号下标那个位置，调整的时候只需要调整0~8就可以了，在adjustDown函数里，是不包括end的 end--; } } //打印数组，之所以是用函数是因为，若输出array.length长度的数据，结果可能会包括很多0，影响结果的观看 public void show(){ for(int i=0;i<this.usedSize;i++){ System.out.printf(this.elem[i]+" "); } System.out.println(); } public static void main(String[] args) { TestHeap th=new TestHeap(); int[] array={27,15,19,18,28,34,65,49,25,37}; System.out.printf("创建的大堆："); th.creatHeap(array); th.show();//65 49 34 25 37 27 19 18 15 28 System.out.printf("插入一个数据:80 :"); th.push(80); th.show();//80 65 34 25 49 27 19 18 15 28 37，之所以是这个结果是因为，之前elem里存的是已经建立好的大堆，所以直接在该大堆上进行改造即可 System.out.printf("删除堆顶元素:"); th.pop(); th.show();//65 49 34 25 37 27 19 18 15 28 System.out.println("堆顶元素："+th.peek());//65 System.out.printf("堆排序的结果："); th.heapSort(); th.show(); } }执行结果：
