景德镇陶瓷学院招生网:Queue-PriorityQueue源码剖析

admin 4个月前 (06-06) 科技 43 1

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并发操作存在安全问题

,

阳光在线手机版下载

阳光在线(原诚信在线官网)现已开放阳光在线手机版、阳光在线电脑客户端下载。阳光在线娱乐游戏公平、公开、公正,用实力赢取信誉。

Sunbet声明:该文看法仅代表作者自己,与本平台无关。转载请注明:景德镇陶瓷学院招生网:Queue-PriorityQueue源码剖析

网友评论

  • (*)

最新评论

  • 云博代理开户 2020-06-06 00:01:15 回复

    欧博网址www.ludiealliedinstitute.com欢迎进入欧博网址(Allbet Gaming),欧博网址开放会员注册、代理开户、电脑客户端下载、苹果安卓下载等业务。我词穷了,反正很好

    1

标签列表

    文章归档

      站点信息

      • 文章总数:664
      • 页面总数:0
      • 分类总数:8
      • 标签总数:1145
      • 评论总数:250
      • 浏览总数:13424