Java集合Queue-PriorityQueue

2021-08-12 11:03:43 浏览数 (1)

优先队列有两种:最大优先队列,当前最大的元素优先出队;最小优先队列,当前最小的元素优先出队。

PriorityQueue 通过用数组表示的小顶堆来实现,具体结构如下图所示

首先任何结点都小于其左右子结点,除此之外,对于任何一个结点,假设它的下标为n:

  • 左子结点:2 * n 1
  • 右子结点:2 * n 2
  • 父结点:(n 1) / 2

1 构造

  1. 成员变量
  1. 构造函数

看起来有7种实际上只有4种

除了第一种,其它的是对PriorityQueueSortedSet 和其它Collection 进行初始化,其中SortedSet 本身就已经是排好序,所以不需要经过什么特殊处理,而其它的则需要调用heapify()进行处理。

进入heapify() 源码可以看到用到了siftDown() 函数,后面会讲到

2 增加

addoffer 的语义是相同的,add也是调用了offer ,主要的是扩容函数grow 和筛选函数siftUp 。扩容函数后面讲,先来分析筛选函数(siftUp/siftDown)

假设待插入的元素是4,这个gif图有个缺陷就是,比较完后,并不是4和待比较的结点交换,而是单纯把父节点移下来。

3 删除

siftDownsiftUp 差不多,都是包含有比较器和没有比较器两种方法,这里就拿一个分析即可。

4 查询

由于查询并没有涉及结构的变化和调整,所以源码是非常简单的。

5 扩容

扩容发生在添加元素的时候,当size >= queue.length 的时候就会发生扩容。

0 人点赞