data-structures - 二项式堆上的正确功能实现

Question

我正在阅读 Binomial Heap在 Purely 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 有两种情况:equal 和bigger。
3. 对于equal，是的，我们可以链接两棵树(我们只链接两棵排名相同的树)，然后尝试将新链接的树插入堆中，不问任何问题。
4. 但即使是更大的情况也会有相同的情况，为什么？即使排名 t > 排名 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'))

Answer 1

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

你是对的，如果 insTree 是一个通用的公共(public)函数，而不是一个特殊用途的私有(private)函数，那么它就必须处理缺失的情况。