权重偏左堆：自上而下版本合并的优点？

我正在自学，它要求推理并实现一个偏向权重的左堆。这是我的基本实现：

(* 3.4 (b) *)
functor WeightBiasedLeftistHeap (Element : Ordered) : Heap =
struct
  structure Elem = Element

  datatype Heap = E | T of int * Elem.T * Heap * Heap

  fun size E = 0
    | size (T (s, _, _, _)) = s
  fun makeT (x, a, b) =
    let
      val sizet = size a + size b + 1
    in
      if size a >= size b then T (sizet, x, a, b)
      else T (sizet, x, b, a)
    end

  val empty = E
  fun isEmpty E = true | isEmpty _ = false

  fun merge (h, E) = h
    | merge (E, h) = h
    | merge (h1 as T (_, x, a1, b1), h2 as T (_, y, a2, b2)) =
      if Elem.leq (x, y) then makeT (x, a1, merge (b1, h2))
      else makeT (y, a2, merge (h1, b2))
  fun insert (x, h) = merge (T (1, x, E, E), h)

  fun findMin E = raise Empty
    | findMin (T (_, x, a, b)) = x
  fun deleteMin E = raise Empty
    | deleteMin (T (_, x, a, b)) = merge (a, b)
end

现在，在 3.4 (c) 和 (d) 中，它要求：

现在，merge分两个运作 传递：自上而下的传递，包括 打电话给merge，以及自下而上的传递 包括对助手的调用 功能，makeT。调整merge到 以单一、自上而下的方式进行操作。 自上而下的方式有什么好处 的版本merge有一个懒惰的 环境？在并发的 环境？

我改变了merge通过简单的内联函数makeT，但我没有看到任何好处，所以我认为我还没有掌握这部分练习的精神。我缺少什么？

  fun merge (h, E) = h
    | merge (E, h) = h
    | merge (h1 as T (s1, x, a1, b1), h2 as T (s2, y, a2, b2)) =
      let
        val st = s1 + s2
        val (v, a, b) =
          if Elem.leq (x, y) then (x, a1, merge (b1, h2))
          else (y, a2, merge (h1, b2))
        in
          if size a >= size b then T (st, v, a, b)
          else T (st, v, b, a)
        end

我想我已经找到了关于惰性评估的一点。如果我不使用递归合并来计算大小，则在需要子级之前不需要评估递归调用：

  fun merge (h, E) = h
    | merge (E, h) = h
    | merge (h1 as T (s1, x, a1, b1), h2 as T (s2, y, a2, b2)) =
      let
    val st = s1 + s2
        val (v, ma, mb1, mb2) =
        if Elem.leq (x, y) then (x, a1, b1, h2)
        else (y, a2, h1, b2)
      in
        if size ma >= size mb1 + size mb2
        then T (st, v, ma, merge (mb1, mb2))
        else T (st, v, merge (mb1, mb2), ma)
      end

这就是全部？但我不确定并发性。

我认为您基本上已经了解了惰性求值——如果您每次进行合并时都必须遍历整个数据结构以找出任何内容，那么使用惰性求值并不是很有帮助。 ..

至于并发性，我预计问题是，如果一个线程正在评估合并，另一个线程出现并想要查找某些内容，则至少在第一个线程完成合并之前，它将无法完成任何有用的事情。 （甚至可能需要更长的时间。）