优先队列PriorityQueue，有空了解一下吗？

PriorityQueue这个队列不知道大家使用过吗，反正我用的很少，主要对它不是很了解，今天我带领大家剖析下PriorityQueue这个优先级队列。,顾名思义，PriorityQueue是优先队列的意思。优先队列的作用是能保证每次取出的元素都是队列中权值最小的。这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器。,图片,以上是PriorityQueue的类图,,运行结果：,图片,运行结果：,图片,PriorityQueue通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。,图片,上图中我们给每个元素按照层序遍历的方式进行了编号，如果你足够细心，会发现父节点和子节点的编号是有联系的，更确切的说父子节点的编号之间有如下关系：,leftNo = parentNo*2+1,rightNo = parentNo*2+2,parentNo = (nodeNo-1)/2,通过上述三个公式，可以轻易计算出某个节点的父节点以及子节点的下标。这也就是为什么可以直接用数组来存储堆的原因。,如果原长度比较小，大概就是扩展为两倍，否则就是增加50%，使用Arrays.copyOf方法拷贝数组。,参数k表示插入位置，x表示新元素。k初始等于数组大小，即在最后一个位置插入。代码的主要部分是：往上寻找x真正应该插入的位置，这个位置用k表示。,怎么找呢？新元素(x)不断与父节点(e)比较，如果新元素(x)大于等于父节点(e)，则已满足堆的性质，退出循环，k就是新元素最终的位置，否则，将父节点往下移(queue[k]=e)，继续向上寻找。,优先级可以有相同的，内部元素不是完全有序的，如果遍历输出，除了第一个，其他没有特定顺序。查看头部元素的效率很高，为O(1)，入队、出队效率比较高，为O(log2(N))，构建堆的效率为O(N)。根据值查找和删除元素的效率比较低，为O(N)。