inkar-us-i.hatenablog.com

こちらの記事でLeftist Heapの紹介をしましたが、今回はその亜種であるWeight-biased Leftist Heapを紹介します。
このデータ構造はほとんどLeftist Heapと同様ですが、rankのかわりに要素数が左に偏るようになります。すなわち、

  1. 根の部分が常に最小値となる
  2. 全てのノードについて、その左側の子の要素数は、右側の子の要素数以上である

以下が実装になります。ここで、HEAP, ORDEREDは上の記事と同様のものです。

(* Weight-biased leftist heap  *)
module WBLHeap (Elt : ORDERED)
       : HEAP with type elt = Elt.t =
  struct
    type elt = Elt.t
    type t =
      | E
      | T of int * elt * t * t

    let size = function
      | E -> 0
      | T (s, _, _, _) -> s

    let make_t x a b =
      if size a >= size b then T (1 + size a + size b, x, a, b)
      else T (1 + size a + size b, x, b, a)

    let empty () = E

    let is_empty = function
      | E -> true
      | _ -> false

    let rec merge h1 h2 = match h1, h2 with
      | _, E -> h1
      | E, _ -> h2
      | T (_, x1, a1, b1), T (_, x2, a2, b2) ->
         if Elt.lt x1 x2
         then make_t x1 a1 (merge b1 h2)
         else make_t x2 a2 (merge h1 b2)

    let insert x h = merge (T (1, x, E, E)) h

    let find_min = function
      | T (_, x, _, _) -> x
      | E -> raise Empty

    let delete_min = function
      | T (_, _, a, b) -> merge a b
      | E -> raise Empty

    let rec from_list xs =
      let rec iter res xs = match xs with
        | a :: b :: xs -> iter (merge a b :: res) xs
        | a :: [] -> a :: res
        | [] -> res in
      let rec from_list' xs = match iter [] xs with
        | [] -> raise Empty
        | h :: [] -> h
        | xs' -> from_list' xs'
      in from_list' (List.rev_map (fun x -> T (1, x, E, E)) xs)
  end

Purely Functional Data Structures

Purely Functional Data Structures

純粋関数型データ構造

純粋関数型データ構造