二叉树-堆

• 2019 年 12 月 31 日
• 筆記

二叉树：满二叉树、完全二叉树

满二叉树：叶子节点都在最底层，除了叶子节点，其他节点都有左右两个子节点；

完全二叉树：叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大；

堆

• 完全二叉树
• 堆的每个节点都大于等于（或者小于等于）其子树的中的每个节点
• 每个节点都大于等于其子树的节点，叫大顶堆，即顶点为树中最大值

• 每个节点都小于等于其子树的节点，叫小顶堆，即顶点为树中最小值

堆的插入（最大堆）

• 按照二叉树的顺序，插入新元素
• 新插入的元素，需要与父节点比较，如果大于父节点，则和父节点交换
• 依次与父节点比较，满足则完成，否则继续交换到根
• 时间复杂度为 logN

堆的删除（最大堆）

• 删除都是移除根元素，然后为了继续满足完全二叉树的特性，需要将最后一个元素替换到根元素位置
• 然后，从顶向下，做交换操作，直到满足堆的特性，即父节点为子树的最大值

Java的实现：PriorityQueue

# 父index 找 子index：  左子：2 * index + 1  右子：2 * index + 2  # 子index 找 父 index：  数学运算：(index-1) / 2  位运算：(index-1) >>> 2

插入

删除

扩展

>>>与>>区别？  >>>为无符号右移  无论正负，高位都补0，  >>为右移  正数的话，高位补0  负数的话，高位补1    7 >>> 1  7 >> 1  -7 >>> 1  -7 >> 1