Java 数据结构 优先级队列（堆）

目录

常用方法

常⽤接⼝介绍

常用方法

常⽤接⼝介绍

于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()); } }