2

我正在阅读Binomial HeapPurely Functional Data Structures。

函数的实现insTree让我很困惑。这是一组代码

datatype Tree = Node of int * Elem.T * Tree list

fun link (t1 as Node (r, x1, c1), t2 as Node (_, x2, c2)) = 
  if Elem.leq (x1, x2) then Node (r+1, x1, t2::c1)
  else Node (r+1, x2, t1::c2)

fun rank (Node (r, x, c)) = r

fun insTree (t, []) = [t]
  | insTree (t, ts as t' :: ts') =
      if rank t < rank t' then t::ts else insTree (link (t, t'), ts')

我的困惑在于insTree为什么它不考虑 rank t > rank t' 的情况？

在if rank t < rank t' then t::ts else insTree (link (t, t'), ts'),

  1. 如果 t 的排名小于t 的排名，则将 t 放入堆中，不问任何问题
  2. else有两种情况：等于和更大。
  3. 对于equal，是的，我们可以链接两棵树（我们只链接两个具有相同等级的树），然后尝试将新链接的树插入堆中，没有问题。
  4. 但即使是更大的情况也会有相同的平等，为什么？即使 rank t > rank t'，我们仍然链接它们吗？

编辑

我认为的过程inserting a binomial tree into a binomial heap应该是这样的：

  1. 我们得到树 t 和堆
  2. 在堆（实际上是一个列表）中，我们将树 t 的排名与堆中的每棵树进行比较
  3. 我们找到一个与 t 的等级相匹配的缺失等级（堆中的递增顺序），我们将 t 放在那个位置
  4. 我们在堆中找到一棵与 t 具有相同等级的树，然后我们链接两棵树并处理一棵rank+1新树并再次尝试将新树插入堆中。

所以，我认为正确的fun insTree可能是这样的：

fun insTree (t, []) = [t]
      | insTree (t, ts as t' :: ts') =
          if rank t < rank t' then t::ts 
          else if rank t = rank t' then insTree (link (t, t'), ts')
          else t'::(insTree (t, ts'))
4

2 回答 2

1

insTree 是一个对用户不可见的辅助函数。用户调用 insert，后者又调用 insTree，其中有一棵等级为 0 的树，以及一列等级递增的树。insTree 有一个不变量，即 t 的等级 <= 列表中第一棵树的等级。所以如果不是<，那么它一定是=。

你是对的，如果 insTree 是一个通用的公共函数，而不是一个专用的私有函数，那么它必须处理丢失的情况。

于 2013-10-31T19:07:19.567 回答
0

这背后的一个重要细节是二项式堆不是任何恰好有 k 个孩子的树。这是一棵被严格定义为的树

0阶二叉树是单节点，n阶二叉树是单节点，0、1、2、...、n-1阶二叉树为子节点。

这个答案，解释了为什么构造二项式堆所需的插入函数不管理这些情况（理论上它们不会发生）。也许您提出的案例对合并操作有意义（但底层实现应该不同）。

于 2013-10-31T12:13:08.673 回答