小型手机网站建设哪家好,泰安网页,wordpress edc,wordpress里的页面布局概述
PriorityQueue#xff0c;优先级队列#xff0c;一种特殊的队列#xff0c;作用是能保证每次取出的元素都是队列中权值最小的#xff08;Java的优先队列每次取最小元素#xff0c;C的优先队列每次取最大元素#xff09;。元素大小的评判可以通过元素本身的自然顺序…概述
PriorityQueue优先级队列一种特殊的队列作用是能保证每次取出的元素都是队列中权值最小的Java的优先队列每次取最小元素C的优先队列每次取最大元素。元素大小的评判可以通过元素本身的自然顺序(Natural Ordering)也可通过构造时传入的比较器如Java中的ComparatorC的仿函数。
Java中PriorityQueue通过二叉小顶堆实现可用一棵完全二叉树表示。PriorityQueue实现Queue接口不允许放入null元素其通过堆实现具体说是通过完全二叉树(Complete Binary Tree)实现的小顶堆任意一个非叶子节点的权值都不大于其左右子节点的权值也就意味着可以通过数组来作为PriorityQueue的底层实现。
给每个元素按照层序遍历的方式进行编号父子节点的编号之间的关系
leftNo parentNo*21
rightNo parentNo*22
parentNo (nodeNo-1)/2通过上述三个公式可以轻易计算出某个节点的父节点以及子节点的下标。这也就是为什么可以直接用数组来存储堆的原因。
应用场景
常用于需要按优先级处理元素的场景
任务调度调度系统中的任务可能有不同的优先级。使用PriorityQueue可确保高优先级的任务先执行。JDK中的定时任务调度可能会使用类似的结构来管理不同的任务图算法许多图算法如Dijkstra需要频繁选择当前最小或最大权重的边或节点。PriorityQueue适合存储这些节点以快速获取最优解实时数据处理在一些流式处理框架中可能需要实时处理数据并保持数据的优先级。PriorityQueue可帮助维护这些数据的顺序MQ在某些消息中间件中可能会根据消息的优先级来处理消息。使用PriorityQueue可实现这一点确保高优先级的消息先被消费事件驱动架构在事件驱动系统中基于事件优先级PriorityQueue可方便地管理和调度这些事件合并多个有序序列在处理多个已排序的数据流时可使用PriorityQueue来合并这些序列以保持整体的排序。
源码
PriorityQueue的peek()和element操作是常数时间add()offer()无参数的remove()以及poll()方法的时间复杂度都是log(N)。
方法剖析 add()和offer() 都是向优先队列中插入元素Queue接口规定二者对插入失败时的处理不同前者在插入失败时抛出异常后者则会返回false。
新加入的元素可能会破坏小顶堆的性质因此需要进行必要的调整
public boolean offer(E e) {if (e null)throw new NullPointerException();modCount;int i size;if (i queue.length)grow(i 1);siftUp(i, e);size i 1;return true;
}扩容函数grow()类似于ArrayList里的grow()再申请一个更大的数组并将原数组的元素复制过去。siftUp(int k, E x)方法用于插入元素x并维持堆的特性。
private void siftUp(int k, E x) {if (comparator ! null)siftUpUsingComparator(k, x, queue, comparator);elsesiftUpComparable(k, x, queue);
}private static T void siftUpComparable(int k, T x, Object[] es) {Comparable? super T key (Comparable? super T) x;while (k 0) {int parent (k - 1) 1;Object e es[parent];if (key.compareTo((T) e) 0)break;es[k] e;k parent;}es[k] key;
}private static T void siftUpUsingComparator(int k, T x, Object[] es, Comparator? super T cmp) {while (k 0) {int parent (k - 1) 1;Object e es[parent];if (cmp.compare(x, (T) e) 0)break;es[k] e;k parent;}es[k] x;
}调整过程从k指定的位置开始将x逐层与当前点的parent进行比较并交换直到满足x queue[parent]为止。比较可以是元素的自然顺序也可以是依靠比较器的顺序。
element()和peek() 语义完全相同都是获取但不删除队首元素也就是队列中权值最小的那个元素唯一的区别是当方法失败时前者抛出异常后者返回null。根据小顶堆的性质堆顶那个元素就是全局最小的那个由于堆用数组表示根据下标关系0下标处的那个元素既是堆顶元素。所以直接返回数组0下标处的那个元素即可。 代码
public E peek() {return (E) queue[0];
}remove()和poll() 语义完全相同都是获取并删除队首元素区别是当方法失败时前者抛出异常后者返回null。由于删除操作会改变队列的结构为维护小顶堆的性质需要进行必要的调整。
public E poll() {final Object[] es;final E result;if ((result (E) ((es queue)[0])) ! null) {modCount;final int n;final E x (E) es[(n --size)];es[n] null;if (n 0) {final Comparator? super E cmp;if ((cmp comparator) null)siftDownComparable(0, x, es, n);elsesiftDownUsingComparator(0, x, es, n, cmp);}}return result;
}首先记录0下标处的元素并用最后一个元素替换0下标位置的元素之后调用siftDown()方法对堆进行调整最后返回原来0下标处的那个元素也就是最小的那个元素。siftDown(int k, E x)方法从k指定的位置开始将x逐层向下与当前点的左右孩子中较小的那个交换直到x小于或等于左右孩子中的任何一个为止。
private void siftDown(int k, E x) {if (comparator ! null)siftDownUsingComparator(k, x, queue, size, comparator);elsesiftDownComparable(k, x, queue, size);
}private static T void siftDownComparable(int k, T x, Object[] es, int n) {// assert n 0;Comparable? super T key (Comparable? super T)x;int half n 1; // loop while a non-leafwhile (k half) {int child (k 1) 1; // assume left child is leastObject c es[child];int right child 1;if (right n ((Comparable? super T) c).compareTo((T) es[right]) 0)c es[child right];if (key.compareTo((T) c) 0)break;es[k] c;k child;}es[k] key;
}private static T void siftDownUsingComparator(int k, T x, Object[] es, int n, Comparator? super T cmp) {// assert n 0;int half n 1;while (k half) {int child (k 1) 1;Object c es[child];int right child 1;if (right n cmp.compare((T) c, (T) es[right]) 0)c es[child right];if (cmp.compare(x, (T) c) 0)break;es[k] c;k child;}es[k] x;
}remove(Object o) 用于删除队列中跟o相等的某一个元素如果有多个相等只删除一个源自Collection接口的方法。由于删除操作会改变队列结构所以要进行调整又由于删除元素的位置可能是任意的所以调整过程比其它函数稍加繁琐。具体来说remove(Object o)可分为2种情况
删除的是最后一个元素。直接删除即可不需调整不是最后一个元素从删除点开始以最后一个元素为参照调用一次siftDown()即可。
public boolean remove(Object o) {// 通过遍历数组的方式找到第一个满足o.equals(queue[i])元素的下标int i indexOf(o);if (i -1)return false;else {removeAt(i);return true;}
}private int indexOf(Object o) {if (o ! null) {final Object[] es queue;for (int i 0, n size; i n; i)if (o.equals(es[i]))return i;}return -1;
}E removeAt(int i) {// assert i 0 i size;final Object[] es queue;modCount;int s --size;if (s i) // removed last elementes[i] null;else {E moved (E) es[s];es[s] null;siftDown(i, moved);if (es[i] moved) {siftUp(i, moved);if (es[i] ! moved)return moved;}}return null;
}堆排序
堆排序利用堆的特性来排序一个数组通常包含以下几个步骤
构建最大堆 将输入数据构建成一个最大堆从最后一个非叶子节点开始逐层向上调整堆确保每个父节点都大于或等于子节点。排序过程 将最大堆的根节点最大值与堆的最后一个元素交换然后将堆的大小减一实际上是忽略最后一个元素对新的根节点进行堆调整重新建立最大堆重复上述过程直到堆的大小为1。
示例代码
public class HeapSort {public static void heapSort(int[] arr) {PriorityQueueInteger maxHeap new PriorityQueue((a, b) - b - a);for (int num : arr) {maxHeap.offer(num);}for (int i 0; i arr.length; i) {arr[i] maxHeap.poll();}}public static void main(String[] args) {int[] arr {4, 10, 3, 5, 1};heapSort(arr);for (int num : arr) {System.out.print(num );}}
}拓展
JDK
JDK源码里基于PriorityQueue实现的数据结构主要有两个
PriorityBlockingQueue带优先级的阻塞队列DelayQueue延迟队列
PriorityBlockingQueue
在线程池里看到这个类一个支持优先级排序的无界阻塞队列。PriorityBlockingQueue不会阻塞生产者而只是在没有可消费的数据时阻塞消费者。因此使用时需要特别注意生产者生产数据的速度绝对不能快于消费者消费数据的速度否则时间一长最终会耗尽所有可用的内存空间。
PriorityBlockingQueue的几个属性
queue数组用来存放队列元素size用来存放队列元素个数lock独占锁对象用来控制某个时间只能有一个线程可以进行入队、出队操作notEmpty条件(Condition)变量用来实现take方法阻塞模式跟其它阻塞队列相比这里没有notFull条件变量这是因为PriorityBlockingQueue是无界队列其put方法是非阻塞的。allocationspinLock是个自旋锁使用CAS操作来保证某个时间只有一个线程可以扩容队列状态为0或10表示当前没有进行扩容1表示当前正在扩容
PriorityBlockingQueue内部是使用平衡二叉树堆实现的所以直接遍历队列元素不保证元素有序。
每次出队都返回优先级最高或最低的元素默认使用对象的compareTo方法提供比较规则这意味着队列元素必须实现Comparable接口如果需要自定义比较规则则可以通过构造函数自定义comparator。
DelayQueue
ScheduledExecutorService
ScheduledExecutorService是JDK提供的用于定时任务调度API支持设置任务优先级
private ScheduledExecutorService schdExctr Executors.newSingleThreadScheduledExecutor(new ThreadFactory() {private ThreadFactory factory Executors.defaultThreadFactory();Overridepublic Thread newThread(Runnable r) {Thread t factory.newThread(r);t.setPriority(Thread.MIN_PRIORITY);return t;}
});RocketMQ消息优先级
RocketMQ通过消息优先级实现消息的先入先出。消息优先级由生产者在发送消息时设置范围为0-4数字越大优先级越高。
Broker在接收到消息后会将消息存储在不同的队列中每种优先级对应一个队列。Broker会按照优先级从高到低的顺序消费队列中的消息实现高优先级消息的先消费。
消费者在消费消息时也会按照优先级从高到低的顺序拉取队列中的消息进行消费保证高优先级消息的先消费。
RocketMQ通过设置消息优先级和隔离优先级消息到不同队列来实现消息的优先级从而达到高优先级消息的先入先出。
仅供参考的代码
// 生产者发送高优先级消息
Message msg new Message(TopicTest, TagA, KEY, Hello.getBytes());
msg.setKeys(KEY1);
msg.setPriority(3); // 设置消息优先级为3
producer.send(msg);// 消费者设置消费消息的优先级
pullConsumer.setConsumeMessageAck(true);
pullConsumer.registerMessageListener(new PriorityMessageListener());public class PriorityMessageListener implements MessageListener {Overridepublic Action consumeMessage(MessageExt ext) { switch (ext.getPriority()) {case 3: // 消费优先级为3的消息 break;}}
}参考
