堆的特性

堆

堆的属性

堆就是用数组实现的完全二叉树, 它没有使用父指针或者子指针.

堆分为两种, 最大堆/大顶堆和最小堆/小顶堆, 两者的差别在于节点的排序方式.

在最大堆中, 父节点的值比每一个子节点的值都要大; 在最小堆中, 父节点的值比每一个子节点的值都要小. 这就是堆属性, 这个属性对堆中的每一个节点都成立, 堆属性决定了树中节点的位置.

根据这一属性, 最大堆总是将其中的最大值存放在树的根节点, 最小堆根节点中的元素总是树中的最小值. 因此堆常常被当做优先队列使用, 因为可以快速地访问到最重要的元素.

但注意, 堆的根节点中存放的是最大或者最小元素, 其他节点的排序顺序是未知的. 在一个最大堆中, 最大的那一个元素总是位于根节点, 即第一个元素, 但是最小的元素则未必是最后一个元素, 例如上图中的最大堆对应的数组为:

并不是完全顺序的.

最大堆/最小堆用公式表示为:

• 最大堆: $\text{arr}[i] \ge \text{arr}[2i+1], \quad \text{arr}[i] \ge \text{arr}[2i+2]$
• 最小堆: $\text{arr}[i] \le \text{arr}[2i+1], \quad \text{arr}[i] \le \text{arr}[2i+2]$

堆和树的区别

• 节点的顺序: 二叉搜索树的左子节点必须比父节点小, 右子节点必须必比父节点大. 在最大堆中, 父结点必须不小于两个子节点, 但两个子节点并无大小约束

• 内存占用: 普通树占用的内存空间比它们存储的数据要多, 因为还需要存储左右节点的指针, 甚至父节点的指针. 堆仅仅使用一个数据来存储数组, 且不使用指针

• 平衡性: 二叉搜索树必须是平衡的情况下, 其大部分操作的复杂度才能达到$O(\log n)$. 但是在堆中实际上不需要整棵树都是有序的, 我们只需要满足堆属性即可, 所以是一个完全二叉树, 平衡不是问题, 可以保证$O(\log n)$的性能
• 用途: 在二叉树中搜索会很快, 但是在堆中搜索会很慢. 在堆中搜索不是第一优先级, 因为使用堆的目的是将最值的节点放在最前面, 从而快速的进行相关插入, 删除操作

堆的索引性质

仅仅依赖数组的下标, 无需额外的指针, 就可以维护一棵二叉树. 在堆中, 父节点与子节点的下标关系为, 对于下标$i$对应的节点:

$\text{parnet}(i) = \lfloor (i - 1) / 2 \rfloor$ $\text{left}(i) = 2i + 1$ $\text{right}(i) = 2i + 2$

堆的高度

树/堆的高度指的是从树的根节点到最低的叶节点所需要的步数, 一个高度为$h$的堆有$h+1$层, 根节点单算一层.

如果一个堆有$n$个节点, 那么它的高度是$h = \lfloor \log_2n \rfloor$. 所以如下图所示的有15个节点的堆, 其高度为$\lfloor \log_215 \rfloor = \lfloor 3.91 \rfloor = 3$.

如果最下面的一层已经填满, 则最下面一层包含$2^h$个节点, 前面所有层包含$2^h - 1$个节点, 因此叶子节点对应的索引在$\lfloor n / 2 \rfloor$与$n - 1$之间.

堆的操作

有两个原始操作用于保证插入或删除节点以后堆是一个有效的最大堆或者最小堆:

• 上浮 shiftUp(): 如果一个节点比它的父节点大(最大堆)或者小(最小堆), 那么需要将它同父节点交换位置, 这个节点在数组的位置上升

• 下沉 shiftDown(): 如果一个节点比它的子节点小(最大堆)或者大(最小堆), 那么需要将它向下移动. 这个操作也称作堆化(heapify)

上浮或者下沉是一个递归的过程, 所以它的时间复杂度是$O(\log n)$.

还有一些基础操作:

• 插入 insert(value): 在堆的尾部添加一个新的元素, 然后使用shiftUp()来修复堆

• 弹出 remove()/pop(): 移除根节点并返回最大值(最大堆)或者最小值(最小堆), 为了将这个节点删除后的空位填补上, 需要将最后一个元素移到根节点的位置, 然后使用shiftDown()方法来修复堆

因为都需要从根节点到叶子节点, 因此这两个操作的时间复杂度都是$O(\log n)$.

在此基础上, 常见的一些堆操作还有:

• 排序 sort(): 由于堆就是一个数组, 我们可以使用它独特的属性将数组从低到高排序, 时间复杂度为$O(n \log n)$
• 生成堆 buildHeap(array): 通过反复调用insert(value)方法将一个无需数组转换成一个堆, 时间复杂度为$O(n)$
• 搜索 search(value): 堆不是为快速搜索而建立的, 因而做不到$O(1)$和$O(\log n)$. 只能一一对比, 时间复杂度为$O(n)$

参考资料

• 数据结构: 堆(Heap)