java源码-PriorityBlockingQueue
开篇 PriorityBlockingQueue是带优先级的无界阻塞队列,每次出队都返回优先级最高的元素是二叉树最小堆的实现。 使用数组存储的时候i结点的父结点下标就为(i–1)/2。它的左右子结点下标分别为2*i+1和2*i+2 堆实际上是一棵完全二叉树,其任何一非叶节点满足性质: Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2],即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。 堆分为大顶堆和小顶堆,满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆,满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的,小顶堆的堆顶的关键字是所有关键字中最小的,PriorityBlockingQueue是采用小顶堆实现的。 类图 PriorityBl...