二进位堆、二项堆和斐波那契堆的区别

二进制堆

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

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

二项式堆

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

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

斐波那契堆

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

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