きくらげ観察日記

好きなことを、適当に。

Leftist Heapの性質

Leftist Heapは、純粋関数型的にヒープを操作するために用いられるデータ構造です。

Leftist Heapは要素が左に偏っている二分木として実装されます。
データ構造自体は以下のように単純に構成できます。

type 'a heap =
  | E
  | T of 'a * 'a heap * 'a heap

ただし、このデータ構造は以下のような制約を持ちます。

let rank = function
  | E -> 0
  | T (_, _, r) -> 1 + rank r

このような関数rankを定義したとき、ツリーのどのノードT(x, l, r)に対しても、

rank l >= rank r ... (1)

が成り立っていなければなりません。

ちなみに、上の性質を満たしているLeftist Heap tでは、以下の不等式が成り立ちます。

rank t <= log(size t + 1) ... (2)

ただし、size t はtの要素数を表します。

証明:
t = E のとき、

rank t = 0 <= 0 = log(size t + 1)

なので(2)が成立。

l, r がともに(2)を満たしていると仮定して、t = T(x, l, r) のとき、
tについて(2)が成り立たないと仮定すると、rankは整数なので、

rank t >= log(size t + 1) + 1

よって、

rank r = rank t - 1
  >= log(size t + 1)

ところで、仮定よりrは(2)を満たすので、

log(size t + 1) <= rank r <= log(size r + 1)
∴ log(size t + 1) <= log(size r + 1)

logは単調増加なので、

size t <= size r

ところで、明らかに

size r < size t

であるため、矛盾。
したがって、tは(2)を満たす。

以上より、全てのleftist heap tは(2)を満たす ■


この不等式(2)が成り立つことによって、2つのヒープをマージする時に右へ右へと辿っていけばO(logn)でマージを完了させることができます。
長くなってしまったので、具体的な実装はまた今度。