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の要素数をマージ) となる。