「複数のheapqをマージしたいけどO(NlogN)はちょっと・・・」
そんなあなたに朗報です！そのマージはSkew Heapを使えばO(logN)でできます！！！！（ならし計算量）

Skew Heap ってなに？

ご存知なら読み飛ばして結構です。

併合可能優先度付きキュー(meldable priority queue)の実装の１つです。有名なものだとleftist treeというのもあります。今回実装する(min)Skew Heapはleftist treeの簡易版です。

原則、以下3つの操作ができます。ここで言うヒープの優先度不等式というのは、「親の優先度が子より高くなっているか」みたいなのを指しています。

• pop 最も優先度の高いデータを取り出す O(logN)
• push ヒープの優先度不等式を満たす形でデータを加える O(logN)
• meld ヒープの優先度不等式を満たす形で2つのヒープを合体させる O(logN)

次項の実装例では値が小さいほど優先度が高いmin Skew Heapを書いています。

実装例を見てみよう！

class SkewHeap:
  def __init__(self, init_val = None):
    self.val = init_val
    self.left = None
    self.right = None
    self.root = None
  def heapmeld(self, h1, h2):
    if h1 == None: return h2
    if h2 == None: return h1
    if h1.val == None: return h2
    if h2.val == None: return h1
    if h1.val > h2.val:
      h1.val, h1.left, h1.right, h2.val, h2.left, h2.right = h2.val, h2.left, h2.right, h1.val, h1.left, h1.right
    h1.right = self.heapmeld(h2, h1.right)
    h1.left, h1.right = h1.right, h1.left
    return h1
  def heappop(self):
    res = self.root.val
    self.root = self.heapmeld(self.root.left, self.root.right)
    return res
  def heappush(self, x):
    h = SkewHeap(x)
    self.root = self.heapmeld(self.root, h)
  def heaptop(self):
    if self.root == None:
      return None
    return self.root.val

どういう実装なの？

前項のコードを見てどう思いましたか？推敲できそうだったら教えてくださいね
それでは順を追ってコードの上の方から説明していきますね。

init関数

init関数では、インスタンス生成時の初期化をしています。
変数名の説明は要りますか？要りませんよね。

heapmeld関数

2つのSkew Heapを合体させます。ここがSkew Heapの最も大事な部分です。
引数のh1, h2はSkew Heapクラスのインスタンスになります。
最初の4連続のif文は、ヒープと無を合体させようとした際のエラー回避です。
その次のif文はこんな感じですが・・・

if h1.val > h2.val:
  h1.val, h1.left, h1.right, h2.val, h2.left, h2.right = h2.val, h2.left, h2.right, h1.val, h1.left, h1.right

基本的に第一引数のヒープが第二引数のヒープより値が小さく（優先度が大きく）なるようにしています。if文内の大変長い代入文は第一引数のヒープと第二引数のヒープを入れ替えようとしています。

その次の文ですね。

h1.right = self.heapmeld(h2, h1.right)

第二引数と第一引数のヒープ（優先度が大きい方）の右側部分木でまた合体をさせます。引数の順番は(h1.right, h2)でも変わりません。合体されたヒープは第一引数のヒープの右側部分木になります。
再帰的な呼び出しなので、これは片方のヒープが無になるまで続きます。片方が無になると、そこへもう片方のヒープがくっついてゆくという仕組みです。

最後の文です。

h1.left, h1.right = h1.right, h1.left
return h1

第一引数のヒープの右側部分木に第二引数のヒープが合体しました。
最後にこのヒープの右と左を入れ替えて、出力です。

heappop関数

ヒープの根の値を出力します。その上で根の左側部分木と右側部分木をheapmeldで合体させると、先程の根を取り除いた新しいヒープが現れます。

heappush関数

pushする値をそのままSkew Heapとして扱います。頂点が1つだとしてもヒープはヒープなんです。こうすると、pushしたいヒープとこれをheapmeldで合体させることで実装完了です。

heaptop関数

ヒープの根の値を返します。存在しないならNoneを返します。

heapmeldはなんで左部分木と右部分木を入れ替えるの？

例を見てみるのが一番わかりやすいと思います。

この2つのヒープを合成してみましょうか。左側の４頂点のヒープをh1、右側のヒープをh2としておきます。左右の入れ替えなしでheapmeld(h1, h2)をやってみましょう。

何だか右に偏っていますね。気のせいでしょうか。

賑やかそうなヒープがやってきました。これも合成しましょうか。

何だか右がもの凄く大きくありませんか？？
このままだとheapmeldは容易くO(N)になってしまいます。

このような偏りをある程度解消するために右部分木と左部分木の入れ替えを行います。こうすることでヒープは平衡二分探索木に近い形を取れるようになり、meldはO(logN)で機能します！！！！！

どんな記事にも終わりはある

ここまでSkew Heapの実装について書いてきましたが、いかがでしたか。書けそうですか。

今回実装したのはmin Skew Heapですが、maxとして扱いたい場合はmeldの不等号を反転させるか、ヒープに入れる値の符号を反転させるといいと思います。

コードがおかしいとか（一応確認はしておきましたけど）、話がおかしい、みたいな事が御座いましたらtwitterでも何でもいいので教えてくださると嬉しいです。

参考文献（Web）

ジョージ・メイソン大学のコンピュータサイエンスの授業資料
https://cs.gmu.edu/~rcarver/cs310/MoreHeaps_Splay_Skip.pdf
Lilliput Steps - Skew Heap
http://kagamiz.hatenablog.com/entry/2013/06/26/210256