本文最后更新于:January 31, 2022 am
前言 优先队列是JAVA以堆排序为基础实现的数据结构,这种结构在删除或新增元素后,会自动进行重排,非常方便。本文分析优先队列中的常用方法源码来加强理解。
堆排序 所谓堆 ,是一种完全二叉树。如果这颗树的父节点值大于等于子节点值,则称为大顶堆。如果父节点值小于等于子节点,则成为小顶堆。
算法 1、将序列中的n个元素构造成堆
2、堆顶 与序列末尾元素交换,这样末尾元素就成了整个序列的最大(最小)值
3、对当前序列的前n-1个元素重复1和2
有关堆排序的详解可以参考这篇文章 。
源码解析 变量 private static final int DEFAULT_INITIAL_CAPACITY = 11 ;private int size = 0 ;private final Comparator<? super E> comparator;transient Object[] queue;transient int modCount = 0 ;
对offer()、poll()、remove()这3个方法及它们的关联方法进行分析,其他方法都很简单,直接看源码即可。
offer(E e)
方法增加元素 每次调用offer()方法时,队列已经是堆的状态的了,offer的元素先假定放在队尾,然后自下向上重构堆
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public boolean offer (E e) { if (e == null ) throw new NullPointerException(); modCount++; int i = size; if (i >= queue.length) grow(i + 1 ); size = i + 1 ; if (i == 0 ) queue[0 ] = e; else siftUp(i, e); return true ; }
siftUp(int k, E x)
自下向上 重构堆1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 private void siftUp (int k, E x) { if (comparator != null ) siftUpUsingComparator(k, x); else siftUpComparable(k, x); } private void siftUpComparable (int k, E x) { Comparable<? super E> key = (Comparable<? super E>) x; while (k > 0 ) { int parent = (k - 1 ) >>> 1 ; Object e = queue[parent]; if (key.compareTo((E) e) >= 0 ) break ; queue[k] = e; k = parent; } queue[k] = key; } private void siftUpUsingComparator (int k, E x) { while (k > 0 ) { int parent = (k - 1 ) >>> 1 ; Object e = queue[parent]; if (comparator.compare(x, (E) e) >= 0 ) break ; queue[k] = e; k = parent; } queue[k] = x; }
grow(int minCapacity)
扩容的方法1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 private void grow (int minCapacity) { int oldCapacity = queue.length; int newCapacity = oldCapacity + ((oldCapacity < 64 ) ? (oldCapacity + 2 ) : (oldCapacity >> 1 )); if (newCapacity - MAX_ARRAY_SIZE > 0 ) newCapacity = hugeCapacity(minCapacity); queue = Arrays.copyOf(queue, newCapacity); }private static int hugeCapacity (int minCapacity) { if (minCapacity < 0 ) throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
poll()
方法每次取出队首元素后,假定队尾元素放置队首,然后自上向下重构堆
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public E poll () { if (size == 0 ) return null ; int s = --size; modCount++; E result = (E) queue[0 ]; E x = (E) queue[s]; queue[s] = null ; if (s != 0 ) siftDown(0 , x); return result; }
siftDown(int k, E x)
自上向下 重构堆1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 private void siftDown (int k, E x) { if (comparator != null ) siftDownUsingComparator(k, x); else siftDownComparable(k, x); }private void siftDownComparable (int k, E x) { Comparable<? super E> key = (Comparable<? super E>)x; int half = size >>> 1 ; while (k < half) { int child = (k << 1 ) + 1 ; Object c = queue[child]; int right = child + 1 ; if (right < size && ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0 ) c = queue[child = right]; if (key.compareTo((E) c) <= 0 ) break ; queue[k] = c; k = child; } queue[k] = key; }private void siftDownUsingComparator (int k, E x) { int half = size >>> 1 ; while (k < half) { int child = (k << 1 ) + 1 ; Object c = queue[child]; int right = child + 1 ; if (right < size && comparator.compare((E) c, (E) queue[right]) > 0 ) c = queue[child = right]; if (comparator.compare(x, (E) c) <= 0 ) break ; queue[k] = c; k = child; } queue[k] = x; }
从上述代码中可以看出,调用poll()
之后,重构堆时,只是保证了堆顶元素最小,但是左右孩子结点的大小关系不一定,所以底层数组不一定是完全有序的。这本来也是堆结构的性质。我们用一段代码来验证。
1 2 3 4 5 6 7 8 9 PriorityQueue<Integer> queue=new PriorityQueue<>(); queue.add(1 ); queue.add(2 ); queue.add(3 ); queue.add(4 ); queue.add(5 ); System.out.println(Arrays.toString(queue.toArray())); queue.poll(); System.out.println(Arrays.toString(queue.toArray()));
remove(Object o)
方法删除指定元素
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public boolean remove (Object o) { int i = indexOf(o); if (i == -1 ) return false ; else { removeAt(i); return true ; } }private int indexOf (Object o) { if (o != null ) { for (int i = 0 ; i < size; i++) if (o.equals(queue[i])) return i; } return -1 ; }
removeAt(int i)
删除指定位置元素1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 private E removeAt (int i) { modCount++; int s = --size; if (s == i) queue[i] = null ; else { E moved = (E) queue[s]; queue[s] = null ; siftDown(i, moved); if (queue[i] == moved) { siftUp(i, moved); if (queue[i] != moved) return moved; } } return null ; }
参考文章 https://www.cnblogs.com/chengxiao/p/6129630.html