Queue

介绍优先级队列，是0个或多个元素的集合，集合中的每个元素都有一个权重值，每次出队都弹出优先级最大或最小的元素。 一般来说，优先级队列使用堆来实现。 源码分析主要属性 // 默认容量 private static final int DEFAULT_INITIAL_CAPACITY = 11; // 存储元素的地方 transient Object[] queue; // non-private to simplify nested class access // 元素个数 private int size = 0; // 比较器 private final Comparator<? super E> comparator; // 修改次数 transient int modCount = 0; // non-private to simplify nested class access默认容量是11；queue，元素存储在数组中，这跟我们之前说的堆一般使用数组来存储是一致的；comparator，比较器，在优先级队列中，也有两种方式比较元素，一种是元素的自然顺序，一种是通过比较器来比较；modCount，修改次数，有这个属性表示PriorityQueue也是fast-fail的；入队入队有两个方法，add(E e)和offer(E e)，两者是一致的，add(E e)也是调用的offer(E e)。 public boolean add(E e) { return offer(e);}public boolean offer(E e) { // 不支持null元素 if (e == null) throw new NullPointerException(); modCount++; // 取size int i = size; // 元素个数达到最大容量了，扩容 if (i >= queue.length) grow(i + 1); // 元素个数加1 size = i + 1; // 如果还没有元素 // 直接插入到数组第一个位置 // 这里跟我们之前讲堆不一样了 // java里面是从0开始的 // 我们说的堆是从1开始的 if (i == 0) queue[0] = e; else // 否则，插入元素到数组size的位置，也就是最后一个元素的下一位 // 注意这里的size不是数组大小，而是元素个数 // 然后，再做自下而上的堆化 siftUp(i, e); return true;}private void siftUp(int k, E x) { // 根据是否有比较器，使用不同的方法 if (comparator != null) siftUpUsingComparator(k, x); else siftUpComparable(k, x);}@SuppressWarnings("unchecked")private void siftUpComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>) x; while (k > 0) { // 找到父节点的位置 // 因为元素是从0开始的，所以减1之后再除以2 int parent = (k - 1) >>> 1; // 父节点的值 Object e = queue[parent]; // 比较插入的元素与父节点的值 // 如果比父节点大，则跳出循环 // 否则交换位置 if (key.compareTo((E) e) >= 0) break; // 与父节点交换位置 queue[k] = e; // 现在插入的元素位置移到了父节点的位置 // 继续与父节点再比较 k = parent; } // 最后找到应该插入的位置，放入元素 queue[k] = key;}入队不允许null元素；如果数组不够用了，先扩容；如果还没有元素，就插入下标0的位置；如果有元素了，就插入到最后一个元素往后的一个位置（实际并没有插入哈）；自下而上堆化，一直往上跟父节点比较；如果比父节点小，就与父节点交换位置，直到出现比父节点大为止；由此可见，PriorityQueue是一个小顶堆。扩容private void grow(int minCapacity) { // 旧容量 int oldCapacity = queue.length; // Double size if small; else grow by 50% // 旧容量小于64时，容量翻倍 // 旧容量大于等于64，容量只增加旧容量的一半 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) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;}当数组比较小（小于64）的时候每次扩容容量翻倍；当数组比较大的时候每次扩容只增加一半的容量；出队出队有两个方法，remove()和poll()，remove()也是调用的poll()，只是没有元素的时候抛出异常。 ...

PHP 的 SPL 库内置了 SplPriorityQueue优先级队列，是以Heap堆特性实现的，默认为MaxHeap模式，即priority越大越优先出队，同时可以通过重写compare方法来使用MinHeap（优先级越低越优先出队，场景貌似很少吧）。SplPriorityQueue堆特性这里需要注意并理解：SplPriorityQueue是以堆数据结构来实现的，当我们出队时会拿出堆顶的元素，此时堆的特性被破坏，堆会进行相应的调整至稳定态(MaxHeap or MinHeap)，即会将最后一个元素替换到堆顶，然后进行稳定态验证，不符合堆特性则继续调整，或者我们就得到了一个稳定态的堆，所以当优先级相同，出队顺序并不会按照入队顺序。源码示例：<?php$splPriorityQueue = new \SplPriorityQueue();// 设定返回数据的meta信息// \SplPriorityQueue::EXTR_DATA 默认 只返回数// \SplPriorityQueue::EXTR_PRIORITY 只返回优先级// \SplPriorityQueue::EXTR_BOTH 返回数据和优先级// $splPriorityQueue->setExtractFlags(\SplPriorityQueue::EXTR_DATA);$splPriorityQueue->insert(“task1”, 1);$splPriorityQueue->insert(“task2”, 1);$splPriorityQueue->insert(“task3”, 1);$splPriorityQueue->insert(“task4”, 1);$splPriorityQueue->insert(“task5”, 1);echo $splPriorityQueue->extract() . PHP_EOL;echo $splPriorityQueue->extract() . PHP_EOL;echo $splPriorityQueue->extract() . PHP_EOL;echo $splPriorityQueue->extract() . PHP_EOL;echo $splPriorityQueue->extract() . PHP_EOL;//执行结果task1task5task4task3task2可以看到，虽然 5 个任务的优先级相同，但队列并没有按照入队顺序返回数据，因为堆的特性使然：1、入队 task1, task2, task3, task4, task5，因为优先级相同，所以堆一直处于稳定态。2、出队，得 task1，堆先将结构调整为 task5, task2, task3, task4，已然达到了稳定态。3、出队，得 task5，堆先将结构调整为 task4, task2, task3，已然达到了稳定态。4、出队，得 task4，堆先将结构调整为 task3, task2，已然达到了稳定态。5、出队，得 task3，堆先将结构调整为 task2，已然达到了稳定态。4、出队，得 task2。Iterator, CountableSplPriorityQueue实现了 Iterator, Countable接口，所以我们可以foreach/count函数操作它，或者使用rewind,valid,current,next/count方法。注意，因为是堆实现，所以rewind方法是一个no-op没有什作用的操作，因为头指针始终指向堆顶，即current始终等于top，不像List只是游走指针，出队是会删除堆元素的，extract = current + next（current出队，从堆中删除）。<?php$splPriorityQueue = new \SplPriorityQueue();$splPriorityQueue->insert(“task1”, 1);$splPriorityQueue->insert(“task2”, 2);$splPriorityQueue->insert(“task3”, 1);$splPriorityQueue->insert(“task4”, 4);$splPriorityQueue->insert(“task5”, 5);echo “Countable： " . count($splPriorityQueue) . PHP_EOL;// 迭代的话会删除队列元素 current 指针始终指向 top 所以 rewind 没什么意义for ($splPriorityQueue->rewind(); $splPriorityQueue->valid();$splPriorityQueue->next()) { var_dump($splPriorityQueue->current()); var_dump($splPriorityQueue->count()); $splPriorityQueue->rewind();}var_dump(“is empty:” . $splPriorityQueue->isEmpty());Extract出队extract 出队更为友好，即始终返回优先级最高的元素，优先级相投时会以堆调整的特性返回数据。<?php$splPriorityQueue = new \SplPriorityQueue();// data priority$splPriorityQueue->insert(“task1”, 1);$splPriorityQueue->insert(“task2”, 2);$splPriorityQueue->insert(“task3”, 1);$splPriorityQueue->insert(“task4”, 4);$splPriorityQueue->insert(“task5”, 5);echo “Countable： " . count($splPriorityQueue) . PHP_EOL;while (! $splPriorityQueue->isEmpty()) { var_dump($splPriorityQueue->extract()); echo $splPriorityQueue->count() . PHP_EOL;}自定义优先级处理方式重写compare方法定义自己的优先级处理机制。<?phpclass CustomedSplPriorityQueue extends SplPriorityQueue{ public function compare($priority1, $priority2): int { // return $priority1 - $priority2;//高优先级优先 return $priority2 - $priority1;//低优先级优先 }}$splPriorityQueue = new \CustomedSplPriorityQueue();$splPriorityQueue->setExtractFlags(SplPriorityQueue::EXTR_BOTH);$splPriorityQueue->insert(“task1”, 1);$splPriorityQueue->insert(“task2”, 2);$splPriorityQueue->insert(“task3”, 1);$splPriorityQueue->insert(“task4”, 4);$splPriorityQueue->insert(“task5”, 5); echo “Countable： " . count($splPriorityQueue) . PHP_EOL;while (!$splPriorityQueue->isEmpty()) { var_dump($splPriorityQueue->extract());} ...