java优先队列PriorityQueue

文章目录

• • 前言
  • PriorityQueue
  • • 优先队列
    • java中优先队列的声明
    • 按优先级排序
    • 常见方法
    • • private void grow(int minCapacity)
      • public boolean offer(E e)
      • public E poll()
      • public int size()
      • public void clear()
      • public E peek()
      • public boolean isEmpty()
  • 总结

前言

今天复习算法时，发现优先队列有些忘记了，就去研究了下优先队列的源码，写个小笔记，加深下理解。

PriorityQueue 优先队列

我们知道队列是FIFO（先进先出）的，而优先队列的每一个元素都有一个对应的优先级，所以优先队列最前面的元素是优先级最高或者优先级元素最低的元素。

优先队列保留了队列的基本性质，优先队列其实可以看成堆，这样更加好理解。

java中优先队列的声明

在java中，是有已经封装好的优先队列供我们调用的，即PriorityQueue

PriorityQueue queue = new PriorityQueue();

这样声明的优先队列的值就默认为优先队列的优先级了。

优先队列插入和删除元素的时间复杂度为O(log2N)

当我们需要声明一个带初始容量的优先队列时，我们可以直接在声明的后面加上我们想要的容量，比如我们声明一个50的容量。

PriorityQueue queue = new PriorityQueue(50);

按优先级排序

在默认情况下，不传入Comparator对象的话，Java会默认按优先级从小到大排序，即一个小顶堆，就是按优先级从小到大的队列，队首是优先级最小的元素。

那假如我们想要一个队首是最大优先级的元素时，我们需要怎么设置呢

PriorityQueue queue = new PriorityQueue(new Comparator() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

常见方法 private void grow(int minCapacity)

这个方法可以增加优先队列的容量

private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        // Double size if small; else grow by 50%
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, 
                oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1
                                           );
        queue = Arrays.copyOf(queue, newCapacity);
    }

public boolean offer(E e)

插入一个元素e，如果e为空，会抛出NullPointerException，如果队列的容量满了，会自动扩容。插入成功返回true

public E poll()

弹出一个优先级最高或者最低（取决于你的设置），如果优先队列为空，返回null

public int size()

返回当前优先队列的个数

public void clear()

清空当前队列

public void clear() {
        modCount++;
        final Object[] es = queue;
        for (int i = 0, n = size; i < n; i++)
            es[i] = null;
        size = 0;
    }

public E peek()

获取队首元素

public E peek() {
        return (E) queue[0];
    }

public boolean isEmpty()

检查优先队列是否为空，空就返回true

总结

简单常见的一些方法，如果有什么问题，希望大佬指教。