PriorityQueue优先队列

2019-01-30 16:39:10


优先队列,继承AbstractQueue类,内部用堆实现。所以如果不懂堆的话,就不用往下看了。

一. Fields

  1. // 默认容量
  2. private static final int DEFAULT_INITIAL_CAPACITY = 11;
  3. // 存放元素的数组
  4. transient Object[] queue;
  5. // 元素个数
  6. int size;
  7. // 用于比较元素的比较器
  8. private final Comparator<? super E> comparator;
  9. // 防止并发修改
  10. transient int modCount;

二. Constructors

前三个构造器最终都是调用PriorityQueue(int initialCapacity, Comparator<? super E> comparator)这个构造器来指定容量与比较器,容量如果没指定则默认为11,比较器没指定则为null,此时就需要存放的对象自身是可比较的,否则在add时会类型转换异常。

  1. public PriorityQueue() {
  2. this(DEFAULT_INITIAL_CAPACITY, null);
  3. }
  4. public PriorityQueue(int initialCapacity) {
  5. this(initialCapacity, null);
  6. }
  7. public PriorityQueue(Comparator<? super E> comparator) {
  8. this(DEFAULT_INITIAL_CAPACITY, comparator);
  9. }
  10. public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
  11. if (initialCapacity < 1)
  12. throw new IllegalArgumentException();
  13. this.queue = new Object[initialCapacity];
  14. this.comparator = comparator;
  15. }

还有由集合构造优先队列的构造器,第一个相当于将后两个整合了一下

  1. public PriorityQueue(Collection<? extends E> c) {
  2. // 由SortedSet或优先队列构造优先队列,比较器可以直接拿来用
  3. // 而且它们的toArray()方法返回的数组可以保证满足堆的要求(一个有序,另一个就是直接把堆的数组复制过来)
  4. if (c instanceof SortedSet<?>) {
  5. SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
  6. this.comparator = (Comparator<? super E>) ss.comparator();
  7. initElementsFromCollection(ss);
  8. }
  9. else if (c instanceof PriorityQueue<?>) {
  10. PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
  11. this.comparator = (Comparator<? super E>) pq.comparator();
  12. initFromPriorityQueue(pq);
  13. }
  14. else {
  15. this.comparator = null;
  16. initFromCollection(c);
  17. }
  18. }
  19. public PriorityQueue(PriorityQueue<? extends E> c) {
  20. this.comparator = (Comparator<? super E>) c.comparator();
  21. initFromPriorityQueue(c);
  22. }
  23. public PriorityQueue(SortedSet<? extends E> c) {
  24. this.comparator = (Comparator<? super E>) c.comparator();
  25. initElementsFromCollection(c);
  26. }
  27. private void initElementsFromCollection(Collection<? extends E> c) {
  28. Object[] es = c.toArray();
  29. int len = es.length;
  30. // 确保数组类型是Object[]
  31. if (es.getClass() != Object[].class)
  32. es = Arrays.copyOf(es, len, Object[].class);
  33. // 如果比较器为null,说明元素自身可比较,则不存在元素为null的情况
  34. // len == 1 额。。没搞明白
  35. if (len == 1 || this.comparator != null)
  36. for (Object e : es)
  37. if (e == null)
  38. throw new NullPointerException();
  39. this.queue = ensureNonEmpty(es);
  40. this.size = len;
  41. }
  42. private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
  43. if (c.getClass() == PriorityQueue.class) {
  44. this.queue = ensureNonEmpty(c.toArray());
  45. this.size = c.size();
  46. } else {
  47. initFromCollection(c);
  48. }
  49. }
  50. private void initFromCollection(Collection<? extends E> c) {
  51. initElementsFromCollection(c);
  52. heapify();
  53. }
  54. // 把一个无序的数组调整成堆
  55. private void heapify() {
  56. final Object[] es = queue;
  57. // i 是数组中最后一个非叶子节点,即树中倒数第二层中最右边的那个
  58. // 从这个下标开始遍历,每次向下调整
  59. int n = size, i = (n >>> 1) - 1;
  60. final Comparator<? super E> cmp;
  61. if ((cmp = comparator) == null)
  62. for (; i >= 0; i--)
  63. siftDownComparable(i, (E) es[i], es, n);
  64. else
  65. for (; i >= 0; i--)
  66. siftDownUsingComparator(i, (E) es[i], es, n, cmp);
  67. }

三. Methods

  1. addoffer向队列中添加元素,如果元素为null,抛空指针异常。如果底层数组满了,需要先扩容。

    1. public boolean add(E e) {
    2. return offer(e);
    3. }
    4. public boolean offer(E e) {
    5. if (e == null)
    6. throw new NullPointerException();
    7. modCount++;
    8. int i = size;
    9. // 需要扩容
    10. if (i >= queue.length)
    11. grow(i + 1);
    12. // 调整节点,将e插入队列中合适的位置
    13. siftUp(i, e);
    14. size = i + 1;
    15. return true;
    16. }
    17. // 扩容 minCapacity为需要的最小长度
    18. private void grow(int minCapacity) {
    19. int oldCapacity = queue.length;
    20. // 如果旧容量小于64,扩为原来的2倍加2,否则扩为原来的1.5倍
    21. int newCapacity = oldCapacity + ((oldCapacity < 64) ?
    22. (oldCapacity + 2) :
    23. (oldCapacity >> 1));
    24. // 如果新容量大于MAX_ARRAY_SIZE
    25. // 如果所需最小容量小于0,则溢出,抛异常
    26. // 如果所需最小容量大于MAX_ARRAY_SIZE直接扩为Integer.MAX_VALUE
    27. // 否则扩为MAX_ARRAY_SIZE
    28. if (newCapacity - MAX_ARRAY_SIZE > 0) // MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
    29. newCapacity = hugeCapacity(minCapacity);
    30. // 拷贝到新数组
    31. queue = Arrays.copyOf(queue, newCapacity);
    32. }
    33. private static int hugeCapacity(int minCapacity) {
    34. if (minCapacity < 0) // overflow
    35. throw new OutOfMemoryError();
    36. return (minCapacity > MAX_ARRAY_SIZE) ?
    37. Integer.MAX_VALUE :
    38. MAX_ARRAY_SIZE;
    39. }
    40. // 调整元素位置
    41. // 先将插入元素放在数组尾部,然后与它的父节点比较,如果它小于父节点则与父节点交换位置
    42. // 不断重复与父节点比较,知道插入它大于等于父节点
    43. private void siftUp(int k, E x) {
    44. // 如果构造器中传入比较器,用这个比较器比较
    45. if (comparator != null)
    46. siftUpUsingComparator(k, x, queue, comparator);
    47. else
    48. // 否则按照元素自身排序,对象必须是可比较的
    49. siftUpComparable(k, x, queue);
    50. }
    51. // 没有提供比较器,元素自身可比较
    52. private static <T> void siftUpComparable(int k, T x, Object[] es) {
    53. Comparable<? super T> key = (Comparable<? super T>) x;
    54. while (k > 0) {
    55. // 父节点下标
    56. int parent = (k - 1) >>> 1;
    57. Object e = es[parent];
    58. // 要插入元素和父节点元素比较
    59. if (key.compareTo((T) e) >= 0)
    60. // 如果key 大于等于父元素停止比较
    61. break;
    62. // 如果父元素大于等于插入元素,将父元素下移
    63. es[k] = e;
    64. k = parent;
    65. }
    66. // 找到key的位置
    67. es[k] = key;
    68. }
    69. // 使用提供的比较器插入元素
    70. private static <T> void siftUpUsingComparator(
    71. int k, T x, Object[] es, Comparator<? super T> cmp) {
    72. while (k > 0) {
    73. int parent = (k - 1) >>> 1;
    74. Object e = es[parent];
    75. if (cmp.compare(x, (T) e) >= 0)
    76. break;
    77. es[k] = e;
    78. k = parent;
    79. }
    80. es[k] = x;
    81. }
  2. peek,返回堆顶元素
    1. public E peek() {
    2. return (E) queue[0];
    3. }
  3. remove,从队列中移除元素

    1. public boolean remove(Object o) {
    2. // 遍历数组查找o的下标
    3. int i = indexOf(o);
    4. if (i == -1)
    5. return false;
    6. else {
    7. // 如果找到,移除
    8. removeAt(i);
    9. return true;
    10. }
    11. }
    12. E removeAt(int i) {
    13. // assert i >= 0 && i < size;
    14. final Object[] es = queue;
    15. modCount++;
    16. int s = --size;
    17. // 如果移除的元素是最后一个元素,直接置为null
    18. if (s == i) // removed last element
    19. es[i] = null;
    20. else {
    21. E moved = (E) es[s];
    22. es[s] = null;
    23. siftDown(i, moved);
    24. // if 成立说明 i 是叶子节点,即树最下面的那层
    25. // 是直接将数组最后一个元素放到 i 处,无法保证es[i]大于等于其父节点
    26. // 所以需要向上调整
    27. if (es[i] == moved) {
    28. siftUp(i, moved);
    29. // 如果调整了,即有元素发生交换,返回moved
    30. if (es[i] != moved)
    31. return moved;
    32. }
    33. }
    34. return null;
    35. }
    36. // 从下标k开始到数组结尾,对于树是从上往下调整
    37. // 先将数组最后一个元素放在下标k处,然后与它的左右子节点中最小的比较
    38. // 如果它大于子节点中最小的那个,则与它交换位置,并继续与子节点比较
    39. // 直到它小于左右子节点,或它被移动到了叶子节点的位置
    40. private void siftDown(int k, E x) {
    41. if (comparator != null)
    42. siftDownUsingComparator(k, x, queue, size, comparator);
    43. else
    44. siftDownComparable(k, x, queue, size);
    45. }
    46. // 没有比较器
    47. private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {
    48. // assert n > 0;
    49. Comparable<? super T> key = (Comparable<? super T>)x;
    50. int half = n >>> 1; // loop while a non-leaf
    51. while (k < half) { // k == half - 1时,k是数组最后一个元素的父节点下标
    52. // k的左子节点的下标
    53. int child = (k << 1) + 1; // assume left child is least
    54. Object c = es[child];
    55. // k的右子节点下标
    56. int right = child + 1;
    57. // c = 左右节点中较小的那个
    58. if (right < n && ((Comparable<? super T>) c).compareTo((T) es[right]) > 0)
    59. c = es[child = right];
    60. // 如果key比左右节点都小,说明key可以放在这里
    61. if (key.compareTo((T) c) <= 0)
    62. break;
    63. // 小的节点往上移
    64. es[k] = c;
    65. k = child;
    66. }
    67. es[k] = key;
    68. }
    69. private static <T> void siftDownUsingComparator(
    70. int k, T x, Object[] es, int n, Comparator<? super T> cmp) {
    71. // assert n > 0;
    72. int half = n >>> 1;
    73. while (k < half) {
    74. int child = (k << 1) + 1;
    75. Object c = es[child];
    76. int right = child + 1;
    77. if (right < n && cmp.compare((T) c, (T) es[right]) > 0)
    78. c = es[child = right];
    79. if (cmp.compare(x, (T) c) <= 0)
    80. break;
    81. es[k] = c;
    82. k = child;
    83. }
    84. es[k] = x;
    85. }
  4. poll,移除堆顶元素
    1. public E poll() {
    2. final Object[] es;
    3. final E result;
    4. // 如果堆顶不为空
    5. if ((result = (E) ((es = queue)[0])) != null) {
    6. modCount++;
    7. final int n;
    8. final E x = (E) es[(n = --size)];
    9. es[n] = null;
    10. // 如果移除完了还有元素剩余,从堆顶开始向下调整
    11. if (n > 0) {
    12. final Comparator<? super E> cmp;
    13. if ((cmp = comparator) == null)
    14. siftDownComparable(0, x, es, n);
    15. else
    16. siftDownUsingComparator(0, x, es, n, cmp);
    17. }
    18. }
    19. return result;
    20. }
  5. iterator,返回一个迭代器,没有什么特定的顺序,只能保证第一个访问到的是最小的元素。

    1. public Iterator<E> iterator() {
    2. return new Itr();
    3. }
    4. private final class Itr implements Iterator<E> {
    5. // 下一次调用next方法返回的元素的下标
    6. private int cursor;
    7. // 上一次调用next方法返回的元素的下标(如果是从数组中返回的),初始为-1
    8. // 如果上一次访问的元素被移除或元素是从forgetMeNot中返回的,也设为-1
    9. private int lastRet = -1;
    10. // 在用迭代器remove时,有可能会将元素调整到lastRet前面
    11. // 此时如果继续只遍历数组,会将这个元素忘掉
    12. // 此时需要将这个元素放进这个队列,数组遍历完后,再调用next时从这个队列中取元素
    13. private ArrayDeque<E> forgetMeNot;
    14. // 如果上一次调用next方法返回的元素是从forgetMeNot中取出来的,则lastRetElt等于这个元素
    15. private E lastRetElt;
    16. // 防止并发修改
    17. private int expectedModCount = modCount;
    18. Itr() {} // prevent access constructor creation
    19. // 判断是否还有元素可以遍历,即数组没遍历完或forgetMeNot队列不为空
    20. public boolean hasNext() {
    21. return cursor < size ||
    22. (forgetMeNot != null && !forgetMeNot.isEmpty());
    23. }
    24. // 返回一个元素
    25. public E next() {
    26. // 判断是否有并发修改
    27. if (expectedModCount != modCount)
    28. throw new ConcurrentModificationException();
    29. // 如果数组没遍历完,直接返回数组中下一个元素
    30. if (cursor < size)
    31. return (E) queue[lastRet = cursor++];
    32. // 数组遍历完了,但是forgetMeNot中还有元素没访问到,从这里取出一个元素
    33. if (forgetMeNot != null) {
    34. lastRet = -1;
    35. lastRetElt = forgetMeNot.poll();
    36. if (lastRetElt != null)
    37. return lastRetElt;
    38. }
    39. throw new NoSuchElementException();
    40. }
    41. public void remove() {
    42. if (expectedModCount != modCount)
    43. throw new ConcurrentModificationException();
    44. // 如果上一个元素是从数组返回的,调用removeAt移除
    45. if (lastRet != -1) {
    46. E moved = PriorityQueue.this.removeAt(lastRet);
    47. lastRet = -1;
    48. // moved == null说明没有元素被调整到lastRet前面,直接cursor--
    49. if (moved == null)
    50. cursor--;
    51. else {
    52. // 如果有元素被移动到lastRet前面,则继续按照下标迭代会将它忽略掉
    53. // 因此要将它放入forgetMeNot队列中
    54. if (forgetMeNot == null)
    55. forgetMeNot = new ArrayDeque<>();
    56. forgetMeNot.add(moved);
    57. }
    58. } else if (lastRetElt != null) {
    59. // 上一个元素是从forgetMeNot返回的
    60. PriorityQueue.this.removeEq(lastRetElt);
    61. lastRetElt = null;
    62. } else {
    63. throw new IllegalStateException();
    64. }
    65. expectedModCount = modCount;
    66. }
    67. }
    68. // 找到o的下标后再调removeAt
    69. void removeEq(Object o) {
    70. final Object[] es = queue;
    71. for (int i = 0, n = size; i < n; i++) {
    72. if (o == es[i]) {
    73. removeAt(i);
    74. break;
    75. }
    76. }
    77. }

0
2
0

添加评论

正在回复:
取消
1
0
2
0