阅读java.util.PriorityQueue源码Note

原创
2020/04/24 15:06
阅读数 39

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
}
  1. iterator()方法返回的Iterator遍历时,顺序是随机的。如果想使用特定的顺序遍历,可以使用Arrays.sort(pq.toArray())
  2. 此队列是线程不安全的。相对线程安全的是: java.util.concurrent.PriorityBlockingQueue
  3. 时间复杂度:
方法 时间复杂度 备注
off O(log(n))  
poll O(log(n))  
remove O(log(n))  
add O(log(n))  
remove(Object) linear time 底层为使用了indexOf,遍历整个数组
contains(Object) linear time 底层为使用了indexOf,遍历整个数组
peek constant time 取数组的第一个元素 queue[0]
element constant time 取数组的第一个元素 queue[0]
size constant time 取数组的第一个元素 queue[0]

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();
    }
  1. 扩容策略,原始容量小于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);
    }
  1. toArray()方法,返回的数组是无序的。仅仅是简单地拷贝底层的数组
public Object[] toArray() {
        return Arrays.copyOf(queue, size);
    }

欢迎关注我的公众号:

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部