完全二叉树:除了最后一行,其他行都满的二叉树,而且最后一行所有叶子节点都从左向右开始排序。
二叉堆:完全二叉树的基础上,加以一定的条件约束的一种特殊的二叉树。根据约束条件的不同,二叉堆又可以分为两个类型:
大顶堆和小顶堆。
大顶堆(最大堆):父结点的键值总是大于或等于任何一个子节点的键值;
小顶堆(最小堆):父结点的键值总是小于或等于任何一个子节点的键值。
一 . 例子
在java.util.concurrent包下
PriorityBlockingQueue优先级阻塞队里 底层实现
核心思想:
// 位运算 右移1位 找到父节点
int parent = (k -1) >>>1;
// 与父节点进行比较 决定上浮或者下沉
源码截图: