二进制堆

二进制堆是一个具有以下属性的二进制树。

  • 二进制堆是一个完整的二进制树,也就是说,除了最后一层之外,所有的层次都被完全填满,而且最后一层的所有键都尽可能的靠左。二进制堆的这一属性使它们适合存储在一个数组中。
  • 一个二进制堆要么是最小堆,要么是最大堆。在最小二进制堆中,根部的键必须是二进制堆中所有键的最小值。同样的属性对于二进制树中的所有节点必须是递归的。最大二进制堆与最小二进制堆类似。

二项式堆

二项式堆是一个二项式树的集合,每个二项式树都遵循Min-Heap属性,并且任何程度的二项式树最多只有一个。

二进制堆和二项式堆的关键区别在于堆的结构方式。在二进制堆中,堆是一棵树,是一棵完整的二进制树。在二进制堆中,堆是一个较小的树的集合(也就是一个树的森林),每个树都是一个二进制树。一棵完整的二叉树可以被构建为容纳任何数量的元素,但某个阶数为N的二叉树的元素数量总是2*N。因此,需要一棵完整的二叉树来支持一个二叉堆,但我们可能需要多棵二叉树来支持一个二叉堆。

斐波那契堆

与二项式堆一样,斐波那契堆也是一个具有最小堆或最大堆属性的树的集合。在斐波那契堆中,树可以有任何形状,甚至所有的树都可以是单节点(这与二项式堆不同,二项式堆中的每棵树都必须是二项式树)。Fibonacci Heap维护一个指向最小值的指针(这就是树的根)。所有的树根都是用一个循环的双链表连接的,所以所有的树根都可以用一个’min’指针来访问。

下表提到了与二进制堆、二项式堆和斐波那契堆相关的各种操作在时间复杂性上的差异(区别)

操作 二进制堆 二项式堆 斐波那契堆
插入 O(log N) O(log N) O(1)
最小查找 O(1) O(log N) O(1)
删除 O(log N) O(log N) O(log N)
递减键 O(log N) O(log N) O(1)
联合 O(N) O(log N) O(1)