二分ヒープについて

二分ヒープを書きました

二分ヒープ is 何

平たく言えば std::priority_queue みたいなやつ

次の操作がいい感じの計算量でできる

• top()
  • 最大値を取得する
  • $O(1)$
• pop()
  • 最大値を削除する
  • $O(\log N)$
• push(value)
  • 値を追加する
  • $O(\log N)$

構造

二分木を持つ．各ノード（葉以外も）が値を持っていて，セグ木と同じ要領で 1-indexed である．

ヒープは，次の条件をつねに満たす．

• あるノードの親のもつ値は，子のもつ値以上である．

これを満たすようにクエリに対応する．なお，ノードの追加自体は，ヒープを持っている可変長配列に push_back するだけでできる．これで，任意のサイズのヒープを単純なかたちで作れる．

top

根のノードを参照すればよい．おわり．

pop

根のノードを削除して，一番 index の大きいノードを根の位置にもってくる．

ヒープ条件を満たすように，持ってきたノードを根からぐんぐん下に swap して持っていくとよい．

$O(\log N)$ でできる．

push

ヒープを持つ配列に push_back して，一番下に持ってくる．ヒープ条件を満たすまで上に swap していけばよい．最悪計算量はもちろん $O(\log N)$ だが，平均計算量は $O(1)$ らしい．まあお気持ちはわかるが証明は思いついてない．

$O(1)$ はあくまで平均計算量で，償却はされないことに注意．

進化

これだけだと std::priority_queue と同じなので，嬉しさがない． そこで，次のようにインターフェースを書き換えることを考える．

• top()
  • key が最大となる要素と，その番号を返す．
  • $O(1)$
• pop()
  • key が最大となる要素を削除する．
  • $O(\log N)$
• push(id, key)
  • (id, key) の組を追加する．
  • $O(\log N)$
• prioritize(id, key)
  • id について，key の値を更新する．
  • $O(\log N)$

こうすると，ダイクストラをするときに queue が小さくなって，嬉しい（push が prioritize に書き換えられて，場合分けが一個減る）

これは，id としてありうる値を index にもてる配列を用意して，A[i] = id が i であるノードのポインタ のようにしてやるとよい．（なお，今回の二分木は配列上に表現できるから，その index を持ってあげれば十分）

prioritize(id, key) が呼ばれたら，この配列を利用してノードの値を書き換え，上か下に適当に swap してやると，$O(\log N)$ でヒープの条件を満たすようにできる．

ともあれ，こうするとダイクストラで定数倍を落とせる．うれしい．

つづき

Fibonacci Heap を使うともっと計算量が落ちます．今度実装してまたここにあげます．