このページは、優先度付きキュー(priority queue)の実装に使われる ヒープ の１つである pairing heap を紹介するページです。キューとは、 要素を一時的にためておくバッファのことです。そして優先度付きキューとは、 優先度の高い順に要素を取り出せるキューのことです。またヒープとは、 最小値や最大値を効率的に取り出すことが出来る木構造のデータ構造です。
pairing heap を使うと ヒープを安定にすることが出来ます。つまり、pairing heap を使ったヒープソートは安定ソートになるということです。 この特徴を優先度付きキューに応用すると、 優先度付きキューを安定にすることが出来ます。 通常のヒープは安定ではありませんので、 それを使った優先度付きキューは 同じ優先度の要素をどんな順番で取り出せるのかは予測できません。 ところが、pairing heap を使った優先度付きキューは、 同じ優先度の要素をキューに入れた順に取り出すことができます。ようするに、 同じ優先度の要素に関して FIFO にすることが出来るのです。
それでは、早速 pairing heap の java による実装を見てみましょう。 まずは pairing heap の考え方を理解するために、 再帰を用いた実装を示します。
実装には多分木を使っています。 多分木というと難しいというイメージですが、 pairing heap はとても簡単です。でも簡単だけど、 こんなので本当にヒープソートが \(O(n\log n)\) の計算量になるのか心配ですよね？ 私も pairing heap を知ったときにそう思いました。しかし、ご安心ください。 確かに pairing heap は unify() が \(O(\log n)\) に収まらず、 \(O(n)\) になる瞬間もありますが、 そのコストは、他の処理の時間的余裕に吸収されていまい、 ヒープソート全体では \(O(n\log n)\) の計算量になるんだそうです。 こういうのを amortized complexity と言うそうです。
さて、 再帰を基本とする関数型言語の場合は上記のような実装でもよいのですが、 java のような手続き型言語の場合、 不用意に再帰を使うとスタックオーバーフローを起こしてしまいます。 そんなわけで、再帰をループで書き換えてみましょう。以下のようになります。 効率化のため線形リストを自前で実装しています。
これでずいぶんと効率的になりましたが、まだ無駄があります。push() や offer()、unify() で new が使われています。new は非常に重たい処理なので、 頻繁に呼び出される push() や offer() で使うのは好ましくありません。 そこで、少し工夫して push() や offer()、unify() から new を取り除いてみましょう。以下のようになります。
ところで、この実装を注意して見ると分かりますが、pairing heap では、 merge や insert といった操作でループを使っていません。 もちろん再帰も使っていません。ということは計算量が \(O(1)\) ということです。すごいですよね。ただ、amortized complexity 的に見ると \(O(1)\) であるとは証明はされておらず、\(O(\log n)\) という扱いのようです。