ここでは、 Haskellで pairing heap を用いたヒープソートを実装してみましょう。 java による実装をお望みの方は こちらへ どうぞ。さて、またヒープかよ、 お前はどんだけヒープが好きなんだと思われるかもしれませんが、 私なんか序の口です。今まで紹介したヒープ以外にも、 ２項ヒープやらフィボナッチヒープやらヒープマニアを名乗りたかったら極めねばならないヒープは星の数です(^^;
今まで紹介して来た 完全２分木ヒープ、 leftist heap、 skew heap は、 どれも２分木でした。今回紹介する pairing heap は多分木です。 私は多分木というと難しいという印象を持っていたのですが、 pairing heap はそのイメージをくつがえすほど簡単です。 まずは実装を見てみましょう。 Haskell による pairing heap を用いたヒープソートは以下のようになります。
どうでしょう。非常に美しく簡単と感じませんか？ ヒープソートというより ボトムアップ マージソート に近い印象です。 しかし、美しいけどこんなんで本当に \(O(n\log n)\) の計算量になるの？ と心配になりますよね。 私も pairing heap を知ったときにはそう思いました。 ところが、このアルゴリズムも skew heap と同じで、 unify が \(O(\log n)\) に収まらず、\(O(n)\) になる瞬間もありますが、 そのコストは他の処理の時間的余裕に吸収されてしまい、 ヒープソート全体では計算量が \(O(n\log n)\) になるんだそうです。 こういうのを amortized complexity と言うそうです。
ところで皆さん、 ヒープソートと言ったら不安定なソートの代表と思っていませんか？ 私は思ってました。ところが、pairing heap を少し変形してやると、 何とヒープソートを安定ソートにすることができるのです。 私が pairing heap に感じていた美しさの原因はこのあたりにあると思います。 それでは、具体的に見てみましょう。 安定化 pairing heap によるヒープソートは以下のようになります。
コムソート のときのように Haskell のキューを使うこともできたのですが、 コードが美しくない上にメモリも食うし速度も遅いので、 リストで実装してみました。
ヒープソートを安定に出来たところで何がうれしい？ この実装だと木を生成しているのだから、 マージソートと同じでメモリの節約にはなってないじゃないか、 と思われるかもしれません。しかし、１つ面白い応用分野があります。 優先度付きキュー(priority queue)です。完全２分木や leftist heap、 skew heap を使った優先度付きキューは、 異なる優先度の要素に関しては優先度順に取り出せますが、 同じ優先度の要素に関してはどんな順序で取り出せるのか分かりません。 これらのヒープが安定ではないからです。 しかし、安定化 pairing heap を使うと、 同じ優先度の要素をキューに入れた順に取り出すことができます。 つまり同じ優先度の要素に関しては FIFO になるわけですね。 そのような応用を視野に入れた実装は以下のようになります。
また、この実装を注意して見ると分かりますが、pairing heap では、 merge や insert といった操作で再帰を使っていません。 もちろんループも使っていません。ということは計算量が \(O(1)\) ということです。すごいですよね。 ただ、amortized complexity 的に見ると \(O(1)\) であるとは証明はされておらず、\(O(\log n)\) という扱いのようです。