Java 常用集合类 PriorityQueue

PriorityQueue 整体设计

PriorityQueue 继承自抽象父类 AbstractQueue 的优先级队列,使用小顶堆实现每次取出的元素都是队列中权值最小的。元素大小的判断可以通过传入的比较器计算,否则采用自然排序。不允许放入 null。

按照堆的特点可以把堆分为大顶堆小顶堆
大顶堆:每个结点的值都大于等于其左右孩子结点的值
小顶堆:每个结点的值都小于等于其左右孩子结点的值

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable { 
}

PriorityQueue 属性和构造函数

主要属性

// 默认初始容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;

// 表示为平衡二叉堆的优先级队列:queue[n]的两个子节点列是queue[2*n+1]和queue[2*(n+1)]
transient Object[] queue; 

// 队列元素数量
private int size = 0;

// 比较器,用于定义比较规则
private final Comparator<? super E> comparator;

构造函数

// 默认构造器
public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}

// 指定初始容量
public PriorityQueue(int initialCapacity) {
    this(initialCapacity, null);
}

// 对初始容量的要求 >= 1
public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {
      if (initialCapacity < 1)
          throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
      this.comparator = comparator;
}

// 对 SortedSet 和 PriorityQueue 特殊处理
public PriorityQueue(Collection<? extends E> c) {
    if (c instanceof SortedSet<?>) {
        SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
        this.comparator = (Comparator<? super E>) ss.comparator();
        initElementsFromCollection(ss);
    }
    else if (c instanceof PriorityQueue<?>) {
        PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
        this.comparator = (Comparator<? super E>) pq.comparator();
        initFromPriorityQueue(pq);
    }
    else {
        this.comparator = null;
        initFromCollection(c);
    }
}

使用 SortedSet 初始化,已经是排序数组,直接赋值

private void initElementsFromCollection(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if (a.getClass() != Object[].class)
            a = Arrays.copyOf(a, a.length, Object[].class);

    int len = a.length;
    // 不支持有 null 元素
    if (len == 1 || this.comparator != null)
            for (int i = 0; i < len; i++)
                    if (a[i] == null)
                            throw new NullPointerException();
      this.queue = a;
    this.size = a.length;
}

使用 PriorityQueue 初始化,直接赋值

private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
    if (c.getClass() == PriorityQueue.class) {
          this.queue = c.toArray();
        this.size = c.size();
    } else {
          initFromCollection(c);
    }
}

使用其他集合类初始化,调用 heapify() 调整顺序

private void initFromCollection(Collection<? extends E> c) {
    initElementsFromCollection(c);
    heapify();
}

添加元素

可以调用 add()offer() 添加元素

public boolean add(E e) {
    return offer(e);
}

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;
}

向上调整元素

不断地和 parent(queue[(k-1)/2])比较,如果小于 parent 进行互换

// k 当前位置,x 当前元素,向上调整
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) {
        // 找到 parent,如果小于 parent,进行换位
          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

如果 queue 数组已经占满,进行扩容,扩容后大小计算以 64 为分界线,并且如果 newCapacity 增加到 MAX_ARRAY_SIZE,调用 hugeCapacity() 计算的到。扩容是通过数组拷贝的方式。

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
      newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
          MAX_ARRAY_SIZE;
}

取出元素

peek() 方法返回堆顶元素,poll() 方法返回并移除堆顶元素

public E peek() {
      return (size == 0) ? null : (E) queue[0];
}

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;
}

向下调整元素

private void siftDown(int k, E x) {
    if (comparator != null)
          siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}
child默认为小的那个下标,记录小的对象为c;,就结束循环,调整完成,否则将c赋值为queue[k],k = child,继续向下调整。

private void siftDownUsingComparator(int k, E x) {
    // 最后一层非叶子节点层
    int half = size >>> 1;
    while (k < half) {
        // k的左子节点child,右子节点right
        int child = (k << 1) + 1;
        Object c = queue[child];
        int right = child + 1;
        // 如果右子节点存在,找到比较小的子节点,作为c取出,下标为child
        if (right < size &&
              comparator.compare((E) c, (E) queue[right]) > 0)
              c = queue[child = right];
        // 如果x大于c,进行交换,并进入下一层循环
        if (comparator.compare(x, (E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = x;
}

private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1;        // loop while a non-leaf
    while (k < half) {
        int child = (k << 1) + 1; // assume left child is least
        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;
}

删除元素

默认删除堆顶元素,如果删除指定元素先找到元素位置,然后移除

public E remove() {
    E x = poll();
    if (x != null)
      return x;
    else
      throw new NoSuchElementException();
}

// 先找到元素位置
public boolean remove(Object o) {
    int i = indexOf(o);
    if (i == -1)
          return false;
    else {
        removeAt(i);
          return true;
    }
}

// 如果移除的是叶子节点,直接置为 null
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;
}

heapify 方法

private void heapify() {
    // 从 queue[size/2-1] 位置开始执行 siftDown
    // 即最后一层非叶子节点开始调整位置
    for (int i = (size >>> 1) - 1; i >= 0; i--)
          siftDown(i, (E) queue[i]);
}

iterator 方法

优先级队列的迭代器

public Iterator<E> iterator() {
    return new Itr();
}

private final class Itr implements Iterator<E> {
    // next 元素的坐标
      private int cursor = 0;
    // 移除元素存入
    private ArrayDeque<E> forgetMeNot = null;

    // 最近一次获取的元素的坐标,如果元素已经被 remove 则为 -1
      private int lastRet = -1;
    // 最近一次从 forgetMeNot 出队列的元素
      private E lastRetElt = null;

    public boolean hasNext() {
          return cursor < size ||
              (forgetMeNot != null && !forgetMeNot.isEmpty());
    }

    // 先从 queue 中依次获取
    public E next() {
        if (cursor < size)
            return (E) queue[lastRet = cursor++];
        if (forgetMeNot != null) {
              lastRet = -1;
            // 从 forgetMeNot 队列中出队列
            lastRetElt = forgetMeNot.poll();
              if (lastRetElt != null)
                  return lastRetElt;
        }
        throw new NoSuchElementException();
    }

    public void remove() {
        if (lastRet != -1) {
            // 移除 lastRet
              E moved = PriorityQueue.this.removeAt(lastRet);
            lastRet = -1;
              if (moved == null)
                  cursor--;
            else {
                    if (forgetMeNot == null)
                          forgetMeNot = new ArrayDeque<>();
                // 放入 forgetMeNot 队列
                  forgetMeNot.add(moved);
            }
        } else if (lastRetElt != null) {
              PriorityQueue.this.removeEq(lastRetElt);
            lastRetElt = null;
        } else {
              throw new IllegalStateException();
        }
    }
}

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注