精华内容
下载资源
问答
  • 任务的优先队列 基于任务的PriorityQueue的实现在此程序中,用户可以: 注册新任务,并传递名称和优先级 提取并返回列表中优先级最低的任务 清除任务列表 列出所有待处理的任务及其优先级 导入和导出CSV文件中的...
  • 1.优先级队列介绍1.1 优先级队列有时在调度任务时,我们会想要先处理优先级更高的任务。例如,对于同一个柜台,在决定队列中下一个服务的用户时,总是倾向于优先服务VIP用户,而让普通用户等待,即使普通的用户是先...

    1.优先级队列介绍

    1.1 优先级队列

    有时在调度任务时,我们会想要先处理优先级更高的任务。例如,对于同一个柜台,在决定队列中下一个服务的用户时,总是倾向于优先服务VIP用户,而让普通用户等待,即使普通的用户是先加入队列的。

    优先级队列和普通的先进先出FIFO的队列类似,最大的不同在于,优先级队列中优先级最高的元素总是最先出队的,而不是遵循先进先出的顺序。

    1.2 堆

    优先级队列的接口要求很简单。从逻辑上来说,向量、链表或者平衡二叉搜索树等数据结构都可用于实现优先级队列。但考虑到时间和空间的效率,就必须仔细斟酌和考量了。而一种被称为堆的数据结构非常适合实现优先级队列。’

    堆和二叉搜索树类似,存储的元素在逻辑上是按照层次排放的,在全局任意地方其上层元素优先级大于下层元素,这一顺序性也被称为堆序性,而其中优先级最大的元素被放在最高的层级(大顶堆)。和二叉搜索树的排序方式不同的是,堆中元素的顺序并不是完全的排序,而只是维护了一种偏序关系,被称为堆序性。在这种偏序关系下,元素之间的顺序性比较疏散,维护堆序性的代价比较低,因而在实现优先级队列时,堆的效率要高于平衡二叉搜索树。

    1.3 完全二叉堆

    完全二叉堆是堆的一种,其元素在逻辑上是以完全二叉树的形式存放的,但实际却是存储在向量(数组)中的。在这里,我们使用完全二叉堆来实现优先级队列。

    3a34c58a499f67869d05e2da2afb08f0.png

    2.优先级队列ADT接口

    /*** 优先级队列 ADT接口*/

    public interface PriorityQueue {/*** 插入新数据

    *@paramnewData 新数据

    **/

    voidinsert(E newData);/*** 获得优先级最大值(窥视) 不删数据

    *@return当前优先级最大的数据

    **/E peekMax();/*** 获得并且删除当前优先级最大值

    *@return被删除的 当前优先级最大的数据*/E popMax();/*** 获得当前优先级队列 元素个数

    *@return当前优先级队列 元素个数

    **/

    intsize();/*** 是否为空

    *@returntrue 队列为空

    * false 队列不为空

    **/

    booleanisEmpty();

    }

    3.完全二叉堆实现细节

    3.1 基础属性

    完全二叉堆内部使用之前封装好的向量作为基础。和二叉搜索树类似,用户同样可以通过传入Comparator比较器来指定堆中优先级大小比较的逻辑。

    public class CompleteBinaryHeap implements PriorityQueue{/*** 内部向量

    **/

    private ArrayListinnerArrayList;/*** 比较逻辑

    **/

    private final Comparatorcomparator;/*** 当前堆的逻辑大小

    **/

    private intsize;

    构造方法:

    /*** 无参构造函数

    **/

    publicCompleteBinaryHeap() {this.innerArrayList = new ArrayList<>();this.comparator = null;

    }/*** 指定初始容量的构造函数

    *@paramdefaultCapacity 指定的初始容量

    **/

    public CompleteBinaryHeap(intdefaultCapacity){this.innerArrayList = new ArrayList<>(defaultCapacity);this.comparator = null;

    }/*** 指定初始容量的构造函数

    *@paramcomparator 指定的比较器逻辑

    **/

    public CompleteBinaryHeap(Comparatorcomparator){this.innerArrayList = new ArrayList<>();this.comparator =comparator;

    }/*** 指定初始容量和比较器的构造函数

    *@paramdefaultCapacity 指定的初始容量

    *@paramcomparator 指定的比较器逻辑

    **/

    public CompleteBinaryHeap(int defaultCapacity, Comparatorcomparator) {this.innerArrayList = new ArrayList<>(defaultCapacity);this.comparator =comparator;

    }/*** 将指定数组 转换为一个完全二叉堆

    *@paramarray 指定的数组

    **/

    publicCompleteBinaryHeap(E[] array){this.innerArrayList = new ArrayList<>(array);this.comparator = null;this.size =array.length;//批量建堆

    heapify();

    }/*** 将指定数组 转换为一个完全二叉堆

    *@paramarray 指定的数组

    *@paramcomparator 指定的比较器逻辑

    **/

    public CompleteBinaryHeap(E[] array, Comparatorcomparator){this.innerArrayList = new ArrayList<>(array);this.comparator =comparator;this.size =array.length;//批量建堆

    heapify();

    }

    3.2 辅助方法

    由于完全二叉堆在逻辑上等价于一颗完全二叉树,但实际上却采用了一维的向量数据结构来存储元素。因而我们需要实现诸如getParentIndex、getLeftChildIndex、getRightChildIndex等方法来进行完全二叉树和向量表示方法的转换。

    这里,定义了一些私有方法来封装常用的逻辑,用以简化代码。

    /*** 获得逻辑上 双亲节点下标

    *@paramcurrentIndex 当前下标

    **/

    private int getParentIndex(intcurrentIndex){return (currentIndex - 1)/2;

    }/*** 获得逻辑上 左孩子节点下标

    *@paramcurrentIndex 当前下标

    **/

    private int getLeftChildIndex(intcurrentIndex){return (currentIndex * 2) + 1;

    }/*** 获得逻辑上 右孩子节点下标

    *@paramcurrentIndex 当前下标

    **/

    private int getRightChildIndex(intcurrentIndex){return (currentIndex + 1) * 2;

    }/*** 获得末尾下标

    **/

    private intgetLastIndex(){return this.size - 1;

    }/*** 获得最后一个非叶子节点下标

    **/

    private intgetLastInternal(){return (this.size()/2) - 1;

    }/*** 交换向量中两个元素位置

    *@parama 某一个元素的下标

    *@paramb 另一个元素的下标

    **/

    private void swap(int a, intb){//现暂存a、b下标元素的值

    E aData = this.innerArrayList.get(a);

    E bData= this.innerArrayList.get(b);//交换位置

    this.innerArrayList.set(a,bData);this.innerArrayList.set(b,aData);

    }/*** 进行比较

    **/@SuppressWarnings("unchecked")private intcompare(E t1, E t2){//迭代器不存在

    if(this.comparator == null){//依赖对象本身的 Comparable,可能会转型失败

    return((Comparable) t1).compareTo(t2);

    }else{//通过迭代器逻辑进行比较

    return this.comparator.compare(t1,t2);

    }

    }

    3.3 插入和上滤

    当新元素插入完全二叉堆时,我们直接将其插入向量末尾(堆底最右侧),此时新元素的优先级可能会大于其双亲元素甚至祖先元素,破坏了堆序性,因此我们需要对插入的新元素进行一次上滤操作,使完全二叉堆恢复堆序性。由于堆序性只和双亲和孩子节点相关,因此堆中新插入元素的非祖先元素的堆序性不会受到影响,上滤只是一个局部性的行为。

    上滤操作

    上滤的元素不断的和自己的双亲节点进行优先级的比较:

    1. 如果上滤元素的优先级较大,则与双亲节点交换位置,继续向上比较。

    2. 如果上滤元素的优先级较小(等于),堆序性恢复,终止比较,结束上滤操作。

    3. 特别的,当上滤的元素被交换到树根节点时(向量下标第0位),此时由于上滤的元素是堆中的最大元素,终止上滤操作。

    上滤操作的时间复杂度:

    上滤操作时,上滤元素进行比较的次数正比于上滤元素的深度。因此,上滤操作的时间复杂度为O(logN)。

    @Overridepublic voidinsert(E newData) {//先插入新数据到 向量末尾

    this.innerArrayList.add(newData);//获得向量末尾元素下标

    int lastIndex =getLastIndex();//对向量末尾元素进行上滤,以恢复堆序性

    siftUp(lastIndex);

    }/*** 上滤操作

    *@paramindex 需要上滤的元素下标

    **/

    private void siftUp(intindex){while(index >= 0){//获得当前节点

    int parentIndex =getParentIndex(index);

    E currentData= this.innerArrayList.get(index);

    E parentData= this.innerArrayList.get(parentIndex);//如果当前元素 大于 双亲元素

    if(compare(currentData,parentData) > 0){//交换当前元素和双亲元素的位置

    swap(index,parentIndex);//继续向上迭代

    index =parentIndex;

    }else{//当前元素没有违反堆序性,直接返回

    return;

    }

    }

    }

    3.4 删除和下滤

    当优先级队列中极值元素出队时,需要在满足堆序性的前提下,选出新的极值元素。

    我们简单的将当前向量末尾的元素放在堆顶,堆序性很有可能被破坏了。此时,我们需要对当前的堆顶元素进行一次下滤操作,使得整个完全二叉堆恢复堆序性。

    下滤操作:

    下滤的元素不断的和自己的左、右孩子节点进行优先级的比较:

    1. 双亲节点最大,堆序性恢复,终止下滤。

    2. 左孩子节点最大,当前下滤节点和自己的左孩子节点交换,继续下滤。

    3.右孩子节点最大,当前下滤节点和自己的右孩子节点交换,继续下滤。

    4. 特别的,当下滤的元素抵达堆底时(成为叶子节点),堆序性已经恢复,终止下滤。

    下滤操作时间复杂度:

    下滤操作时,下滤元素进行比较的次数正比于下滤元素的高度。因此,下滤操作的时间复杂度为O(logN)。

    @OverridepublicE popMax() {if(this.innerArrayList.isEmpty()){throw new CollectionEmptyException("当前完全二叉堆为空");

    }//将当前向量末尾的元素和堆顶元素交换位置

    int lastIndex =getLastIndex();

    swap(0,lastIndex);//暂存被删除的最大元素(之前的堆顶最大元素被放到了向量末尾)

    E max = this.innerArrayList.get(lastIndex);this.size--;//对当前堆顶元素进行下滤,以恢复堆序性

    siftDown(0);returnmax;

    }/*** 下滤操作

    *@paramindex 需要下滤的元素下标

    **/

    private void siftDown(intindex){int size = this.size();//叶子节点不需要下滤

    int half = size >>> 1;while(index

    E leftData= this.innerArrayList.get(leftIndex);

    E rightData= this.innerArrayList.get(rightIndex);

    E currentData= this.innerArrayList.get(index);//比较左右孩子大小

    if(compare(leftData,rightData) >= 0){//左孩子更大,比较双亲和左孩子

    if(compare(currentData,leftData) >= 0){//双亲最大,终止下滤

    return;

    }else{//三者中,左孩子更大,交换双亲和左孩子的位置

    swap(index,leftIndex);//继续下滤操作

    index =leftIndex;

    }

    }else{//右孩子更大,比较双亲和右孩子

    if(compare(currentData,rightData) >= 0){//双亲最大,终止下滤

    return;

    }else{//三者中,右孩子更大,交换双亲和右孩子的位置

    swap(index,rightIndex);//继续下滤操作

    index =rightIndex;

    }

    }

    }else{//右孩子不存在 (下标越界)

    E leftData= this.innerArrayList.get(leftIndex);

    E currentData= this.innerArrayList.get(index);//当前节点 大于 左孩子

    if(compare(currentData,leftData) >= 0){//终止下滤

    return;

    }else{//交换 左孩子和双亲的位置

    swap(index,leftIndex);//继续下滤操作

    index =leftIndex;

    }

    }

    }

    }

    3.5 批量元素建堆

    有时,我们需要将一个无序的元素集合数组转换成一个完全二叉堆,这一操作被称为批量建堆。

    一个朴素的想法是:将无序集合中的元素依次插入一个空的完全二叉堆,对每一个新插入的元素进行上滤操作。使用上滤操作实现的对N个元素进行批量建堆的算法,其时间复杂度为O(n.logn),比较直观。

    但还存在一种效率更加高效的批量建堆算法,是以下滤操作为基础实现的,被称为Floyd建堆算法。下滤操作可以看做是将两个较小的堆合并为一个更大堆的过程(单个元素可以被视为一个最小的堆),通过从底到高不断的下滤操作,原本无序的元素集合将通过不断的合并建立较小的堆,最终完成整个集合的建堆过程。

    Floyd建堆算法的时间复杂度的证明较为复杂,其时间复杂度比起以上滤为基础的朴素算法效率高一个数量级,为O(n)。

    简单的一种解释是:在完全二叉树中,低层元素的数量要远远少于高层的数量。高层元素的高度较高而深度较低;底层元素的高度较低而深度较高。由于上滤操作的时间复杂度正比于高度,对于存在大量底层元素的完全二叉堆很不友好,使得基于上滤的批量建堆算法效率较低。

    80da9443d07da5ae4cf3246b4dfd0fe3.png

    /*** 批量建堆(将内部数组转换为完全二叉堆)

    **/

    private voidheapify(){//获取下标最大的 内部非叶子节点

    int lastInternalIndex =getLastInternal();//Floyd建堆算法 时间复杂度"O(n)"//从lastInternalIndex开始向前遍历,对每一个元素进行下滤操作,从小到大依次合并

    for(int i=lastInternalIndex; i>=0; i--){

    siftDown(i);

    }

    }

    4.堆排序

    堆排序主要分为两步进行:

    1. 堆排序首先将传入的数组转化为一个堆(floyd建堆算法,时间复杂度O(n))。

    2. 和选择排序类似,堆排序每次都从未排序的区间中选择出一个极值元素置入已排序区域,在堆中极值元素就是堆顶元素,可以通过popMax方法(时间复杂度O(logN))获得。从数组末尾向前遍历,循环往复直至排序完成,总的时间复杂度为O(N logN)。

    综上所述,堆排序的渐进时间复杂度为O(N logN)。同时由于堆排序能够在待排序数组中就地的进行排序,因此空间效率很高,空间复杂度为(O(1))。

    public static voidheapSort(T[] array){

    CompleteBinaryHeap completeBinaryHeap = new CompleteBinaryHeap<>(array);for(int i=array.length-1; i>=0; i--){

    array[i]=completeBinaryHeap.popMax();

    }

    }

    5.完整代码

    优先级队列ADT接口:

    8f900a89c6347c561fdf2122f13be562.png

    961ddebeb323a10fe0623af514929fc1.png

    1 /**

    2 * 优先级队列 ADT接口3 */

    4 public interface PriorityQueue {5

    6 /**

    7 * 插入新数据8 *@paramnewData 新数据9 **/

    10 voidinsert(E newData);11

    12 /**

    13 * 获得优先级最大值(窥视)14 *@return当前优先级最大的数据15 **/

    16 E peekMax();17

    18 /**

    19 * 获得并且删除当前优先级最大值20 *@return被删除的 当前优先级最大的数据21 */

    22 E popMax();23

    24 /**

    25 * 获得当前优先级队列 元素个数26 *@return当前优先级队列 元素个数27 **/

    28 intsize();29

    30 /**

    31 * 是否为空32 *@returntrue 队列为空33 * false 队列不为空34 **/

    35 booleanisEmpty();36 }

    View Code

    完全二叉堆实现:

    8f900a89c6347c561fdf2122f13be562.png

    961ddebeb323a10fe0623af514929fc1.png

    /*** 完全二叉堆 实现优先级队列*/

    public class CompleteBinaryHeap implements PriorityQueue{//=========================================成员属性===========================================

    /*** 内部向量

    **/

    private ArrayListinnerArrayList;/*** 比较逻辑

    **/

    private final Comparatorcomparator;/*** 当前堆的逻辑大小

    **/

    private intsize;//===========================================构造函数========================================

    /*** 无参构造函数

    **/

    publicCompleteBinaryHeap() {this.innerArrayList = new ArrayList<>();this.comparator = null;

    }/*** 指定初始容量的构造函数

    *@paramdefaultCapacity 指定的初始容量

    **/

    public CompleteBinaryHeap(intdefaultCapacity){this.innerArrayList = new ArrayList<>(defaultCapacity);this.comparator = null;

    }/*** 指定初始容量的构造函数

    *@paramcomparator 指定的比较器逻辑

    **/

    public CompleteBinaryHeap(Comparatorcomparator){this.innerArrayList = new ArrayList<>();this.comparator =comparator;

    }/*** 指定初始容量和比较器的构造函数

    *@paramdefaultCapacity 指定的初始容量

    *@paramcomparator 指定的比较器逻辑

    **/

    public CompleteBinaryHeap(int defaultCapacity, Comparatorcomparator) {this.innerArrayList = new ArrayList<>(defaultCapacity);this.comparator =comparator;

    }/*** 将指定数组 转换为一个完全二叉堆

    *@paramarray 指定的数组

    **/

    publicCompleteBinaryHeap(E[] array){this.innerArrayList = new ArrayList<>(array);this.comparator = null;this.size =array.length;//批量建堆

    heapify();

    }/*** 将指定数组 转换为一个完全二叉堆

    *@paramarray 指定的数组

    *@paramcomparator 指定的比较器逻辑

    **/

    public CompleteBinaryHeap(E[] array, Comparatorcomparator){this.innerArrayList = new ArrayList<>(array);this.comparator =comparator;this.size =array.length;//批量建堆

    heapify();

    }//==========================================外部方法===========================================

    @Overridepublic voidinsert(E newData) {//先插入新数据到 向量末尾

    this.innerArrayList.add(newData);//获得向量末尾元素下标

    int lastIndex =getLastIndex();//对向量末尾元素进行上滤,以恢复堆序性

    siftUp(lastIndex);

    }

    @OverridepublicE peekMax() {//内部数组第0位 即为堆顶max

    return this.innerArrayList.get(0);

    }

    @OverridepublicE popMax() {if(this.innerArrayList.isEmpty()){throw new CollectionEmptyException("当前完全二叉堆为空");

    }//将当前向量末尾的元素和堆顶元素交换位置

    int lastIndex =getLastIndex();

    swap(0,lastIndex);//暂存被删除的最大元素(之前的堆顶最大元素被放到了向量末尾)

    E max = this.innerArrayList.get(lastIndex);this.size--;//对当前堆顶元素进行下滤,以恢复堆序性

    siftDown(0);returnmax;

    }

    @Overridepublic intsize() {return this.size;

    }

    @Overridepublic booleanisEmpty() {return this.size() == 0;

    }

    @OverridepublicString toString() {//:::空列表

    if(this.isEmpty()){return "[]";

    }//:::列表起始使用"["

    StringBuilder s = new StringBuilder("[");//:::从第一个到倒数第二个元素之间

    for(int i=0; i

    s.append(this.innerArrayList.get(i)).append(",").append(" ");

    }//:::最后一个元素使用"]"结尾

    s.append(this.innerArrayList.get(size-1)).append("]");returns.toString();

    }public static voidheapSort(T[] array){

    CompleteBinaryHeap completeBinaryHeap = new CompleteBinaryHeap<>(array);for(int i=array.length-1; i>=0; i--){

    array[i]=completeBinaryHeap.popMax();

    }

    }//=========================================内部辅助函数===========================================

    /*** 上滤操作

    *@paramindex 需要上滤的元素下标

    **/

    private void siftUp(intindex){while(index >= 0){//获得当前节点

    int parentIndex =getParentIndex(index);

    E currentData= this.innerArrayList.get(index);

    E parentData= this.innerArrayList.get(parentIndex);//如果当前元素 大于 双亲元素

    if(compare(currentData,parentData) > 0){//交换当前元素和双亲元素的位置

    swap(index,parentIndex);//继续向上迭代

    index =parentIndex;

    }else{//当前元素没有违反堆序性,直接返回

    return;

    }

    }

    }/*** 下滤操作

    *@paramindex 需要下滤的元素下标

    **/

    private void siftDown(intindex){int size = this.size();//叶子节点不需要下滤

    int half = size >>> 1;while(index

    E leftData= this.innerArrayList.get(leftIndex);

    E rightData= this.innerArrayList.get(rightIndex);

    E currentData= this.innerArrayList.get(index);//比较左右孩子大小

    if(compare(leftData,rightData) >= 0){//左孩子更大,比较双亲和左孩子

    if(compare(currentData,leftData) >= 0){//双亲最大,终止下滤

    return;

    }else{//三者中,左孩子更大,交换双亲和左孩子的位置

    swap(index,leftIndex);//继续下滤操作

    index =leftIndex;

    }

    }else{//右孩子更大,比较双亲和右孩子

    if(compare(currentData,rightData) >= 0){//双亲最大,终止下滤

    return;

    }else{//三者中,右孩子更大,交换双亲和右孩子的位置

    swap(index,rightIndex);//继续下滤操作

    index =rightIndex;

    }

    }

    }else{//右孩子不存在 (下标越界)

    E leftData= this.innerArrayList.get(leftIndex);

    E currentData= this.innerArrayList.get(index);//当前节点 大于 左孩子

    if(compare(currentData,leftData) >= 0){//终止下滤

    return;

    }else{//交换 左孩子和双亲的位置

    swap(index,leftIndex);//继续下滤操作

    index =leftIndex;

    }

    }

    }

    }/*** 批量建堆(将内部数组转换为完全二叉堆)

    **/

    private voidheapify(){//获取下标最大的 内部非叶子节点

    int lastInternalIndex =getLastInternal();//Floyd建堆算法 时间复杂度"O(n)"//从lastInternalIndex开始向前遍历,对每一个元素进行下滤操作,从小到大依次合并

    for(int i=lastInternalIndex; i>=0; i--){

    siftDown(i);

    }

    }/*** 获得逻辑上 双亲节点下标

    *@paramcurrentIndex 当前下标

    **/

    private int getParentIndex(intcurrentIndex){return (currentIndex - 1)/2;

    }/*** 获得逻辑上 左孩子节点下标

    *@paramcurrentIndex 当前下标

    **/

    private int getLeftChildIndex(intcurrentIndex){return (currentIndex * 2) + 1;

    }/*** 获得逻辑上 右孩子节点下标

    *@paramcurrentIndex 当前下标

    **/

    private int getRightChildIndex(intcurrentIndex){return (currentIndex + 1) * 2;

    }/*** 获得当前向量末尾下标

    **/

    private intgetLastIndex(){return this.size - 1;

    }/*** 获得最后一个非叶子节点下标

    **/

    private intgetLastInternal(){return (this.size()/2) - 1;

    }/*** 交换向量中两个元素位置

    *@parama 某一个元素的下标

    *@paramb 另一个元素的下标

    **/

    private void swap(int a, intb){//现暂存a、b下标元素的值

    E aData = this.innerArrayList.get(a);

    E bData= this.innerArrayList.get(b);//交换位置

    this.innerArrayList.set(a,bData);this.innerArrayList.set(b,aData);

    }/*** 进行比较

    **/@SuppressWarnings("unchecked")private intcompare(E t1, E t2){//迭代器不存在

    if(this.comparator == null){//依赖对象本身的 Comparable,可能会转型失败

    return((Comparable) t1).compareTo(t2);

    }else{//通过迭代器逻辑进行比较

    return this.comparator.compare(t1,t2);

    }

    }

    }

    View Code

    展开全文
  • 我们知道线程池运行时,会不断从任务队列中获取任务,然后...但是有一种特殊的队列叫做优先级队列,它会对插入的数据进行优先级排序,保证优先级越高的数据首先被获取,与数据的插入顺序无关。实现优先级队列高效常...

    我们知道线程池运行时,会不断从任务队列中获取任务,然后执行任务。如果我们想实现延时或者定时执行任务,重要一点就是任务队列会根据任务延时时间的不同进行排序,延时时间越短地就排在队列的前面,先被获取执行。队列是先进先出的数据结构,就是先进入队列的数据,先被获取。但是有一种特殊的队列叫做优先级队列,它会对插入的数据进行优先级排序,保证优先级越高的数据首先被获取,与数据的插入顺序无关。

    实现优先级队列高效常用的一种方式就是使用堆。

    一. 用堆实现优先级队列

    在常用排序算法总结这篇文章中,我们详细地讲解了堆排序的实现。这里我们回顾一下。

    1.1 什么是堆它是一个完全二叉树,即除了最后一层节点不是满的,其他层节点都是满的,即左右节点都有。

    它不是二叉搜索树,即左节点的值都比父节点值小,右节点的值都不比父节点值小,这样查找的时候,就可以通过二分的方式,效率是(log N)。

    它是特殊的二叉树,它要求父节点的值不能小于子节点的值。这样保证大的值在上面,小的值在下面。所以堆遍历和查找都是低效的,因为我们只知道

    从根节点到子叶节点的每条路径都是降序的,但是各个路径之间都是没有联系的,查找一个值时,你不知道应该从左节点查找还是从右节点开始查找。

    它可以实现快速的插入和删除,效率都在(log N)左右。所以它可以实现优先级队列。

    堆是一个二叉树,但是它最简单的方式是通过数组去实现二叉树,而且因为堆是一个完全二叉树,就不存在数组空间的浪费。怎么使用数组来存储二叉树呢?就是用数组的下标来模拟二叉树的各个节点,比如说根节点就是0,第一层的左节点是1,右节点是2。由此我们可以得出下列公式:// 对于n位置的节点来说:int left = 2 * n + 1; // 左子节点int right = 2 * n + 2; // 右子节点int parent = (n - 1) / 2; // 父节点,当然n要大于0,根节点是没有父节点的

    对于堆来说,只有两个操作,插入insert和删除remove,不管插入还是删除保证堆的成立条件,1.是完全二叉树,2.父节点的值不能小于子节点的值。public void insert(int value) {         // 第一步将插入的值,直接放在最后一个位置。并将长度加一

    store[size++] = value;         // 得到新插入值所在位置。

    int index = size - 1;         while(index > 0) {             // 它的父节点位置坐标

    int parentIndex = (index - 1) / 2;             // 如果父节点的值小于子节点的值,你不满足堆的条件,那么就交换值

    if (store[index] > store[parentIndex]) {

    swap(store, index, parentIndex);

    index = parentIndex;

    } else {                 // 否则表示这条路径上的值已经满足降序,跳出循环

    break;

    }

    }

    }

    主要步骤:直接将value插入到size位置,并将size自增,这样store数组中插入一个值了。

    要保证从这个叶节点到根节点这条路径上的节点,满足父节点的值不能小于子节点。

    通过int parentIndex = (index - 1) / 2得到父节点,如果比父节点值大,那么两者位置的值交换,然后再拿这个父节点和它的父父节点比较。

    直到这个节点值比父节点值小,或者这个节点已经是根节点就退出循环。因为我们每次只插入一个值,所以只需要保证新插入位置的叶节点到根节点路径满足堆的条件,因为其他路径没做操作,肯定是满足条件的。第二因为是直接在size位置插入值,所以肯定满足是完全二叉树这个条件。因为每次循环index都是除以2这种倍数递减的方式,所以它最多循环次数是(log N)次。public int remove() {          // 将根的值记录,最后返回

    int result = store[0];          // 将最后位置的值放到根节点位置

    store[0] = store[--size];          int index = 0;          // 通过循环,保证父节点的值不能小于子节点。

    while(true) {              int leftIndex = 2 * index + 1; // 左子节点

    int rightIndex = 2 * index + 2; // 右子节点

    // leftIndex >= size 表示这个子节点还没有值。

    if (leftIndex >= size) break;              int maxIndex = leftIndex;              if (store[leftIndex] 

    swap(store, index, maxIndex);

    index = maxIndex;

    } else {                  break;

    }

    }          return result;

    }

    在堆中最大值就在根节点,所以操作步骤:将根节点的值保存到result中。

    将最后节点的值移动到根节点,再将长度减一,这样满足堆成立第一个条件,堆是一个完全二叉树。

    使用循环,来满足堆成立的第二个条件,父节点的值不能小于子节点的值。

    最后返回result。

    那么怎么样满足堆的第二个条件呢?因为根点的值现在是新值,那么就有可能比它的子节点小,所以就有可能要进行交换。我们要找出左子节点和右子节点那个值更大,因为这个值可能要和父节点值进行交换,如果它不是较大值的话,它和父节点进行交换之后,就会出现父节点的值小于子节点。

    将找到的较大子节点值和父节点值进行比较。

    如果父节点的值小于它,那么将父节点和较大子节点值进行交换,然后再比较较大子节点和它的子节点。

    如果父节点的值不小于子节点较大值,或者没有子节点(即这个节点已经是叶节点了),就跳出循环。

    每次循环我们都是以2的倍数递增,所以它也是最多循环次数是(log N)次。

    所以通过堆这种方式可以快速实现优先级队列,它的插入和删除操作的效率都是O(log N)。

    二. DelayedWorkQueue类static class DelayedWorkQueue extends AbstractQueue        implements BlockingQueue {

    从定义中看出DelayedWorkQueue是一个阻塞队列。

    2.1 重要成员属性// 初始时,数组长度大小。

    private static final int INITIAL_CAPACITY = 16;        // 使用数组来储存队列中的元素。

    private RunnableScheduledFuture>[] queue =            new RunnableScheduledFuture>[INITIAL_CAPACITY];        // 使用lock来保证多线程并发安全问题。

    private final ReentrantLock lock = new ReentrantLock();        // 队列中储存元素的大小

    private int size = 0;        //特指队列头任务所在线程

    private Thread leader = null;

    // 当队列头的任务延时时间到了,或者有新的任务变成队列头时,用来唤醒等待线程

    private final Condition available = lock.newCondition();

    DelayedWorkQueue是用数组来储存队列中的元素,那么我们看看它是怎么实现优先级队列的。

    2.2 插入元素排序siftUp方法private void siftUp(int k, RunnableScheduledFuture> key) {            // 当k==0时,就到了堆二叉树的根节点了,跳出循环

    while (k > 0) {                // 父节点位置坐标, 相当于(k - 1) / 2

    int parent = (k - 1) >>> 1;                // 获取父节点位置元素

    RunnableScheduledFuture> e = queue[parent];                // 如果key元素大于父节点位置元素,满足条件,那么跳出循环

    // 因为是从小到大排序的。

    if (key.compareTo(e) >= 0)                    break;                // 否则就将父节点元素存放到k位置

    queue[k] = e;                // 这个只有当元素是ScheduledFutureTask对象实例才有用,用来快速取消任务。

    setIndex(e, k);                // 重新赋值k,寻找元素key应该插入到堆二叉树的那个节点

    k = parent;

    }            // 循环结束,k就是元素key应该插入的节点位置

    queue[k] = key;

    setIndex(key, k);

    }

    通过循环,来查找元素key应该插入在堆二叉树那个节点位置,并交互父节点的位置。具体流程在前面已经介绍过了。

    2.3 移除元素排序siftDown方法private void siftDown(int k, RunnableScheduledFuture> key) {            int half = size >>> 1;            // 通过循环,保证父节点的值不能小于子节点。

    while (k 

    int child = (k <

    RunnableScheduledFuture> c = queue[child];                // 右子节点, 相当于 (k * 2) + 2

    int right = child + 1;                // 如果左子节点元素值大于右子节点元素值,那么右子节点才是较小值的子节点。

    // 就要将c与child值重新赋值

    if (right  0)

    c = queue[child = right];                // 如果父节点元素值小于较小的子节点元素值,那么就跳出循环

    if (key.compareTo(c) <= 0)                    break;                // 否则,父节点元素就要和子节点进行交换

    queue[k] = c;

    setIndex(c, k);

    k = child;

    }            queue[k] = key;

    setIndex(key, k);

    }

    通过循环,保证父节点的值不能小于子节点。

    2.4 插入元素方法public void put(Runnable e) {

    offer(e);

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

    }        public boolean offer(Runnable e, long timeout, TimeUnit unit) {            return offer(e);

    }

    我们发现与普通阻塞队列相比,这三个添加方法都是调用offer方法。那是因为它没有队列已满的条件,也就是说可以不断地向DelayedWorkQueue添加元素,当元素个数超过数组长度时,会进行数组扩容。public boolean offer(Runnable x) {            if (x == null)                throw new NullPointerException();

    RunnableScheduledFuture> e = (RunnableScheduledFuture>)x;            // 使用lock保证并发操作安全

    final ReentrantLock lock = this.lock;

    lock.lock();            try {                int i = size;                // 如果要超过数组长度,就要进行数组扩容

    if (i >= queue.length)                    // 数组扩容

    grow();                // 将队列中元素个数加一

    size = i + 1;                // 如果是第一个元素,那么就不需要排序,直接赋值就行了

    if (i == 0) {

    queue[0] = e;

    setIndex(e, 0);

    } else {                    // 调用siftUp方法,使插入的元素变得有序。

    siftUp(i, e);

    }                // 表示新插入的元素是队列头,更换了队列头,

    // 那么就要唤醒正在等待获取任务的线程。

    if (queue[0] == e) {

    leader = null;                    // 唤醒正在等待等待获取任务的线程

    available.signal();

    }

    } finally {

    lock.unlock();

    }            return true;

    }

    主要是三步:元素个数超过数组长度,就会调用grow()方法,进行数组扩容。

    将新元素e添加到优先级队列中对应的位置,通过siftUp方法,保证按照元素的优先级排序。

    如果新插入的元素是队列头,即更换了队列头,那么就要唤醒正在等待获取任务的线程。这些线程可能是因为原队列头元素的延时时间没到,而等待的。

    数组扩容方法:private void grow() {            int oldCapacity = queue.length;            // 每次扩容增加原来数组的一半数量。

    int newCapacity = oldCapacity + (oldCapacity >> 1); // grow 50%

    if (newCapacity 

    newCapacity = Integer.MAX_VALUE;            // 使用Arrays.copyOf来复制一个新数组

    queue = Arrays.copyOf(queue, newCapacity);

    }

    2.5 获取队列头元素

    2.5.1 立即获取队列头元素public RunnableScheduledFuture> poll() {            final ReentrantLock lock = this.lock;

    lock.lock();            try {

    RunnableScheduledFuture> first = queue[0];                // 队列头任务是null,或者任务延时时间没有到,都返回null

    if (first == null || first.getDelay(NANOSECONDS) > 0)                    return null;                else

    // 移除队列头元素

    return finishPoll(first);

    } finally {

    lock.unlock();

    }

    }

    当队列头任务是null,或者任务延时时间没有到,表示这个任务还不能返回,因此直接返回null。否则调用finishPoll方法,移除队列头元素并返回。// 移除队列头元素

    private RunnableScheduledFuture> finishPoll(RunnableScheduledFuture> f) {            // 将队列中元素个数减一

    int s = --size;            // 获取队列末尾元素x

    RunnableScheduledFuture> x = queue[s];            // 原队列末尾元素设置为null

    queue[s] = null;            if (s != 0)                // 因为移除了队列头元素,所以进行重新排序。

    siftDown(0, x);

    setIndex(f, -1);            return f;

    }

    这个方法与我们在第一节中,介绍堆的删除方法一样。先将队列中元素个数减一。

    将原队列末尾元素设置成队列头元素,再将队列末尾元素设置为null。

    调用siftDown(0, x)方法,保证按照元素的优先级排序。

    2.5.2 等待获取队列头元素public RunnableScheduledFuture> take() throws InterruptedException {            final ReentrantLock lock = this.lock;

    lock.lockInterruptibly();            try {                for (;;) {

    RunnableScheduledFuture> first = queue[0];                    // 如果没有任务,就让线程在available条件下等待。

    if (first == null)

    available.await();                    else {                        // 获取任务的剩余延时时间

    long delay = first.getDelay(NANOSECONDS);                        // 如果延时时间到了,就返回这个任务,用来执行。

    if (delay <= 0)                            return finishPoll(first);                        // 将first设置为null,当线程等待时,不持有first的引用

    first = null; // don't retain ref while waiting

    // 如果还是原来那个等待队列头任务的线程,

    // 说明队列头任务的延时时间还没有到,继续等待。

    if (leader != null)

    available.await();                        else {                            // 记录一下当前等待队列头任务的线程

    Thread thisThread = Thread.currentThread();

    leader = thisThread;                            try {                                // 当任务的延时时间到了时,能够自动超时唤醒。

    available.awaitNanos(delay);

    } finally {                                if (leader == thisThread)

    leader = null;

    }

    }

    }

    }

    } finally {                if (leader == null && queue[0] != null)                    // 唤醒等待任务的线程

    available.signal();

    lock.unlock();

    }

    }

    如果队列中没有任务,那么就让当前线程在available条件下等待。如果队列头任务的剩余延时时间delay大于0,那么就让当前线程在available条件下等待delay时间。如果队列插入了新的队列头,它的剩余延时时间肯定小于原来队列头的时间,这个时候就要唤醒等待线程,看看它是否能获取任务。

    2.5.3 超时等待获取队列头元素public RunnableScheduledFuture> poll(long timeout, TimeUnit unit)            throws InterruptedException {            long nanos = unit.toNanos(timeout);            final ReentrantLock lock = this.lock;

    lock.lockInterruptibly();            try {                for (;;) {

    RunnableScheduledFuture> first = queue[0];                    // 如果没有任务。

    if (first == null) {                        // 超时时间已到,那么就直接返回null

    if (nanos <= 0)                            return null;                        else

    // 否则就让线程在available条件下等待nanos时间

    nanos = available.awaitNanos(nanos);

    } else {                        // 获取任务的剩余延时时间

    long delay = first.getDelay(NANOSECONDS);                        // 如果延时时间到了,就返回这个任务,用来执行。

    if (delay <= 0)                            return finishPoll(first);                        // 如果超时时间已到,那么就直接返回null

    if (nanos <= 0)                            return null;                        // 将first设置为null,当线程等待时,不持有first的引用

    first = null; // don't retain ref while waiting

    // 如果超时时间小于任务的剩余延时时间,那么就有可能获取不到任务。

    // 在这里让线程等待超时时间nanos

    if (nanos 

    nanos = available.awaitNanos(nanos);                        else {

    Thread thisThread = Thread.currentThread();

    leader = thisThread;                            try {                                // 当任务的延时时间到了时,能够自动超时唤醒。

    long timeLeft = available.awaitNanos(delay);                                // 计算剩余的超时时间

    nanos -= delay - timeLeft;

    } finally {                                if (leader == thisThread)

    leader = null;

    }

    }

    }

    }

    } finally {                if (leader == null && queue[0] != null)                    // 唤醒等待任务的线程

    available.signal();

    lock.unlock();

    }

    }

    与take方法相比较,就要考虑设置的超时时间,如果超时时间到了,还没有获取到有用任务,那么就返回null。其他的与take方法中逻辑一样。

    三. 总结

    使用优先级队列DelayedWorkQueue,保证添加到队列中的任务,会按照任务的延时时间进行排序,延时时间少的任务首先被获取。

    作者:wo883721

    链接:https://www.jianshu.com/p/587901245c95

    展开全文
  • Java 优先级队列 PriorityQueue

    千次阅读 2018-08-18 11:03:52
    不可避免的想到了优先级队列,下面我看看一下Java提供的优先级队列:priorityQueue。 根据上面的继承关系,可以看到PriorityQueue也实现了Collection的接口,不免让人想到List。 什么是队列,队列的性质什么的...

    碰到一个场景,我们要是实现一个任务调度系统,但是呢任务是分等级的,也就是说比较高级的任务必须优先执行,那么这个任务调度系统需要怎么设计呢?不可避免的想到了优先级队列,下面我看看一下Java提供的优先级队列:priorityQueue。
    这里写图片描述
    根据上面的继承关系,可以看到PriorityQueue也实现了Collection的接口,不免让人想到List。
    什么是队列,队列的性质什么的这里不再介绍,有点编程知识的都应该知道。
    优先级队列,既然是优先级,那么内部肯定有一定的规则进行排序,并每一次出队列的保证是优先级最高的。
    优先级队列的用法实际上很简单,需要实现是一个比较器,内部根据这个比较器来判定谁的优先级比较高:

    public class MyComparator implements Comparator<Student> {
    
        @Override
        public int compare(Student o1, Student o2) {
            return -(o1.getId() - o2.getId());
        }
    }

    用起来也很简单:

     public static void main(String[] args) {
            Queue<Integer> queue = new  PriorityQueue();
            queue.add(1);
            queue.add(2);
            queue.add(5);
            queue.add(3);
            while (!queue.isEmpty()){
                System.out.println(queue.poll());
            }
    
            Queue<Student> queue1 = new  PriorityQueue(new MyComparator());
            Student st1 = new Student("ming1", 10);
            Student st2 = new Student("ming2", 11);
            Student st3 = new Student("ming3", 9);
            Student st4 = new Student("ming4", 20);
            Student st5 = new Student("ming5", 1);
            queue1.add(st1);
            queue1.add(st2);
            queue1.add(st3);
            queue1.add(st4);
            queue1.add(st5);
    
            while (!queue1.isEmpty()){
                System.out.println(queue1.poll().getId());
            }
        }

    打印出来的结果:

    1
    2
    3
    5
    
    20
    11
    10
    9
    1

    那我们看下优先级队列的源码,优先级队列的实现实际上按照堆的思想来进行的,如果不了解堆的话,可以先复习一下树的相关知识:
    他有好多种构造方法:

       transient Object[] queue; // non-private to simplify nested class access
       private static final int DEFAULT_INITIAL_CAPACITY = 11;
        public PriorityQueue(int initialCapacity,
                             Comparator<? super E> comparator) {
    
            if (initialCapacity < 1)
                throw new IllegalArgumentException();
            this.queue = new Object[initialCapacity];
            this.comparator = comparator;
        }

    上面只列出了一个构造方法,实际他有很多的,但是最后都会调到这个方法里面来 ,进行队列的初始化,可以看到默认的大小是11,当然你可以不用传初始化的数组的大小与比较器。

    我们来看向队列中添加的方法:

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

    上面的代码最重要的是,插入数据中能保证堆的结构不变,插入数据的时候都在最后,但是在siftUpComparable 方法中,对数据根据比较器的结果对数据进行上移,保证第一个永远是优先级最高的。

    出队列的时候, 没出一个元素,堆的优先级就需要调整,进队的时候是从下向上的调整,那么出队列正好相反,从上往下调整:

        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);
        }
    
        @SuppressWarnings("unchecked")
        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; // 这个是拿到左节点
                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;
        }
    

    上面的代码中,首先拿到的是第一个节点的左节点,和又节点,在我们进队列的时候,就已经保证了父节点的优先级一定高于子节点,但是并没有保证左节点一定比右节点的的优先级高,所以需要比价左右节点的优先级。

    还有一点的是扩容:

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

    扩容也很简单,如果当前的容量小于64,扩大两倍,如果大于64,扩大原来容量的1/2.

    有一点需要注意的是,PriorityQueue不是线程安全的,如果多线程的话 则需要另外一个优先级队列: PriorityBlockingQueue 实现和PriorityQueue是差不多的,区别是在进队和出队的时候加了锁 lock.lock();

    欢迎关注我的微信号: manong_xiaodong

    这里写图片描述

    展开全文
  • 1.优先级队列介绍1.1 优先级队列有时在调度任务时,我们会想要先处理优先级更高的任务。例如,对于同一个柜台,在决定队列中下一个服务的用户时,总是倾向于优先服务VIP用户,而让普通用户等待,即使普通的用户是先...

    1.优先级队列介绍

    1.1 优先级队列

    有时在调度任务时,我们会想要先处理优先级更高的任务。例如,对于同一个柜台,在决定队列中下一个服务的用户时,总是倾向于优先服务VIP用户,而让普通用户等待,即使普通的用户是先加入队列的。

    优先级队列和普通的先进先出FIFO的队列类似,最大的不同在于,优先级队列中优先级最高的元素总是最先出队的,而不是遵循先进先出的顺序。

    1.2 堆

    优先级队列的接口要求很简单。从逻辑上来说,向量、链表或者平衡二叉搜索树等数据结构都可用于实现优先级队列。但考虑到时间和空间的效率,就必须仔细斟酌和考量了。而一种被称为堆的数据结构非常适合实现优先级队列。’

    堆和二叉搜索树类似,存储的元素在逻辑上是按照层次排放的,在全局任意地方其上层元素优先级大于下层元素,这一顺序性也被称为堆序性,而其中优先级最大的元素被放在最高的层级(大顶堆)。和二叉搜索树的排序方式不同的是,堆中元素的顺序并不是完全的排序,而只是维护了一种偏序关系,被称为堆序性。在这种偏序关系下,元素之间的顺序性比较疏散,维护堆序性的代价比较低,因而在实现优先级队列时,堆的效率要高于平衡二叉搜索树。

    1.3 完全二叉堆

    完全二叉堆是堆的一种,其元素在逻辑上是以完全二叉树的形式存放的,但实际却是存储在向量(数组)中的。在这里,我们使用完全二叉堆来实现优先级队列。

    AAffA0nNPuCLAAAAAElFTkSuQmCC

    2.优先级队列ADT接口

    AAffA0nNPuCLAAAAAElFTkSuQmCC/**

    * 优先级队列 ADT接口 */public interface PriorityQueue {    /**

    * 插入新数据

    * @param newData 新数据

    * */

    void insert(E newData);    /**

    * 获得优先级最大值(窥视) 不删数据

    * @return  当前优先级最大的数据

    * */

    E peekMax();    /**

    * 获得并且删除当前优先级最大值

    * @return  被删除的 当前优先级最大的数据     */

    E popMax();    /**

    * 获得当前优先级队列 元素个数

    * @return 当前优先级队列 元素个数

    * */

    int size();    /**

    * 是否为空

    * @return true  队列为空

    *         false 队列不为空

    * */

    boolean isEmpty();

    }

    AAffA0nNPuCLAAAAAElFTkSuQmCC

    3.完全二叉堆实现细节

    3.1 基础属性

    完全二叉堆内部使用之前封装好的向量作为基础。和二叉搜索树类似,用户同样可以通过传入Comparator比较器来指定堆中优先级大小比较的逻辑。

    AAffA0nNPuCLAAAAAElFTkSuQmCCpublic class CompleteBinaryHeap implements PriorityQueue{    /**

    * 内部向量

    * */

    private ArrayList innerArrayList;    /**

    * 比较逻辑

    * */

    private final Comparator comparator;    /**

    * 当前堆的逻辑大小

    * */

    private int size;

    AAffA0nNPuCLAAAAAElFTkSuQmCC

    构造方法:

    AAffA0nNPuCLAAAAAElFTkSuQmCC/**

    * 无参构造函数

    * */

    public CompleteBinaryHeap() {        this.innerArrayList = new ArrayList<>();        this.comparator = null;

    }    /**

    * 指定初始容量的构造函数

    * @param defaultCapacity 指定的初始容量

    * */

    public CompleteBinaryHeap(int defaultCapacity){        this.innerArrayList = new ArrayList<>(defaultCapacity);        this.comparator = null;

    }    /**

    * 指定初始容量的构造函数

    * @param comparator 指定的比较器逻辑

    * */

    public CompleteBinaryHeap(Comparator comparator){        this.innerArrayList = new ArrayList<>();        this.comparator = comparator;

    }    /**

    * 指定初始容量和比较器的构造函数

    * @param defaultCapacity 指定的初始容量

    * @param comparator 指定的比较器逻辑

    * */

    public CompleteBinaryHeap(int defaultCapacity, Comparator comparator) {        this.innerArrayList = new ArrayList<>(defaultCapacity);        this.comparator = comparator;

    }    /**

    * 将指定数组 转换为一个完全二叉堆

    * @param array 指定的数组

    * */

    public CompleteBinaryHeap(E[] array){        this.innerArrayList = new ArrayList<>(array);        this.comparator = null;        this.size = array.length;        // 批量建堆        heapify();

    }    /**

    * 将指定数组 转换为一个完全二叉堆

    * @param array 指定的数组

    * @param comparator 指定的比较器逻辑

    * */

    public CompleteBinaryHeap(E[] array, Comparator comparator){        this.innerArrayList = new ArrayList<>(array);        this.comparator = comparator;        this.size = array.length;        // 批量建堆        heapify();

    }

    AAffA0nNPuCLAAAAAElFTkSuQmCC

    3.2 辅助方法

    由于完全二叉堆在逻辑上等价于一颗完全二叉树,但实际上却采用了一维的向量数据结构来存储元素。因而我们需要实现诸如getParentIndex、getLeftChildIndex、getRightChildIndex等方法来进行完全二叉树和向量表示方法的转换。

    这里,定义了一些私有方法来封装常用的逻辑,用以简化代码。

    AAffA0nNPuCLAAAAAElFTkSuQmCC/**

    * 获得逻辑上 双亲节点下标

    * @param currentIndex 当前下标

    * */

    private int getParentIndex(int currentIndex){        return (currentIndex - 1)/2;

    }    /**

    * 获得逻辑上 左孩子节点下标

    * @param currentIndex 当前下标

    * */

    private int getLeftChildIndex(int currentIndex){        return (currentIndex * 2) + 1;

    }    /**

    * 获得逻辑上 右孩子节点下标

    * @param currentIndex 当前下标

    * */

    private int getRightChildIndex(int currentIndex){        return (currentIndex + 1) * 2;

    }    /**

    * 获得末尾下标

    * */

    private int getLastIndex(){        return this.size - 1;

    }    /**

    * 获得最后一个非叶子节点下标

    * */

    private int getLastInternal(){        return (this.size()/2) - 1;

    }    /**

    * 交换向量中两个元素位置

    * @param a 某一个元素的下标

    * @param b 另一个元素的下标

    * */

    private void swap(int a, int b){        // 现暂存a、b下标元素的值

    E aData = this.innerArrayList.get(a);

    E bData = this.innerArrayList.get(b);        // 交换位置

    this.innerArrayList.set(a,bData);        this.innerArrayList.set(b,aData);

    }    /**

    * 进行比较

    * */

    @SuppressWarnings("unchecked")    private int compare(E t1, E t2){        // 迭代器不存在

    if(this.comparator == null){            // 依赖对象本身的 Comparable,可能会转型失败

    return ((Comparable) t1).compareTo(t2);

    }else{            // 通过迭代器逻辑进行比较

    return this.comparator.compare(t1,t2);

    }

    }

    AAffA0nNPuCLAAAAAElFTkSuQmCC

    3.3 插入和上滤

    当新元素插入完全二叉堆时,我们直接将其插入向量末尾(堆底最右侧),此时新元素的优先级可能会大于其双亲元素甚至祖先元素,破坏了堆序性,因此我们需要对插入的新元素进行一次上滤操作,使完全二叉堆恢复堆序性。由于堆序性只和双亲和孩子节点相关,因此堆中新插入元素的非祖先元素的堆序性不会受到影响,上滤只是一个局部性的行为。

    上滤操作

    上滤的元素不断的和自己的双亲节点进行优先级的比较:

    1. 如果上滤元素的优先级较大,则与双亲节点交换位置,继续向上比较。

    2. 如果上滤元素的优先级较小(等于),堆序性恢复,终止比较,结束上滤操作。

    3. 特别的,当上滤的元素被交换到树根节点时(向量下标第0位),此时由于上滤的元素是堆中的最大元素,终止上滤操作。

    上滤操作的时间复杂度:

    上滤操作时,上滤元素进行比较的次数正比于上滤元素的深度。因此,上滤操作的时间复杂度为O(logN)。

    AAffA0nNPuCLAAAAAElFTkSuQmCC@Override    public void insert(E newData) {        // 先插入新数据到 向量末尾

    this.innerArrayList.add(newData);        // 获得向量末尾元素下标

    int lastIndex = getLastIndex();        // 对向量末尾元素进行上滤,以恢复堆序性        siftUp(lastIndex);

    }   /**

    * 上滤操作

    * @param index 需要上滤的元素下标

    * */

    private void siftUp(int index){        while(index >= 0){            // 获得当前节点

    int parentIndex = getParentIndex(index);

    E currentData = this.innerArrayList.get(index);

    E parentData = this.innerArrayList.get(parentIndex);            // 如果当前元素 大于 双亲元素

    if(compare(currentData,parentData) > 0){                // 交换当前元素和双亲元素的位置                swap(index,parentIndex);                // 继续向上迭代

    index = parentIndex;

    }else{                // 当前元素没有违反堆序性,直接返回

    return;

    }

    }

    }

    AAffA0nNPuCLAAAAAElFTkSuQmCC

    3.4 删除和下滤

    当优先级队列中极值元素出队时,需要在满足堆序性的前提下,选出新的极值元素。

    我们简单的将当前向量末尾的元素放在堆顶,堆序性很有可能被破坏了。此时,我们需要对当前的堆顶元素进行一次下滤操作,使得整个完全二叉堆恢复堆序性。

    下滤操作:

    下滤的元素不断的和自己的左、右孩子节点进行优先级的比较:

    1. 双亲节点最大,堆序性恢复,终止下滤。

    2. 左孩子节点最大,当前下滤节点和自己的左孩子节点交换,继续下滤。

    3.右孩子节点最大,当前下滤节点和自己的右孩子节点交换,继续下滤。

    4. 特别的,当下滤的元素抵达堆底时(成为叶子节点),堆序性已经恢复,终止下滤。

    下滤操作时间复杂度:

    下滤操作时,下滤元素进行比较的次数正比于下滤元素的高度。因此,下滤操作的时间复杂度为O(logN)。

    AAffA0nNPuCLAAAAAElFTkSuQmCC@Override    public E popMax() {        if(this.innerArrayList.isEmpty()){            throw new CollectionEmptyException("当前完全二叉堆为空");

    }        // 将当前向量末尾的元素和堆顶元素交换位置

    int lastIndex = getLastIndex();

    swap(0,lastIndex);        // 暂存被删除的最大元素(之前的堆顶最大元素被放到了向量末尾)

    E max = this.innerArrayList.get(lastIndex);        this.size--;        // 对当前堆顶元素进行下滤,以恢复堆序性

    siftDown(0);        return max;

    }  /**

    * 下滤操作

    * @param index 需要下滤的元素下标

    * */

    private void siftDown(int index){        int size = this.size();        // 叶子节点不需要下滤

    int half = size >>> 1;        while(index 

    E leftData = this.innerArrayList.get(leftIndex);

    E rightData = this.innerArrayList.get(rightIndex);

    E currentData = this.innerArrayList.get(index);                // 比较左右孩子大小

    if(compare(leftData,rightData) >= 0){                    // 左孩子更大,比较双亲和左孩子

    if(compare(currentData,leftData) >= 0){                        // 双亲最大,终止下滤

    return;

    }else{                        // 三者中,左孩子更大,交换双亲和左孩子的位置                        swap(index,leftIndex);                        // 继续下滤操作

    index = leftIndex;

    }

    }else{                    // 右孩子更大,比较双亲和右孩子

    if(compare(currentData,rightData) >= 0){                        // 双亲最大,终止下滤

    return;

    }else{                        // 三者中,右孩子更大,交换双亲和右孩子的位置                        swap(index,rightIndex);                        // 继续下滤操作

    index = rightIndex;

    }

    }

    }else{                // 右孩子不存在 (下标越界)

    E leftData = this.innerArrayList.get(leftIndex);

    E currentData = this.innerArrayList.get(index);                // 当前节点 大于 左孩子

    if(compare(currentData,leftData) >= 0){                    // 终止下滤

    return;

    }else{                    // 交换 左孩子和双亲的位置                    swap(index,leftIndex);                    // 继续下滤操作

    index = leftIndex;

    }

    }

    }

    }

    AAffA0nNPuCLAAAAAElFTkSuQmCC

    3.5 批量元素建堆

    有时,我们需要将一个无序的元素集合数组转换成一个完全二叉堆,这一操作被称为批量建堆。

    一个朴素的想法是:将无序集合中的元素依次插入一个空的完全二叉堆,对每一个新插入的元素进行上滤操作。使用上滤操作实现的对N个元素进行批量建堆的算法,其时间复杂度为O(n.logn),比较直观。

    但还存在一种效率更加高效的批量建堆算法,是以下滤操作为基础实现的,被称为Floyd建堆算法。下滤操作可以看做是将两个较小的堆合并为一个更大堆的过程(单个元素可以被视为一个最小的堆),通过从底到高不断的下滤操作,原本无序的元素集合将通过不断的合并建立较小的堆,最终完成整个集合的建堆过程。

    Floyd建堆算法的时间复杂度的证明较为复杂,其时间复杂度比起以上滤为基础的朴素算法效率高一个数量级,为O(n)。

    简单的一种解释是:在完全二叉树中,低层元素的数量要远远少于高层的数量。高层元素的高度较高而深度较低;底层元素的高度较低而深度较高。由于上滤操作的时间复杂度正比于高度,对于存在大量底层元素的完全二叉堆很不友好,使得基于上滤的批量建堆算法效率较低。

    AAffA0nNPuCLAAAAAElFTkSuQmCC

    AAffA0nNPuCLAAAAAElFTkSuQmCC/**

    * 批量建堆(将内部数组转换为完全二叉堆)

    * */

    private void heapify(){        // 获取下标最大的 内部非叶子节点

    int lastInternalIndex = getLastInternal();        // Floyd建堆算法 时间复杂度"O(n)"        // 从lastInternalIndex开始向前遍历,对每一个元素进行下滤操作,从小到大依次合并

    for(int i=lastInternalIndex; i>=0; i--){

    siftDown(i);

    }

    }

    AAffA0nNPuCLAAAAAElFTkSuQmCC

    4.堆排序

    堆排序主要分为两步进行:

    1. 堆排序首先将传入的数组转化为一个堆(floyd建堆算法,时间复杂度O(n))。

    2. 和选择排序类似,堆排序每次都从未排序的区间中选择出一个极值元素置入已排序区域,在堆中极值元素就是堆顶元素,可以通过popMax方法(时间复杂度O(logN))获得。从数组末尾向前遍历,循环往复直至排序完成,总的时间复杂度为O(N logN)。

    综上所述,堆排序的渐进时间复杂度为O(N logN)。同时由于堆排序能够在待排序数组中就地的进行排序,因此空间效率很高,空间复杂度为(O(1))。

    AAffA0nNPuCLAAAAAElFTkSuQmCCpublic static  void heapSort(T[] array){

    CompleteBinaryHeap completeBinaryHeap = new CompleteBinaryHeap<>(array);        for(int i=array.length-1; i>=0; i--){

    array[i] = completeBinaryHeap.popMax();

    }

    }

    AAffA0nNPuCLAAAAAElFTkSuQmCC

    5.完整代码

    优先级队列ADT接口:

    AAffA0nNPuCLAAAAAElFTkSuQmCC

    AAffA0nNPuCLAAAAAElFTkSuQmCC

    AAffA0nNPuCLAAAAAElFTkSuQmCC1 /** 2  * 优先级队列 ADT接口 3  */ 4 public interface PriorityQueue { 5  6     /** 7      * 插入新数据 8      * @param newData 新数据 9      * */10     void insert(E newData);11 12     /**13      * 获得优先级最大值(窥视)14      * @return  当前优先级最大的数据15      * */16     E peekMax();17 18     /**19      * 获得并且删除当前优先级最大值20      * @return  被删除的 当前优先级最大的数据21      */22     E popMax();23 24     /**25      * 获得当前优先级队列 元素个数26      * @return 当前优先级队列 元素个数27      * */28     int size();29 30     /**31      * 是否为空32      * @return true 队列为空33      *          false 队列不为空34      * */35     boolean isEmpty();36 }

    AAffA0nNPuCLAAAAAElFTkSuQmCC

    View Code

    完全二叉堆实现:

    AAffA0nNPuCLAAAAAElFTkSuQmCC

    AAffA0nNPuCLAAAAAElFTkSuQmCC

    AAffA0nNPuCLAAAAAElFTkSuQmCC/**

    * 完全二叉堆 实现优先级队列 */public class CompleteBinaryHeap implements PriorityQueue{    // =========================================成员属性===========================================

    /**

    * 内部向量

    * */

    private ArrayList innerArrayList;    /**

    * 比较逻辑

    * */

    private final Comparator comparator;    /**

    * 当前堆的逻辑大小

    * */

    private int size;    // ===========================================构造函数========================================

    /**

    * 无参构造函数

    * */

    public CompleteBinaryHeap() {        this.innerArrayList = new ArrayList<>();        this.comparator = null;

    }    /**

    * 指定初始容量的构造函数

    * @param defaultCapacity 指定的初始容量

    * */

    public CompleteBinaryHeap(int defaultCapacity){        this.innerArrayList = new ArrayList<>(defaultCapacity);        this.comparator = null;

    }    /**

    * 指定初始容量的构造函数

    * @param comparator 指定的比较器逻辑

    * */

    public CompleteBinaryHeap(Comparator comparator){        this.innerArrayList = new ArrayList<>();        this.comparator = comparator;

    }    /**

    * 指定初始容量和比较器的构造函数

    * @param defaultCapacity 指定的初始容量

    * @param comparator 指定的比较器逻辑

    * */

    public CompleteBinaryHeap(int defaultCapacity, Comparator comparator) {        this.innerArrayList = new ArrayList<>(defaultCapacity);        this.comparator = comparator;

    }    /**

    * 将指定数组 转换为一个完全二叉堆

    * @param array 指定的数组

    * */

    public CompleteBinaryHeap(E[] array){        this.innerArrayList = new ArrayList<>(array);        this.comparator = null;        this.size = array.length;        // 批量建堆        heapify();

    }    /**

    * 将指定数组 转换为一个完全二叉堆

    * @param array 指定的数组

    * @param comparator 指定的比较器逻辑

    * */

    public CompleteBinaryHeap(E[] array, Comparator comparator){        this.innerArrayList = new ArrayList<>(array);        this.comparator = comparator;        this.size = array.length;        // 批量建堆        heapify();

    }    // ==========================================外部方法===========================================

    @Override    public void insert(E newData) {        // 先插入新数据到 向量末尾

    this.innerArrayList.add(newData);        // 获得向量末尾元素下标

    int lastIndex = getLastIndex();        // 对向量末尾元素进行上滤,以恢复堆序性        siftUp(lastIndex);

    }

    @Override    public E peekMax() {        // 内部数组第0位 即为堆顶max

    return this.innerArrayList.get(0);

    }

    @Override    public E popMax() {        if(this.innerArrayList.isEmpty()){            throw new CollectionEmptyException("当前完全二叉堆为空");

    }        // 将当前向量末尾的元素和堆顶元素交换位置

    int lastIndex = getLastIndex();

    swap(0,lastIndex);        // 暂存被删除的最大元素(之前的堆顶最大元素被放到了向量末尾)

    E max = this.innerArrayList.get(lastIndex);        this.size--;        // 对当前堆顶元素进行下滤,以恢复堆序性

    siftDown(0);        return max;

    }

    @Override    public int size() {        return this.size;

    }

    @Override    public boolean isEmpty() {        return this.size() == 0;

    }

    @Override    public String toString() {        //:::空列表

    if(this.isEmpty()){            return "[]";

    }        //:::列表起始使用"["

    StringBuilder s = new StringBuilder("[");        //:::从第一个到倒数第二个元素之间

    for(int i=0; i

    s.append(this.innerArrayList.get(i)).append(",").append(" ");

    }        //:::最后一个元素使用"]"结尾

    s.append(this.innerArrayList.get(size-1)).append("]");        return s.toString();

    }    public static  void heapSort(T[] array){

    CompleteBinaryHeap completeBinaryHeap = new CompleteBinaryHeap<>(array);        for(int i=array.length-1; i>=0; i--){

    array[i] = completeBinaryHeap.popMax();

    }

    }    // =========================================内部辅助函数===========================================

    /**

    * 上滤操作

    * @param index 需要上滤的元素下标

    * */

    private void siftUp(int index){        while(index >= 0){            // 获得当前节点

    int parentIndex = getParentIndex(index);

    E currentData = this.innerArrayList.get(index);

    E parentData = this.innerArrayList.get(parentIndex);            // 如果当前元素 大于 双亲元素

    if(compare(currentData,parentData) > 0){                // 交换当前元素和双亲元素的位置                swap(index,parentIndex);                // 继续向上迭代

    index = parentIndex;

    }else{                // 当前元素没有违反堆序性,直接返回

    return;

    }

    }

    }    /**

    * 下滤操作

    * @param index 需要下滤的元素下标

    * */

    private void siftDown(int index){        int size = this.size();        // 叶子节点不需要下滤

    int half = size >>> 1;        while(index 

    E leftData = this.innerArrayList.get(leftIndex);

    E rightData = this.innerArrayList.get(rightIndex);

    E currentData = this.innerArrayList.get(index);                // 比较左右孩子大小

    if(compare(leftData,rightData) >= 0){                    // 左孩子更大,比较双亲和左孩子

    if(compare(currentData,leftData) >= 0){                        // 双亲最大,终止下滤

    return;

    }else{                        // 三者中,左孩子更大,交换双亲和左孩子的位置                        swap(index,leftIndex);                        // 继续下滤操作

    index = leftIndex;

    }

    }else{                    // 右孩子更大,比较双亲和右孩子

    if(compare(currentData,rightData) >= 0){                        // 双亲最大,终止下滤

    return;

    }else{                        // 三者中,右孩子更大,交换双亲和右孩子的位置                        swap(index,rightIndex);                        // 继续下滤操作

    index = rightIndex;

    }

    }

    }else{                // 右孩子不存在 (下标越界)

    E leftData = this.innerArrayList.get(leftIndex);

    E currentData = this.innerArrayList.get(index);                // 当前节点 大于 左孩子

    if(compare(currentData,leftData) >= 0){                    // 终止下滤

    return;

    }else{                    // 交换 左孩子和双亲的位置                    swap(index,leftIndex);                    // 继续下滤操作

    index = leftIndex;

    }

    }

    }

    }    /**

    * 批量建堆(将内部数组转换为完全二叉堆)

    * */

    private void heapify(){        // 获取下标最大的 内部非叶子节点

    int lastInternalIndex = getLastInternal();        // Floyd建堆算法 时间复杂度"O(n)"        // 从lastInternalIndex开始向前遍历,对每一个元素进行下滤操作,从小到大依次合并

    for(int i=lastInternalIndex; i>=0; i--){

    siftDown(i);

    }

    }    /**

    * 获得逻辑上 双亲节点下标

    * @param currentIndex 当前下标

    * */

    private int getParentIndex(int currentIndex){        return (currentIndex - 1)/2;

    }    /**

    * 获得逻辑上 左孩子节点下标

    * @param currentIndex 当前下标

    * */

    private int getLeftChildIndex(int currentIndex){        return (currentIndex * 2) + 1;

    }    /**

    * 获得逻辑上 右孩子节点下标

    * @param currentIndex 当前下标

    * */

    private int getRightChildIndex(int currentIndex){        return (currentIndex + 1) * 2;

    }    /**

    * 获得当前向量末尾下标

    * */

    private int getLastIndex(){        return this.size - 1;

    }    /**

    * 获得最后一个非叶子节点下标

    * */

    private int getLastInternal(){        return (this.size()/2) - 1;

    }    /**

    * 交换向量中两个元素位置

    * @param a 某一个元素的下标

    * @param b 另一个元素的下标

    * */

    private void swap(int a, int b){        // 现暂存a、b下标元素的值

    E aData = this.innerArrayList.get(a);

    E bData = this.innerArrayList.get(b);        // 交换位置

    this.innerArrayList.set(a,bData);        this.innerArrayList.set(b,aData);

    }    /**

    * 进行比较

    * */

    @SuppressWarnings("unchecked")    private int compare(E t1, E t2){        // 迭代器不存在

    if(this.comparator == null){            // 依赖对象本身的 Comparable,可能会转型失败

    return ((Comparable) t1).compareTo(t2);

    }else{            // 通过迭代器逻辑进行比较

    return this.comparator.compare(t1,t2);

    }

    }

    }

    AAffA0nNPuCLAAAAAElFTkSuQmCC

    View Code

    展开全文
  • 在做线程池操作的时候,突然来个加紧处理时,会很纠结,不...PS:该Demo的缺陷,每次加入新任务时,是和队头比较,如果和队头的优先级一样则放在队头的后面~~比如:队列544441.[代码][Java]代码package test.thre...
  •   聊堆不能不聊优先级队列优先级队列就是决定哪个任务优先执行的队列,通常会有一个优先级的数据,通过数据的大小来判断优先级,实现优先级队列其实有三种方式: 第一种:无序数组队列,这种在入队时的时间...
  • 1.优先级队列介绍 1.1 优先级队列  有时在调度任务时,我们会想要先处理优先级更高的任务。例如,对于同一个柜台,在决定队列中下一个服务的用户时,总是倾向于优先服务VIP用户,而让普通用户等待,即使普通的...
  • 优先级队列的一个典型应用,就是排队任务的有限调度,当一个任务结束后,优先执行当前优先级最高的任务。队列一个任务是,调用INSERT方法。 packagelhz.algorithm.chapter.six; /** *“优先级队列”,《算法导论...
  • Java/Android优先级任务队列,适用于Java和Android开发人员,原理详解博客:http://blog.csdn.net/yanzhenjie1003/article/details/71773950
  • 队列 有序队列数据结构的生命周期比那些数据库类型的结构(比如链表,树)要短得多。在程序操作执行期间他们才被创建,通常用他们去执行某项特殊的任务;当完成任务之后,他们就会被销毁。这三个数据结构还有一个...
  • 写在前面 有很多时候,一些数据的存储不仅需要先进先出,而且还有根据...其实优先级队列的应用十分广泛,比如说构造哈夫曼树算法,再比如在一些计算机操作系统中用优先级队列来来满足抢先式多任务操作系统等等等等
  • 队列 有序队列数据结构的生命周期比那些数据库类型的结构(比如链表,树)要短得多。在程序操作执行期间他们才被创建,通常用他们去执行某项特殊的任务;当完成任务之后,他们就会被销毁。这三个数据结构还有一个...
  • Java/Android中的优先级任务队列的实践

    万次阅读 多人点赞 2017-05-12 22:18:32
    本篇文章适用于Java和Android开发者,会从实现一个最简单的队列过渡到实现一个带有优先级队列,使用生活中最常见的的例子结合讲解,保准你可以掌握基本的队列原理。
  • 在上一篇文章中分享了堆这种数据结构,同时提到,堆可以用来对数据排序,也可以用来解决Top N、定时任务优先级队列等问题,今天要分享的是Java优先级队列PriorityQueue的源码实现,看看堆在Java中的实际应用。...
  • eventx: 极简的java异步事件处理组件,使用优先级队列线程池。特点:简单、易于使用。可为事件设置优先级,处理完一个任务即提升等待任务的优先级,在任务优先级与创建时间中取得平衡。主要组成部分:发送事件类--...
  • 在说队列之前说两个名词:Task是任务,TaskExecutor是任务执行器 而我们今天要说的队列就完全符合某机构这个情况,队列在有Task进来的时候TaskExecutor就立刻开始执行Task,当没有Task的时候TaskExecutor就处于一个...
  • 需求需要根据优先级执行任务,有任务不是特别...简单测试创建一个使用支持优先级队列(new PriorityBlockingQueue<>() )的线程,然后每个任务实现 java.lang.Comparable 接口new ThreadPoolExecutor(MAX_THR...
  • 该项目实现持久的优先级队列(或工人队列)(如SQS,RabbitMQ的等)超过SQL。 为什么? 在某些情况下,您无法安装队列,而您所拥有的只是某种老式的sql服务器。 该API支持以下操作: CREATE(queue_name)-将创建...
  • 文章目录11.2 剖析 PriorityQueue11.2.1 基本概念11.2.2 基本用法11.2.2.1 Queue 接口11.2.2.2 构造方法11.2.2.3 基本例子11.2.2.4 任务队列11.2.3 实现原理11.2.3.1 内部组成11.2.3.2 基本构造方法11.2.3.3 添加...

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 222
精华内容 88
关键字:

任务优先级队列java

java 订阅