PriorityQueue

Queue
PriorityQueue
- 1.PriorityQueue简介
- 2.基本属性
- 3.基本方法
- - （1）add(E e)和offer(E e)
  - （2）grow(int minCapacity)扩容
  - （3）siftUp(int k, E x) 上浮调整函数
  - （4）peek()
  - （5）remove(Object o)和poll()
  - （6）siftDown(int k, E x)

Queue

Queue是先入先出（FIFO）的一个队列数据结构，可以分为阻塞队列和非阻塞队列。

接口方法：

//插入元素。成功时返回true，如果失败则抛出异常
boolean add(E e);
//插入元素。成功时返回true，失败返回false
boolean offer(E e);
//检索并删除队列的头部，如果队列为空，则抛出异常
E remove();
//检索并删除队列的头部，如果队列为空，则返回null
E poll();
//检索但不删除队列的头部，如果队列为空，则抛出异常
E element();
//检索但不删除队列的头部，如果队列为空，则返回null
E peek();

安全的会进行容量检查的（add、remove、element）

不安全的不进行容量控制的（offer、delete、peek）

PriorityQueue

优先队列的作用是保证每次取出的元素都是队列中权值最小的。

Java中的PriorityQueue实现了Queue接口，不允许放入null元素，通过二叉小顶堆实现，可以用以可完全二叉树表示（具体说是通过完全二叉树实现的小顶堆）。

完全二叉树实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值）。

二叉堆可以使用数组来表示，父子节点下标关系如下：

PriorityQueue优先队列源码解析QueuePriorityQueue

1.PriorityQueue简介

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {

继承了AbstractQueue
实现了Serializable，可以实现序列化和反序列化

2.基本属性

//序列化的UID
private static final long serialVersionUID = -7720805057305804111L;
//默认初始容量为11
private static final int DEFAULT_INITIAL_CAPACITY = 11;
//存放数据的Object数组
transient Object[] queue; // non-private to simplify nested class access
//优先队列中的元素个数
private int size = 0;
//比较器，如果优先级队列使用元素的自然顺序，则为 null（默认是自然排序）。
private final Comparator<? super E> comparator;
//优先队列结构上的修改次数
transient int modCount = 0; // non-private to simplify nested class access

//创建一个具有默认初始容量 (11) 的PriorityQueue ，它根据元素的自然顺序对其元素进行排序。
public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
}

PriorityQueue使用数组存储数据，基于数组形式的小顶堆来做的。

PriorityQueue是在构造函数调用阶段就已经申请了底层数组。而有的容器类比如HashMap则是采用懒加载机制，在实际的使用的时候才会真正的去申请底层的数据空间。hashMap在实际指定的初始容量的情况下，会去申请一个2的n次方的数值大小的空间，而Queue在默认的没有指定初始容量的时候，就只申请了长度为11的数组。ArrayList集合在没有指定初始容量的时候，也是采用的类似懒加载的机制，指定一个长度为0的空数组，真正使用的时候才创建底层数组的空间。

3.基本方法

（1）add(E e)和offer(E e)

因为priority是无界队列，所以添加元素不会抛出illegalStateException异常，如果当前数组已满，则会直接扩容后插入。

public boolean add(E e) {
	//直接调用offer方法
    return offer(e);
}

public boolean offer(E e) {
		//前置检验，检查插入元素是否为null，不允许插入null
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        //检查数组容量，如果容量不够，直接进行扩容。
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
        	//如果当前队列为空，直接放到queue[0]
            queue[0] = e;
        else
        	//需要调整元素位置
            siftUp(i, e);
        return true;
    }

（2）grow(int minCapacity)扩容

如果当前容量小于64，则扩容当前容量+2，比如当前容量是15，则扩容后的容量为 15 + 15 + 2 = 32

如果当前容量大于等于64，则扩容当前容量的一半，比如当前容量是60 ，则扩容后的容量是 60 + 30 = 90

private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}
//由于queue是一个无界数组，当扩容到一定程度时就会超出整型的最大值或者内存溢出，所以做一个限制处理
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
 }

（3）siftUp(int k, E x) 上浮调整函数

该代码的实现其实是一个小顶堆的实现，即一个完全平衡二叉树。每次往里面添加节点的时候，先跟父节点比较大小，如果比父节点小，则需要跟父节点交换位置，然后继续跟当前的父节点比较，直到完成最小元素的位置转换。

private void siftUp(int k, E x) {
    if (comparator != null)
    	//非自然排序
        siftUpUsingComparator(k, x);
    else
    	//自然排序
        siftUpComparable(k, x);
}
//此方法中k就是插入元素的下标值，x是元素
private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
    	//通过节点个数找到父节点的位置
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        //将当前要插入的节点与父节点先进行比较
        //如果大于父节点，直接执行 queue[k] = x; 将该元素放到最底部
        if (comparator.compare(x, (E) e) >= 0)
        	//上浮过程，直到元素x大于父节点，说明小顶堆到达了平衡
            break;
        //如果小于父节点，继续向上比较，执行下一次循环
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
    //最终结果就是小的节点在最上面，大的节点在下面
}


private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
        	//通过节点个数找到父节点的位置
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
}

（4）peek()

//获取但不移除此队列的头，如果此队列为空，则返回null
public E peek() {
    return (size == 0) ? null : (E) queue[0];
}

（5）remove(Object o)和poll()

//获取并移除队列的头部，如果队列为空，则抛出异常
public boolean remove(Object o) {
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
        removeAt(i);
        return true;
    }
}
private E removeAt(int i) {
        // assert i >= 0 && i < size;
        modCount++;
        int s = --size;
        if (s == i) // removed last element
            queue[i] = null;
        else {
            E moved = (E) queue[s];
            queue[s] = null;
            siftDown(i, moved);
            if (queue[i] == moved) {
                siftUp(i, moved);
                if (queue[i] != moved)
                    return moved;
            }
        }
        return null;
}

//获取并移除此队列的头，如果队列为空，则返回null
public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    //取出队头元素
    E result = (E) queue[0];
    //保存队尾元素
    E x = (E) queue[s];
    //同时将队尾元素置为null
    queue[s] = null;
    //如果queue还有元素存在，调节二叉树中的元素位置
    if (s != 0)
        siftDown(0, x);
    return result;
}

（6）siftDown(int k, E x)

取k位置左边子节点c（如果右子节点存在并且小于左子节点，则值应该是右边的值），跟E比较，如果大于E，则queue[k] = E 完成，否则queue[k] = c ，k赋值为c的节点的位置，重复开始的比较，直到遍历了所有左边子节点。

简单来说，就是poll之后去除头节点，将尾节点放在合适的位置上，使之重新成为完全平衡二叉树。

private void siftDown(int k, E x) {
    if (comparator != null)
    	//非自然排序
        siftDownUsingComparator(k, x);
    else
    	//自然排序
        siftDownComparable(k, x);
}

private void siftDownUsingComparator(int k, E x) {
        int half = size >>> 1;
        while (k < half) {
        	//获取小根堆的左孩子节点下标
            int child = (k << 1) + 1;
            Object c = queue[child];
            //获取小根堆的右孩子节点下标
            int right = child + 1;
            if (right < size &&
                comparator.compare((E) c, (E) queue[right]) > 0)
                //找到左右孩子中较小的，记录到c，用child记录其下标
                c = queue[child = right];
             //利用下沉操作，直到平衡
            if (comparator.compare(x, (E) c) <= 0)
                break;
            queue[k] = c;
            //一直执行下沉操作
            k = child;
        }
        queue[k] = x;
}
private void siftDownComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>)x;
        int half = size >>> 1;        // loop while a non-leaf
        while (k < half) {
            int child = (k << 1) + 1; // assume left child is least
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
                c = queue[child = right];
            if (key.compareTo((E) c) <= 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = key;
}

（7）indexOf(Object o)

//获取元素o的下标值，时间复杂度为O（n）
private int indexOf(Object o) {
    if (o != null) {
        for (int i = 0; i < size; i++)
            if (o.equals(queue[i]))
                return i;
    }
    return -1;
}

（8）contains(Object o)

public boolean contains(Object o) {
	//判断元素是否存在，调用公共方法indexOf
    return indexOf(o) != -1;
}

PriorityQueue优先队列源码解析QueuePriorityQueue

PriorityQueue

Queue

PriorityQueue

1.PriorityQueue简介

2.基本属性

3.基本方法

（1）add(E e)和offer(E e)

（2）grow(int minCapacity)扩容

（3）siftUp(int k, E x) 上浮调整函数

（4）peek()

（5）remove(Object o)和poll()

（6）siftDown(int k, E x)

继续阅读

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的简单使用

neo4j之cypher使用文档

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

Effective Java 8:通用程序设计

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

Linux设备模型（中）之上层容器

scala (3) Function 和 Method

hdu7108哈希