数据结构

TODO 列表 #

高级数据结构 TODO 列表,有空再详细了解下。

二项树 #

二项树满足一下条件:

  • 度数为 0 的二项树只包含一个结点。
  • 度数为 K 的二项树有一个根节点,根节点下有 K 的子女,每个子女分别是度数 k-1, k-2, k-3, …, 2, 1, 0 的二项树的根。

二项堆(Binomial Heap) #

二项堆是满足以下二项树的集合:

  • 每棵二项树都满足最小堆性质,即子结点大于等于其父结点的值。
  • 不能有两棵以上的二项树有相同的度数(包括 0),换句话说,具有度数 K 的二项树只有 0 个或 1 个。

图为一个含 13 个结点的二项堆。

二项队列 #