深入理解javapriorityqueue-编程开发技术

《深入理解javapriorityqueue-编程开发技术》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、深入理解JavaPriorityQucuc-编程开发技术深入理解JavaPriorityQueue原文出处：CarpenterLeePriorityQueue本文github地址Java中PriorityQueue通过二叉小顶堆实现，可以用一棵完全二叉树表示。本文从Queue接口函数出发，结合生动的图解，深入浅出地分析PriorityQueue每个操作的具体过程和时间复杂度，将让读者建立对PriorityQueue建立清晰而深入的认识。总体介绍前面以｝^^ArrayDeque为例讲解了Stack和Queu

2、e,其实还有一种特姝的队列叫做PriorityQueue,即优先队列。优先队列的作用是能保证每次取出的元素都是队列中权值最小的（Java的优先队列每次取最小元素，C++的优先队列每次取最大元索）。这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序（naturalordering）,也可以通过构造时传入的比较器（Comparator,类似丁C++的仿函数）。Java中PriorityQueue实现了仙接口，不允许放入null元索；其通过堆实现，具体说是通过完全二叉树（completebinary

3、tree｝实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。PriorityQueue通过用?Object[]queuei%▲10上图屮我们给每个元素按照层序遍丿力的方式进行了编号，如果你足够细心，会发现父节点和子节点的编号是有联系的，更确切的说父子节点的编号之间有如下关系：leftNo=parentNo*2+lrightNo二parcntNo*2+2parentNo=(nodeNoT)/2通过上述三个公式，可以轻易计算

4、出某个节点的父节点以及了节点的下标。这也就是为什么可以直接用数组来存储堆的原因。PriorityQueue的peek()和element操作是常数时■间，add(),?offer(),无参数的remove()以及pol1()方法的时间复杂度都是1og(N)。方法剖析add()和offer()add(Ee)和offer(Ee)的语义相同,都是向优先队列中插入元素,只是Queue接口规定二者对插入失败时的处理不同，前者在插入失败时抛出异常，后则则会返回false。对J;PriorityQueue这两个方法其实

5、没什么差别。PriorityQueue.789(a)101511新加入的元素可能会破坏小顶堆的性质，因此需要进行必要的调整。//offer(Ee)publicbooleanoffer(Ee){if(e==null)//不允许放入null元素thrownewNullPointcrExccption();modCount++;inti二size;if(i>二queue,length)grow(i+1);//自动扩容size二i+1;if(i==0)//队列原来为空，这是插入的第一个元索queue[0]二e;e

6、lsesiftUp(i,e);//调整returntrue;}上述代码中,扩容函数grow()类似于ArrayList里的grow()函数，就是再申请一个更大的数组，并将原数组的元素复制过去，这里不再赘述。需要注意的是siftUp(intk,Ex)方法，该方法用于插入元索x并维持堆的特性。//siftUp()privatevoidsiftUp(intk,Ex){while(k>0){intparent=(k-1)>>>1;//parentNo=(nodeNo-1)/2Objecte二queue[paren

7、t];if(comparator,compare(x,(E)e)>二0)//调用比较器的比较方法break;queue[k]=e;k=parent;}queue[k]二x;}新加入的元索x可能会破坏小顶堆的性质，因此需要进行调整。调整的过程为：从k指定的位置开始，将X逐层与当前点的parent进行比较并交换，直到满足x>=queue[parent]为止。注意这里的比较可以是元素的自然顺序，也可以是依靠比较器的顺序。element()和peek()element()和peek()的语义完全相同，都是获取但不

8、删除队首元素，也就是队列屮权值最小的那个元素，二者唯一的区别是当方法失败吋前者抛出异常，后者返回nullo根据小顶堆的性质，堆顶那个元素就是全局最小的那个；由丁•堆用数组表示，根据下标关系，0下标处的那个元素既是堆顶元素。所以直接返回数组0下标处的那个元素即可。代码也就非常简洁：//peek()publicEpeek(){if(size==0)rcturnnull;return(E)queue[0];//0H标处的那个元素就是