在Binomial Heap上正确的功能实现 [英] Correct functional implementation on Binomial Heap

问题描述

我在二项式堆 = A3P5ROKL5A1OLE& pf_rd_s = center-4& pf_rd_r = 14JNZQW0XAQ5PY6VA6VX& pf_rd_t = 101& pf_rd_p = 430173587& pf_rd_i = 468294rel =nofollow>纯功能数据结构。
> insTree 函数的实现让我非常困惑。这里是一组代码

 数据类型Tree = int * Elem.T的节点*树列表
 $ b $如果Elem.leq（x1，x2）则节点（r + 1，x1，t2）为节点（r，x1，c1），t2为节点（_，x2，c2））= 
。 :: c1）
 else节点（r + 1，x2，t1 :: c2）
 
有趣的等级（Node（r，x，c））= r 
 
 fun insTree（t，[]）= [t] 
 | insTree（t，ts as t':: ts'）= 
如果等级t < （t，t'），ts'）
  

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

在中if rank t <等级t'然后t :: ts else insTree（link（t，t'），ts'），

1. 如果t的等级比t的等级低，那么就把t放入堆中，毫无疑问的是
   
2. else
em>有两种情况：平等和更大。

3. 对于 equal ，是的，我们可以链接两棵树（我们只链接两棵具有相同等级的树），然后尝试插入新的链接树堆，没有问题。


4. ，但即使是更大的情况也会相同，为什么？即使排名为t > rank t'，我们仍将它们链接在一起？

---

编辑

我认为将二叉树插入二项堆的过程应该如下所示：

1. 我们得到树t和堆


2. 在堆中（实际上是一个列表），我们比较树t的等级树在堆中


3. 我们找到一个缺失的等级（堆中递增的顺序），它与t的等级相匹配，我们将t放在该槽中
   
4. 我们在堆中找到一个与t相同的树，然后我们链接两棵树并处理一个 rank + 1 新树，然后再次插入新树到堆中。

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

  fun insTree（t，[]）= [t] 
 | insTree（t，ts as t':: ts'）= 
如果等级t <然后insTree（link（t，t'），ts'）
 else t'：:( insTree（t，ts'）'然后t：ts 
否则如果rank t = rank t' ））
  

解决方案

insTree是不可见的帮助函数给用户。用户调用插入，然后调用insTree级别为0的树和增加级别树的列表。 insTree具有不变量，即t的秩是<=列表中第一棵树的秩。因此，如果它不是<，那么它必须是=。

如果insTree是通用公共功能，而不是专用私人功能，那么它将不得不处理失踪案件。

I am reading Binomial Heap in Purely Functional Data Structures.

The implementation of insTree function confused me quite much. Here are the set of codes

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')

My confusion lies on the bit in insTree that why it does not consider the situation of rank t > rank t'?

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

1. if t's rank is less than t''s rank, then put the t into the heap, no question asked
2. the else has two cases: equal and bigger.
3. For equal, yes, we can link two trees (we link only two trees with the same rank), and then try to insert the new linked tree into the heap, no question asked.
4. but even the bigger case would have the same as equal, why? Even if rank t > rank t', we still link them?

---

Edit

I thought the process of inserting a binomial tree into a binomial heap should be like this:

1. We get the tree t and the heap
2. In the heap (actually a list), we compare rank of the tree t with every tree in the heap
3. We find a missing rank (increasing order in the heap) which matches the rank of t, we put t at that slot
4. We find a tree in the heap with same rank as t, then we link two trees and process a rank+1 new tree and try again insert the new tree to the heap.

So, I think the correct fun insTree could be like this:

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'))

解决方案

insTree is a helper function that is not visible to the user. The user calls insert, which in turn calls insTree with a tree of rank 0, and a list of trees of increasing rank. insTree has an invariant that the rank of t is <= the rank of the first tree in the list. So if it's not <, then it must be =.

You're right that if insTree was a general-purpose public function, rather than a special-purpose private function, then it would have to deal with the missing case.

这篇关于在Binomial Heap上正确的功能实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！