西宁市网站建设_网站建设公司_过渡效果_seo优化

树与图的数据结构详解

1. 堆的不同类型

1.1 二项堆

二项堆是一种有趣的堆变体，它由一组不同阶的二项树组成。
-二项树的构建：0 阶二项树是一个单节点。可以用两个 n - 1 阶二项树构建 n 阶二项树，将其中一个作为另一个根节点的最左子节点。
-确定二项堆中的二项树：要确定二项堆中应包含多少二项树以及它们应包含多少节点，需要将节点数转换为二进制表示。例如，创建一个有 13 个元素的二项堆，13 的二进制表示为 1101（即 (1\times2^0 + 0\times2^1 + 1\times2^2 + 1\times2^3) ），取置位的零基位置（0、2、3），这些位置表示应配置的二项树的阶。
-二项堆的性质：二项堆中同一阶的二项树不能超过一个，且每个二项树必须保持最小堆性质。
-代码实现：使用 Hippie 库支持二项堆，只需修改创建MultiHeap类新实例的行：

MultiHeap<int> heap = HeapFactory.NewBinomialHeap<int>();

之后的元素插入或移除操作与二叉堆相同。

1.2 斐波那契堆

斐波那契堆在某些方面与二项堆相似，但更灵活。
-特点：由多棵树组成，对每棵树