首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Queue-PriorityQueue源码解析

Queue-PriorityQueue源码解析

作者头像
GreizLiao
发布2020-05-14 17:01:39
4820
发布2020-05-14 17:01:39
举报
文章被收录于专栏:足球是圆的足球是圆的

Queue队列通常是先进先出(FIFO),但也有特殊的非FIFO,如本文也分析的PriorityQueue。

Queue接口

Queue接口定义的方法:

添加元素接口:

  1. add(E e) -> 往队列添加一个元素,如果队列已满抛出IllegalStateException异常。
  2. offer(E e) -> 往队列添加一个元素,true成功,false失败,和add区别在与不会因为队列已满抛异常。

删除元素接口:

  1. remove() -> 删除队列头元素并返回该元素,如果队列为空抛出NoSuchElementException异常。
  2. E poll() -> 删除队列头元素并返回该元素,如果队列为空返回null(与remove不同)。

获取队列头元素接口:

  1. E element() -> 返回队列头部元素(没有删除),如果队列为空抛出NoSuchElementException异常。
  2. E peek() -> 返回队列头部元素(没有删除),如果队列为空返回null。

Queue常用的实现类

上图中列出的是Queue平时常用的实现类:

  1. ArrayBlockingQueue -> 有边界的数组形式实现的阻塞队列。
  2. LinkedBlockingQueue -> 有边界的链表形式实现的阻塞队列。
  3. PriorityQueue -> 无边界的二叉堆形式实现的优先级队列。
  4. DelayQueue -> 无边界的优先级形式实现的延迟队列。

PriorityQueue

PriorityQueue是基于二叉堆形式实现的无界队列。队列中元素类型必须是可比较的,构造函数如果没有传入Comparator默认是自然排序。

PriorityQueue结构

PriorityQueue继承了AbstractQueue,AbstractQueue实现Queue接口,即PriorityQueue拥有Queue的方法和特征。

Object[] queue:存放队列元素。

int DEFAULT_INITIAL_CAPACITY:默认的队列大小,默认值为11。

int size:PriorityQueue队列中元素个数。

int modCount:PriorityQueue队列修改次数。

Comparator<? super E> comparator:队列元素排序比较器。

int MAX_ARRAY_SIZE:队列最大值(Integer.MAX_VALUE - 8),VM的保留了8字节的 header words。

PriorityQueue示例

package com.juc.queue;

import java.util.PriorityQueue;
/**
 * Created on 2020/5/10 23:29.
 * @author Griez
 */
public class PriorityQueueTest {
    public static final PriorityQueue<Integer> QUEUE = new PriorityQueue<>();
    public static void main(String[] args) {
        for (int i = 10; i > 0 ; i--) {
            QUEUE.offer(i);
        }
        for (int i = 0; i < 10; i++) {
            System.out.println(QUEUE.poll());
        }
    }
}

创建一个存放Integer的PriorityQueue,采用默认的自然排序。并倒序的往PriorityQueue添加10-1。然后从PriorityQueue头部出队列并输出,输出结果是1-10升序。如果是让我们实现应该是入队时用插叙排序好并存放在queue数组中,但是这样实现往queue数组中添加和删除元素移动次数是不是最优的呢?接下来我们看一下Josh Bloch, Doug Lea是怎么样实现的。

PriorityQueue添加元素解析

java.util.PriorityQueue#offer
public boolean offer(E e) {
    if (e == null)  //《1》不能为空
        throw new NullPointerException();
    modCount++;		// 《2》修改次数加1
    int i = size;
    if (i >= queue.length) // 默认11
        grow(i + 1); // 《3》数组扩容
    size = i + 1;
    if (i == 0)		// 《4》直接把e赋值给0下标元素(顶部元素)
        queue[0] = e;
    else
        siftUp(i, e);	// 《5》筛选顶部元素
    return true;
}

《1》添加的元素不能为空,即PriorityQueue队列不可能存在null元素。 《2》修改次数加1。 《3》如果当前PriorityQueue元素数量大于等于数组容量需要对queue进行扩容操作。 《4》如果当前PriorityQueue为空,直接把e赋值给queue数组0下标(顶部元素)。 《5》通过二叉堆,筛选顶部元素。

java.util.PriorityQueue#grow
private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    // 《1》根据现有的容量选择增长倍数
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1)); 
    // overflow-conscious code
    // 《2》如果《1》计算出的容量比最大大,则以传入容量为准
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

《1》根据现有的容量选择增长倍数,如果现在的容量小于64,则容量直接增长一倍再加2;否则增长50%。 《2》如果《1》计算出的容量比最大大,则以传入容量为准。

java.util.PriorityQueue#siftUp
private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

如果构造PriorityQueue时传有特定比较器,就按特定比较器方式设置顶部元素,否则按默认自然比较器方式设置。

java.util.PriorityQueue#siftUpComparable
private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x; //《1》
    while (k > 0) {
        int parent = (k - 1) >>> 1; //《2》
        Object e = queue[parent];  //《3》
        if (key.compareTo((E) e) >= 0) //《4》
            break;
        queue[k] = e;  //《5》
        k = parent;
    }
    queue[k] = key; //《6》
}

《1》添加的元素必须是Comparable子类,可比较的。 《2》计算父节点下标。 《3》得到父节点元素。 《4》跟父节点元素作比较,如果要添加的元素大于父节点元素则退出。 《5》把父节点的元素移动到数组下标k处,然后把父节点下标赋值给k,循环《1》 - 《4》步骤。 《6》经过前面步骤最终确认需要添加的元素在queue下标,并存入数组。

添加10 - 8 该方法体现的数据结构。

添加7整个过程,用堆数据结构添加7的过程只交换了两次数据位置。如果用插叙排序这种极端情况所有数据都需要移动。

最小二叉堆特性是根节点元素值永远是最小的。

PriorityQueue删除元素解析

java.util.PriorityQueue#poll
public E poll() {
    if (size == 0) //《1》
        return null;
    int s = --size; //《2》
    modCount++; //《3》
    E result = (E) queue[0];//《4》
    E x = (E) queue[s];//《5》
    queue[s] = null;
    if (s != 0)
        siftDown(0, x);//《6》
    return result;
}

《1》如果队列为空,返回null。 《2》队列元素总数减1。 《3》修改次数加1。 《4》把堆头部元素取出,后面直接返回该元素。 《5》获取queue最后一个元素并把该位置设置null。 《6》重新筛选最小值为头部元素。

java.util.PriorityQueue#siftDown
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

如果构造PriorityQueue时传有特定比较器,就按特定比较器方式设置顶部元素,否则按默认自然比较器方式设置。

java.util.PriorityQueue#siftDownComparable
private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1; //《1》       // loop while a non-leaf
    while (k < half) {
        int child = (k << 1) + 1; //《2》 // assume left child is least
        Object c = queue[child];//《3》
        int right = child + 1;//《4》
        if (right < size &&
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0) //《5》
            c = queue[child = right];
        if (key.compareTo((E) c) <= 0)//《6》
            break;
        queue[k] = c;//《7》
        k = child;
    }
    queue[k] = key;//《8》
}

《1》无符号右移1位,取size的一半。 《2》得到二叉堆的左子节点下标。 《3》获取左子节点元素。 《4》右子节点下标。 《5》右子节点下标小于队列元素总数,并且左子节点元素比右子节点元素大时,把右子节点元素赋值给c,把右子节点下标赋值给child。 《6》需要交换的元素key小于或等于子节点元素c,则退出循环。 《7》把子节点c设置到queue下标为k的位置,并把child赋值给k,然后重复《1》-《6》步骤。 《8》找到key合适的位置并设置该元素。

总结

PriorityQueue使用二叉堆数据结构保证了队列头部元素永远是最小的,在添加和删除的过程元素移动次数比插叙排序插入少。队列元素是使用数组queue保存,在多线程的情况对数组queue并发操作存在安全问题。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-05-13 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Queue接口
  • Queue常用的实现类
  • PriorityQueue
    • PriorityQueue结构
      • PriorityQueue示例
        • PriorityQueue添加元素解析
          • java.util.PriorityQueue#offer
          • java.util.PriorityQueue#grow
          • java.util.PriorityQueue#siftUp
          • java.util.PriorityQueue#siftUpComparable
        • PriorityQueue删除元素解析
          • java.util.PriorityQueue#poll
          • java.util.PriorityQueue#siftDown
          • java.util.PriorityQueue#siftDownComparable
      • 总结
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档