Leftist Heap

Algorithm

Leftist Heapはヒープに加えて以下の制約が加わったLeftist Treeという構造を持つ。

  • rank(left child) >= rank(right child)

rankとはright spineの長さ（右にだけ降りていったときの最後の接点までの長さ）のことである。
Leftist Treeは要素数nならば

  • rank <= lg(節点数 + 1)

という性質を持つ。各計算に置けるオーダーは

  • insert: O(log n)
  • delete_min: O(log n)
  • find_min: O(1)
  • merge: O(log n) (O(log(n1) + log(n2)): n1とn2の要素数をマージ)

となる。