方圆

jcf-privorityQueue

2019-09-22

基于优先堆实现的无限的优先队列。队列里的元素根据它们自然的顺序或者构造函数传入的Comparator排序。PriorityQueue不允许null元素,依赖于自然顺序的优先队列也不允许无法比较的对象。

  • 基于最小堆:队列的头是符合指定顺序的最小的元素,如果多个元素都是最小值,头是他们其中一个。
  • 优先队列是无限的,但是有一个内部容量来控制队列上用来存储元素的数组的大小。它总是至少比size大,加入元素时自动增长。
  • 非线程安全:多线程操作,使用java.util.concurrent.PriorityBlockingQueue代替。

    Important variables

    1
    2
    3
    4
    5
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
    transient Object[] queue;
    private int size = 0;
    // null表示使用自然顺序
    private final Comparator<? super E> comparator;
    image.png
    image.png
    PriorityQueue 使用数组来存储二叉堆,如图所示数组存储二叉树有如下性质:
  • L=2*P+1
  • R=2*P+2
  • P=(L-1)/2=(R-2)/2=int((R-2)/2)=(Node-1)/2
    得到以下性质之后,后面代码中都用到。

Main Methods

  • grow()

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // 如果<64,翻倍;否则增加50%;
    int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) :(oldCapacity >> 1));
    // 检查是否超过最大SIZE:Integer.MAX_VALUE - 8
    if (newCapacity - MAX_ARRAY_SIZE > 0)
    // 允许再扩大到 Integer.MAX_VALUE
    newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
    }
  • siftUpUsingComparator()
    在队列末尾加入元素,不断地同父节点进行比较,如果违反父节点小于任意子节点的规则就和父节点交换,直到满足就停止。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
    // 和父节点比较
    int parent = (k - 1) >>> 1;
    Object e = queue[parent];
    // x大于等于父节点,停止
    if (comparator.compare(x, (E) e) >= 0)
    break;
    // 将父节点放下来
    queue[k] = e;
    // 从父节点的位置继续网上搜索
    k = parent;
    }
    queue[k] = x;
    }

    shiftUp.png

  • shifrDownUsingComparator()
    从某个位置移除原有元素后,为了收缩空间,将队列尾部的元素放到移除的位置。然后一直同子节点比较,如果违背父节点小于任意子节点的规则,就和子节点进行交换,直到满足就停止。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    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 = queue[child = right];
    // 如果小于等于较小的子节点就停止
    if (comparator.compare(x, (E) c) <= 0)
    break;
    // 将子节点放到父亲的位置
    queue[k] = c;
    k = child;
    }
    queue[k] = x;
    }

    shiftDown.png

  • add()/offer()
    两者基本相同,前者调用后者实现。加入元素之前确认空间,然后调用shiftUp 也就是 siftUpUsingComparator 实现元素插入并保持优先队列的特性。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    public boolean offer(E e) {
    int i = size;
    if (i >= queue.length)
    grow(i + 1);
    size = i + 1;
    if (i == 0)
    queue[0] = e;
    else
    // 维持堆的特性
    siftUp(i, e);
    return true;
    }
  • peak()

    1
    2
    3
    public E peek() {
    return (size == 0) ? null : (E) queue[0];
    }

    获取但不删除,由于再加入或者删除元素时就进行调整以维护优先队列特性,因此堆顶元素就是优先级最高的。

  • remove()/pool()
    获取并删除,remove(Object) 表示删除队列中与equal(o) 的对象, removeEq(Object o) 表示删除队列中与==o(同一个对象,更严格)的对象,不过两者在定位到对象后最终都通过 removeAt(i)来移除并保持队列特性;

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    private E removeAt(int i) {
    int s = --size;
    if (s == i) // 移除最后一个元素
    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;
    }

    pool() 是移除堆顶元素,移除之后的恢复相对简单:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
       public E poll() {
    if (size == 0)
    return null;
    int s = --size;
    modCount++;
    // 堆顶元素
    E result = (E) queue[0];
    // 最后一个元素,收缩空间
    E x = (E) queue[s];
    queue[s] = null;
    // 将最后一个元素从堆顶往下找合适的位置
    if (s != 0)
    siftDown(0, x);
    return result;
    }

Summary

  • PriorityQueuepeek()element操作是常数时间,add()offer(), 无参数的remove()以及poll()方法的时间复杂度都是*log(N)*。
  • 后两张图片来自网上,侵权请联系删除。
Tags: jcf
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章