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年4月12日
Growl Bassの研究【新歓ブログリレー2020 35日目】
fomalhaut icon fomalhaut
2020年4月6日
はじめてのドット絵
xxpoxx icon xxpoxx
2020年4月3日
猫でもわかる(諸説)ハードサーフェスモデリング
isak icon isak
2020年3月19日
Ubuntuの環境構築備忘録【新歓ブログリレー2020 11日目】
manyato icon manyato
記事一覧 タグ一覧 Google アナリティクスについて