重量偏向的左派堆:自上而下的合并版本的优势？

Question

我正在自学俄冈崎的纯功能数据结构,现在正在练习3.4,它要求推理并实施一个重量偏向的左派堆.这是我的基本实现:

(* 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

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

Answer 1

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

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