本教程操作环境:windows7系统、java10版,DELL G3电脑。
1.入队规则
(1)默认的插入规则中,新加入的元素可能会破坏小顶堆的性质,因此需要进行调整。
(2)调整的过程为:从尾部下标的位置开始,将加入的元素逐层与当前点的父节点的内容进行比较并交换,直到满足父节点内容都小于子节点的内容为止。
(3)默认的删除调整中,首先获取顶部下标和最尾部的元素内容,从顶部的位置开始,将尾部元素的内容逐层向下与当前点的左右子节点中较小的那个交换,直到判断元素内容小于或等于左右子节点中的任何一个为止。
2.入队方法
入队方法有:add(E), put(E), offer(E, timeout, TimeUnit), offer(E)
publicvoidput(Ee){ offer(e);//neverneedtoblock } publicbooleanoffer(Ee){ //判断是否为空 if(e==null) thrownewNullPointerException(); //显示锁 finalReentrantLocklock=this.lock; lock.lock(); //定义临时对象 intn,cap; Object[]array; //判断数组是否满了 while((n=size)>=(cap=(array=queue).length)) //数组扩容 tryGrow(array,cap); try{ //拿到比较器 Comparator<?superE>cmp=comparator; //判断是否有自定义比较器 if(cmp==null) //堆上浮 siftUpComparable(n,e,array); else //使用自定义比较器进行堆上浮 siftUpUsingComparator(n,e,array,cmp); //队列长度+1 size=n+1; //唤醒休眠的出队线程 notEmpty.signal(); }finally{ //释放锁 lock.unlock(); } returntrue; }
可以看出前三个方法内部都是通过 offer(e) 方法实现的。
原文来自:https://www.py.cn
© 版权声明
文章版权归作者所有,未经允许请勿转载。
THE END
暂无评论内容