Java-PriorityQueue

PriorityQueue

用途

大顶堆、小顶堆

方法

创建

PriorityQueue<Integer> numbers0 = new PriorityQueue<>(); // 小根堆(顶端元素为最小)

PriorityQueue<Integer> numbers1 = new PriorityQueue<>((a,b)->b-a); // 大根堆(顶端元素为最大)

// 指定数量
PriorityQueue<Integer> numbers2 = new PriorityQueue<>(10); // 指定容量可以避免执行扩容操作,加快速度

// 使用Comparator
PriorityQueue<Integer> numbers3 = new PriorityQueue<Integer>(10, new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1; // >=0即表示不用交换
            }
        }); // 大根堆(顶端元素为最大)

// 通过Collection作为参数创建
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(2,5,3));
PriorityQueue<Integer> numbers4 = new PriorityQueue<Integer>(arr);

入队

add(),offer()两者均为入队方法，仅在处理队列已满的情况时有所不同

PriorityQueue<Integer> numbers = new PriorityQueue<>();

numbers.add(4); // 队列已满时引发异常
numbers.add(3);
System.out.println("PriorityQueue: " + numbers);
// [3, 4]

numbers.offer(1); // 队列已满时返回false
System.out.println("PriorityQueue: " + numbers);
// [1, 4, 3]

出队

remove(),poll()在处理队列为空时不一样：remove()抛出异常，poll()返回null

numbers.remove();

numbers.poll(); // 推荐这种方法

访问

peek():队列为空时返回null

element():队列为空时抛出异常

numbers.peek();

numbers.element();

清空

clear()

判空

isEmpty()

访问元素个数

size()

自动扩容机制

源码如下:

/**
 * Increases the capacity of the array.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = ArraysSupport.newLength(oldCapacity,
            minCapacity - oldCapacity, /* minimum growth */
            oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1
                                       /* preferred growth */);
    queue = Arrays.copyOf(queue, newCapacity);
}

旧容量在64以下增加2,否则乘以2