ここでは、Haskellで leftist heap を用いたヒープソートを実装してみましょう。leftist heap というのは、 右の部分木に対して要素の追加やマージを優先して行うのですが、 右の木の高さが左より高くなったら、 左の木と交換することでバランスを保つ平衡木のことです。もちろん、 親の要素が子の要素以下というヒープの条件も満たします。また、 ここで言う高さとは、 注目しているノードから右の枝のみをたどって、 葉(leaf)に到達するまでの枝の数のことです。
leftist heap を使うと Haskell でヒープソートが簡単に実装できます。 完全２分木を使ったヒープソート がかなり複雑だったのとは対照的です。
それでは、Haskell による leftist heap を使ったヒープソートの実装を見てみましょう。ここで示すのは、純粋な leftist heap ではなく、あえて平衡木のバランスを崩した実装です。
ここで示したコードの slant 変数を 0 にすればいわゆる普通の leftist heap によるヒープソートになります。しかし、普通の leftist heap では、 左右の木の交換が頻繁に起きます。平衡木とは言っても、 実際には完全２分木のように完全に平衡しているわけではないのですから、 頻繁に交換してまでバランスをとらなくてもよいはずです。 そこで、ある程度バランスが崩れるまで、 左右の木の交換を抑制したのがこのアルゴリズムです。
Haskell では部分木の交換を行わないとしても、 副作用が禁じられているので結局新たに木を作ることになります。ですから、 交換を減らしても速くならないような気がします。しかし、 実際には何故か交換の回数を減らすと速くなります。 理由はよく分かりませんが、 メモリのキャッシュが影響しているのかもしれません。