队列之PriorityQueue

PriorityQueue用来作为平衡二叉堆操作。PriorityQueue是个有序的队列，通过comparator进行排序。如果没有指定比较器，就按自然排序，比如数字就是按升序排序，最小的数在堆顶queue[0]。PriorityQueue的默认初始容量是DEFAULT_INITIAL_CAPACITY = 11。

内部结构是一个对象数组 Object[] queue 。

构造函数：

1.

public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}

2.

public PriorityQueue(int initialCapacity) {
    this(initialCapacity, null);
}

3.

public PriorityQueue(Comparator<? super E> comparator) {
    this(DEFAULT_INITIAL_CAPACITY, comparator);
}

4.

public PriorityQueue(int initialCapacity,
                     Comparator<? super E> comparator) {
    // Note: This restriction of at least one is not actually needed,
    // but continues for 1.5 compatibility
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
}

5.

@SuppressWarnings("unchecked")
public PriorityQueue(Collection<? extends E> c) {
    if (c instanceof SortedSet<?>) {
        SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
        this.comparator = (Comparator<? super E>) ss.comparator();
        initElementsFromCollection(ss);
    }
    else if (c instanceof PriorityQueue<?>) {
        PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
        this.comparator = (Comparator<? super E>) pq.comparator();
        initFromPriorityQueue(pq);
    }
    else {
        this.comparator = null;
        initFromCollection(c);
    }
}

数组扩容：如果数组长度小于64，则增长原来数组的长度 + 2，  否则增长数组长度的1/2。

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);
}

常用APIs:

1. add(E e): boolean , 等同于offer(E e). 

public boolean offer(E e) {
    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] = e;
    else
        siftUp(i, e);
    return true;
}

2. peek() : E， 返回第一个元素的值。

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

3. remove(Object o): boolean, 移除一个元素。

4. poll(): E， 获取第一个元素，并删除该元素。

队列之PriorityQueue

原文：https://www.cnblogs.com/billyqiu/p/14184717.html