526互联

20230327 java.util.PriorityQueue

发布时间 2023-06-20 11:27:36作者: 流星<。)#)))≦

概念

  • public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable
  • 基于优先级堆的无界优先级队列
  • 基于自然排序或指定的比较器
  • 不允许 null
  • 队列的头部是相对于指定排序的最小元素
  • 如果多个元素并列最小值，头部是这些元素之一，头部可能会随操作变更
  • 先级队列是无界的，但有一个内部容量，管理用于存储队列中元素的数组的大小。它总是至少和队列大小一样大。当元素被添加到优先级队列时，其容量会自动增长
  • 线程不安全，存在并发修改异常

使用说明

  • 如果传入构造器的是 SortedSet 或 PriorityQueue ，新的 PriorityQueue 对象会使用其中的比较器
  • 使用迭代器遍历 PriorityQueue 时，注意并不是全局有序的，堆是数组表示的完全二叉树，这个二叉树从根节点都叶子节点的一支是有序的，但是兄弟节点直接并不是有序的，而迭代器是按照数组顺序迭代的
  • 不支持随机访问（以下标访问）
/**
    * 打印 PriorityQueue 所有值
    * 按照索引倒序导引
    * 打印内容：所在索引，当前索引上的值，包括自身在内的从叶子节点到根的所有节点值
    *
    * @param priorityQueue
    */
public static <T> void printPriorityQueue(PriorityQueue<T> priorityQueue) {
    Object[] queue = (Object[]) ReflectUtil.getFieldValue(priorityQueue, "queue");

    List<T> printList = ListUtil.toList();
    for (int k = priorityQueue.size() - 1; k >= 0; k--) {
        printList.clear();

        T val = (T) queue[k];
        printList.add(val);

        int n = k;
        while (n > 0) {
            int parent = n >>> 1;
            T e = (T) queue[parent];
            printList.add(e);
            n = parent;
        }

        Console.log(k, val, printList);
    }
}

源码理解

添加方法（add, offer）

  • add 方法直接调用 offer 方法，因为是无界队列，所以不会抛出异常
  • offer 方法调用 siftUp 方法（筛上），对新增加元素及其向上的所有父元素进行插入排序，保持堆性质

删除方法（remove, poll）

  • remove 方法有重载
    • 实现 Queue 接口的无参方法调用 poll 方法，且遵循规范，在队列为空时抛出异常
    • 实现 Collection 接口的一个参数的方法不会抛出异常，而是返回 false
  • poll 方法在队列为空时返回 false
  • poll 方法调用 siftDown 方法（筛下）

检查方法（element, peek）

  • element 方法会在队列为空时抛出异常，peek 方法返回空

扩容方法（grow）

  • 默认大小 11
  • 扩容策略：
    • 扩容时机：新增元素后，queue数组大于等于size
    • 新容量等于
      • 小于 64 ：old*2+2
      • 大于等于64 ：old*1.5
int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1));

堆操作（heapify, siftDown, siftUp）

siftUp


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


/**
 * 在位置 k 处插入项 x，通过将 x 提升到树上直到它大于或等于其父项，或者是根来保持堆不变性。
 * k – 要填充的位置 
 * x – 要插入的项目
 */
private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    // 从下向上遍历树，找到待插入的位置k
    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;
}

理解：siftUp 方法是从k索引开始，沿着每一层向上查找，直到找到一层中小于x的位置，把x替换到这一层的最小值节点上

siftDown

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

/**
 * 在位置 k 处插入项目 x，通过将 x 重复降级到树下直到它小于或等于其子项或者是叶子来保持堆不变性。
 * 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;
}

理解：siftDown 方法是从k索引开始，沿着每一层最小值向下查找，直到找到一层中最小值大于x的位置，把x替换到这一层的最小值节点上

heapify

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

/**
 * 在整个树中建立堆，在调用之前不假设元素的顺序。
 */
private void heapify() {
    // (size >>> 1) - 1 是拥有子节点的最后一个索引
    for (int i = (size >>> 1) - 1; i >= 0; i--)
        siftDown(i, (E) queue[i]);
}

理解：heapify 方法从拥有子节点的最后一个索引开始，向前遍历索引而不是树，策略是将每一个拥有子节点的值筛下，使最小值在父结点上

removeAt

removeAt 方法是唯一既用到 siftUp 也用到 siftDown 的方法

/**
 * 从队列中移除第 i 个元素。通常，此方法最多保留 i-1 个元素，包括在内，保持不变。在这些情况下，它返回 null。
 * 有时，为了保持堆不变性，它必须将列表中较晚的元素与较早于 i 的元素交换。在这些情况下，此方法返回先前位于列表末尾且现在位于 i 之前某个位置的元素。 
 * iterator.remove 使用这个事实来避免丢失遍历元素。
 */
private E removeAt(int i) {
    // assert i >= 0 && i < size;
    modCount++;
    int s = --size;
    if (s == i) // removed last element
        queue[i] = null;
    else {
        E moved = (E) queue[s];
        queue[s] = null;
        siftDown(i, moved);
        // 在数组的最后一个值小于i及其所有子树时，条件成立
        if (queue[i] == moved) {
            siftUp(i, moved);
            // 数组的最后一个值小于i的父节点时，条件成立
            if (queue[i] != moved)
                return moved;
        }
    }
    return null;
}

条件成立举例：

PriorityQueue<Integer> priorityQueue =
        new PriorityQueue<>(ListUtil.toList(0, 10, 2, 30, 40, 5, 6, 70, 80, 90, 100, 9));

// printPriorityQueue(priorityQueue);

System.out.println((Integer) ReflectUtil.invoke(priorityQueue, "removeAt", 3));     // 9

迭代器 java.util.PriorityQueue.Itr

类中存在一个成员变量，用来存放 removeAt 方法中删除索引后，返回不为 null 的元素

private ArrayDeque<E> forgetMeNot = null;

当使用迭代器的 remove 方法时，forgetMeNot 会记录 removeAt 方法返回不为 null 的元素，这会导致不符合预期的奇怪的迭代顺序

测试代码：

// PriorityQueue<Integer> priorityQueue =
//         new PriorityQueue<>(ListUtil.toList(0, 10, 2, 30, 40, 5, 6, 70, 80, 90, 100, 8, 9));

PriorityQueue<Integer> priorityQueue =
        new PriorityQueue<>(ListUtil.toList(0, 10, 2, 30, 40, 5, 6, 70, 80, 90, 100, 9, 8));


// printPriorityQueue(priorityQueue);

// System.out.println((Integer) ReflectUtil.invoke(priorityQueue, "removeAt", 3));

Iterator<Integer> iterator = priorityQueue.iterator();
while (iterator.hasNext()) {
    Integer next = iterator.next();
    Console.log(next);
    if (ObjUtil.equal(next, 30) || ObjUtil.equal(next, 40)) {
        iterator.remove();
    }
}

注意：尽量不要使用迭代器的 remove 方法