阅读java.util.PriorityQueue源码Note

java.util.PriorityQueue

Binary Heap:
https://www.cnblogs.com/gaochundong/p/binary_heap.html
https://en.wikipedia.org/wiki/Binary_heap
https://www.youtube.com/watch?v=g9YK6sftDi0

1. 不是完整的排序，仅关心父子节点的顺序，而不关心兄弟节点的顺序
2. 堆，最大堆 or 最小堆， 意即：根节点是最大的元素或者最小的元素
3. 借助于数组存储数据，从高层往下存储，从左到右存储。意即：第一个元素是根节点，后面紧跟其子节点；而后再紧跟两个子节点的四个子节点。
4. 堆是一个完全二叉树。如果堆中有 n 个节点，则最小高度为 Θ(lg n)
5. 调整堆时，从最后一个元素开始调整
6. 最大堆插入元素： 将元素先放入底层的叶子节点，依次比较其父节点，若比父节点大，则与父节点交换位置；而后继续比较。直至比其父节点小。类似于不停的向上冒泡。。POPO
7. 最大堆取出根节点后的重新排序：取最后一个叶子节点（最底层、从左到右），假设它为最大节点，因此放置于根节点，与左右子节点比较，若比子节点小，则与子节点交换位置，依次类推，直至比子节点大。 类似于不停的向下沉。。。DOWN

1. 无界，底层使用数组存储，有必要时会扩容
2. 排序规则：元素自行实现java.lang.Comparable 或者 创建队列时传入java.util.Comparator
3. 不允许插入null元素，不允许插入无法比较的元素
4. 第一个元素为最小的元素，可以多个元素都是least，则头部元素为其中一个
5. 底层为数组存储结构

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

    private static final int DEFAULT_INITIAL_CAPACITY = 11;

    /**
     * Priority queue represented as a balanced binary heap: the two
     * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
     * priority queue is ordered by comparator, or by the elements‘
     * natural ordering, if comparator is null: For each node n in the
     * heap and each descendant d of n, n <= d.  The element with the
     * lowest value is in queue[0], assuming the queue is nonempty.
     */
    transient Object[] queue; // non-private to simplify nested class access
}

6. iterator()方法返回的Iterator遍历时，顺序是随机的。如果想使用特定的顺序遍历，可以使用Arrays.sort(pq.toArray())
7. 此队列是线程不安全的。相对线程安全的是： java.util.concurrent.PriorityBlockingQueue
8. 时间复杂度：

indexOf

    private int indexOf(Object o) {
        if (o != null) {
            for (int i = 0; i < size; i++)
                if (o.equals(queue[i]))
                    return i;
        }
        return -1;
    }

peek

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

element 继承父类的方法实现

    public E element() {
        E x = peek();
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }

9. 扩容策略，原始容量小于64时，扩容至两倍+2；否则扩容50%

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

10. toArray()方法，返回的数组是无序的。仅仅是简单地拷贝底层的数组

public Object[] toArray() {
        return Arrays.copyOf(queue, size);
    }

欢迎关注我的公众号：

阅读java.util.PriorityQueue源码Note

原文：https://www.cnblogs.com/zzzzzzzh/p/12767425.html