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

目录常用方法常⽤接⼝介绍常用方法常⽤接⼝介绍于PriorityQueue的使⽤要注意1. PriorityQueue中放置的元素必须要能够⽐较⼤⼩不能插⼊⽆法⽐较⼤⼩的对象否则会抛出 ClassCastException异常2. 不能插⼊null对象否则会抛出NullPointerException3. 没有容量限制可以插⼊任意多个元素其内部可以⾃动扩容4. 插⼊和删除元素的时间复杂度为5. PriorityQueue底层使⽤了堆数据结构6. PriorityQueue默认情况下是⼩堆---即每次获取到的元素都是最⼩的元素优先级队列的构造// 创建⼀个空的优先级队列底层默认容量是11 PriorityQueueInteger q1 new PriorityQueue(); // 创建⼀个空的优先级队列底层的容量为initialCapacity PriorityQueueInteger q2 new PriorityQueue(100); // // list中已经包含了三个元素 PriorityQueueInteger 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 ComparatorInteger{ Override public int compare(Integer o1, Integer o2) { return o2-o1; } } public class TestPriorityQueue { public static void main(String[] args) { PriorityQueueInteger 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()); } }