2021-12-02 二叉堆

完全二叉树:除了最后一行,其他行都满的二叉树,而且最后一行所有叶子节点都从左向右开始排序。

二叉堆:完全二叉树的基础上,加以一定的条件约束的一种特殊的二叉树。根据约束条件的不同,二叉堆又可以分为两个类型:

大顶堆和小顶堆。

大顶堆(最大堆):父结点的键值总是大于或等于任何一个子节点的键值;

小顶堆(最小堆):父结点的键值总是小于或等于任何一个子节点的键值。

一 . 例子

在java.util.concurrent包下

PriorityBlockingQueue优先级阻塞队里 底层实现

核心思想:

  // 位运算 右移1位 找到父节点 

    int parent = (k -1) >>>1;

  // 与父节点进行比较 决定上浮或者下沉

源码截图:

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容