PriorityBlockingQueue源码
2023-08-22 18:14:52 3 举报PriorityBlockingQueue源码
作者其他创作
大纲/内容
66
7
0
1
right<n & c>array[right]
53
x<c ？
61
null
继续while循环
false
插入第二个元素x=61
54
插入第四个元素x=37
parent=(k-1)/2=0e=array[parent]=43x>e ? truebreak 跳出array[k]=x
while k< half
3
5
43
k=2
4
不满足while循环
2
39
数组扩容
加锁，真正数据拷贝
左子节点计算公式
half = 7/2=3
array[k]=x
k=0
小顶堆最小元素出队
parent=(k-1)/2=0e=array[parent]=43x>e？truebreak 跳出array[k]=x
37
48
array[k]=c=43k=child=3
6
扩容是一个极其消耗资源的动作，在真正数据拷贝前，先释放锁让其它线程可以进行出队操作。这里不释放锁，一直持有也没问题，考虑性能优化到极致
表示线程CAS失败，让出CPU
parent=(k-1)/2=0e=array[parent]=43x>e？falsearray[k]=ek=parent
child=k*2+1=1c=array[child]=39right=child+1=2
true
构造器
k=1
parent=(k-1)/2=1e=array[parent]=61x>e？falsearray[k]=ek=parent
插入第一个元素x=43
k=0，x=61，n=7
出队方法
父节点的计算公式
小顶堆实现（上浮）
while不满足array[0] = x;
child=k*2+1=3c=array[child]=43right=child+1=4
出队算法
CAS加锁保证只有一个线程扩容
出队
array[k]=c=39k=child=1
演示小顶端实现
插入第三个元素x=54
k=3
入队方法
array[k] = x;
lock.unlock()
0 条评论
下一页
