feature image

2020年4月27日 | ブログ記事

Randomized Meldable Heap

新歓ブログリレー2020 50日目の記事です

Heap とは、全順序集合の多重部分集合に対して挿入や最小値の取得、削除が可能なデータ構造です。C++ では std::priority_queue が該当します。

特に Meldable Heap は meld、すなわち 2 つの Heap を融合させて 1 つの Heap にする操作を提供する Heap を指します。Meldable Heap には様々なバリエーションが存在し、本稿ではその 1 つである Randomized Meldable Heap と呼ばれるデータ構造を紹介します。

構造

全てのノードが丁度 1 つの要素と対応する、自由な形の二分木を管理します。

この二分木は heap property を維持します。すなわち全てのノードのついて、その要素は子ノードの要素以下になるようにします。この条件が満たされるとき、根には常に最小の要素が対応することが分かります。

meld

2 つの二分木 x, y を、heap property を維持したまま 1 つの木に統合します。それぞれの木の根を比較し、一般性を失わず x の方が小さかったとします。x の根が統合された木の根となり、x の子のうち一方を等確率でランダムに選び、それと y を meld したものを新しい子とします。x, y のいずれか一方が空になったときもう一方が meld 結果となり、再帰が終了します。

このアルゴリズムが heap property を維持することを確認します。仮定より y は x 以上であり、したがって y の全てのノードは x 以上です。よって子と meld した後もその根は x 以上となるので成立します。

最も興味深いのは、このアルゴリズムの時間計算量が木の形状に関わらず O(log|x|+log|y|) となることです。1 以上の定数 c が存在して、時間計算量が  c(log(|x|+1)+log(|y|+1)) 以下となることを数学的帰納法を用いて証明します。

|x|=0 の場合、直ちにアルゴリズムが終了することから条件は満たされます。

|x|≠0 のとき、x の左の子を l、右の子を r とすると、以下のようになります。





insert

単一のノードからなる木を作成し、meld します。

pop

根を削除し、左右の子を meld します。

その他

Meldable Heap には他に Leftist Heap、Skew Heap、Pairing Heap、Fibonacci Heap など多種存在します。どのアルゴリズムも面白く、おすすめです。

明日の担当者は @bonc256 です。

noshi91 icon
この記事を書いた人
noshi91

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2020年5月15日
【新歓ゲーム制作特集 第2弾】Inverse製作秘話
Saltn icon Saltn
2020年5月19日
【新歓ゲーム制作特集 第6弾】個人でゲームを作る話
Facish icon Facish
2020年5月1日
爆☆誕 traQ-S【新歓ブログリレー2020 54日目】
spa icon spa
2020年4月12日
Growl Bassの研究【新歓ブログリレー2020 35日目】
fomalhaut icon fomalhaut
2020年4月6日
はじめてのドット絵
xxpoxx icon xxpoxx
2020年4月3日
猫でもわかる(諸説)ハードサーフェスモデリング
isak icon isak
記事一覧 タグ一覧 Google アナリティクスについて