[java基础-集合篇]优先队列PriorityQueue结构与源码解析

优先队列PriorityQueue

优先级队列表示为平衡二进制堆：

queue[n] 的两个子级是 queue[2*n+1] 和 queue[2*（n+1）]。

注：左子节点index=2*parentIndex+1,右子节点index=2*parentIndex+2,源码中计算parent位置时就是这样反过来计算的

优先级队列按 comparator 排序，如果 comparator 为 null，则按元素的自然排序排序：对于堆中的每个节点 n 和 n 的每个后代 d，n

PriorityQueue 是一个基于优先级堆的无界优先级队列实现，它可以确保每次出队的元素都是队列中优先级最高（最小的）的元素。

PriorityQueue结构

PriorityQueue结构上是一个基于数组的“完全二叉树”，且“任意节点的值<=子节点的值”，是一个“小顶堆”。

完全二叉树：除最底层节点，其他层都是满的，并且最后一层的所有节点尽可能地靠左排列

PriorityQueue方法

add（E e）

实质是offer(E e)方法，元素首先被添加到数组末尾，然后通过siftUp方法向上调整位置以维持堆的性质

扩容grow(int minCapacity)

peek

取第一个元素

poll

取出第一个元素并删除。移除队列头部元素（即最小元素）时，会将数组最后一个元素移动到头部，然后通过siftDown方法向下调整位置以恢复堆的性质

两个方法和上浮方法一样，只是比较方式不同

PriorityQueue特点

不允许元素为null，无添加顺序（不会按照添加顺序来），自然顺序，线程不安全

使用位移运算代替乘除、提升运算效率。

PriorityQueue资料引用（推荐）

Java【优先级队列】详细图解 / 模拟实现 + 【PriorityQueue】常用方法介绍_java优先队列-CSDN博客