目录

常用方法

常⽤接⼝介绍

常用方法

常⽤接⼝介绍

于PriorityQueue的使⽤要注意：

1. PriorityQueue中放置的元素必须要能够⽐较⼤⼩，不能插⼊⽆法⽐较⼤⼩的对象，否则会抛出 ClassCastException异常

2. 不能插⼊null对象，否则会抛出NullPointerException

3. 没有容量限制，可以插⼊任意多个元素，其内部可以⾃动扩容

4. 插⼊和删除元素的时间复杂度为

5. PriorityQueue底层使⽤了堆数据结构

6. PriorityQueue默认情况下是⼩堆---即每次获取到的元素都是最⼩的元素

优先级队列的构造

// 
创建⼀个空的优先级队列，底层默认容量是11 
PriorityQueue<Integer> q1 = new PriorityQueue<>();
// 
创建⼀个空的优先级队列，底层的容量为initialCapacity 
PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
//
// list中已经包含了三个元素
PriorityQueue<Integer> q3 = new PriorityQueue<>(list);

三种构造方法的底层调用：

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

//this调用
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;
    }

插入元素的底层调用：

注意offer调用，siftUp调用，siftUpComparable调用

q1.offer(10);
//
public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        siftUp(i, e);
        size = i + 1;
        return true;
    }
//
siftUp的底层调用
private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x, queue, comparator);
        else
            siftUpComparable(k, x, queue);
    }
//
siftUpComparable的底层调用
private static <T> void siftUpComparable(int k, T x, Object[] es) {
//强转至<>中的类型
        Comparable<? super T> key = (Comparable<? super T>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = es[parent];
            if (key.compareTo((T) e) >= 0)
                break;
            es[k] = e;
            k = parent;
        }
        es[k] = key;
    }

注意：默认情况下，PriorityQueue队列是⼩堆，如果需要⼤堆需要⽤⼾提供⽐较器

// 
⽤⼾⾃⼰定义的⽐较器：直接实现Comparator接⼝，然后重写该接⼝中的
compare⽅法即可
//
class IntCmp implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
}
public class TestPriorityQueue {
public static void main(String[] args) {
PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());
p.offer(4);
p.offer(3);
p.offer(2);
p.offer(1);
p.offer(5);
System.out.println(p.peek());
}
}