ここでは、Haskellで skew heap を用いたヒープソートを実装してみましょう。skew heap は leftist heap のような平衡木から平衡を保つための仕組みを取り除いてしまったヒープです。 ですから当然平衡にはなりません。生成されるヒープは、 バランスの崩れた片方の部分木が非常に大きい木になることもあります。
しかし不思議なことに、 バランスの崩れた木が生成されることで生じたコストは、 ヒープソートを実行するその他の処理の時間的余裕に吸収されてしまい、 ヒープソート全体では \(O(n\log n)\) の計算量になるんだそうです。
このカラクリ、 私はよく分かっていないのでこれ以上詳しい説明はできません。ごめんなさい。 それでは、skew heap によるヒープソートの実装を見てみましょう。 leftist heap よりもさらに簡単です。