（7）PriorityQueue总结

72 阅读 0 评论 48 点赞

我是靠谱客的博主爱听歌凉面，最近开发中收集的这篇文章主要介绍（7）PriorityQueue总结，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.概念

如果我们给每个元素都分配一个数字来标记其优先级，不妨设较小的数字具有较高的优先级，这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样，我们就引入了优先级队列这种数据结构。优先级队列（priority queue）是0个或多个元素的集合，每个元素都有一个优先权，对优先级队列执行的操作有（1）查找（2）插入一个新元素（3）删除一般情况下，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。对于优先权相同的元素，可按先进先出次序处理或按任意优先权进行。

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

2.构造方法

无参：默认大小为11

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

有参：指定大小

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

有参：

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

3.grow方法扩容

1.5倍方式扩容

    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 >>