二进制堆
二进制堆是一个具有以下属性的二进制树。
- 二进制堆是一个完整的二进制树，也就是说，除了最后一层之外，所有的层次都被完全填满，而且最后一层的所有键都尽可能的靠左。二进制堆的这一属性使它们适合存储在一个数组中。
- 一个二进制堆要么是最小堆，要么是最大堆。在最小二进制堆中，根部的键必须是二进制堆中所有键的最小值。同样的属性对于二进制树中的所有节点必须是递归的。最大二进制堆与最小二进制堆类似。
二项式堆
二项式堆是一个二项式树的集合，每个二项式树都遵循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) |
欢迎任何形式的转载，但请务必注明出处，尊重他人劳动成果。
转载请注明：文章转载自 有区别网 [http://www.vsdiffer.com]
本文标题：二进位堆、二项堆和斐波那契堆的区别
本文链接：https://www.vsdiffer.com/vs/difference-between-binary-heap-binomial-heap-and-fibonacci-heap.html
免责声明：以上内容仅是站长个人看法、理解、学习笔记、总结和研究收藏。不保证其正确性，因使用而带来的风险与本站无关！如本网站内容冒犯了您的权益，请联系站长，邮箱：，我们核实并会尽快处理。