えびちゃんの日記

えびちゃん(競プロ)の日記です。

優先度変更可能なヒープについて

Fibonacci ヒープを使うと優先度をならし定数時間で変更することが可能ですよー,という話を 書きました

どうやら,Java だと,そういうのがうれしいらしいです?

しかし,Fibonacci ヒープはポインタをがしがし操作しなきゃいけなくてたいへんなので,あまり書きたいものではないですね.

ところで,上のリンク先の最後の方にちょっとだけ,\(O(\log n)\) time で優先度を変更できる二分ヒープと書きました.軽めのライブラリを用意したいならそっちの方が有用な気がしたので書いておきます.

これは,今朝起きてすぐおふとんで思いついただけのやつです.

二分ヒープについて

二分ヒープを知らない人は調べておくといいかもしれません?

1-indexed の配列 \(A[1\dots n]\) を持ち,最も優先度の高い要素を \(A[1]\) に置くとします.

\(A[i]\) はたかだか二つの子 \(A[2i]\), \(A[2i+1]\) を持ちます.すなわち,\(A[i]\) は \(A[\lfloor i/2\rfloor]\) の子になっています.

また,子は親より高い優先度を持っていてはいけません(ヒープ条件).

対象とするデータ型と操作

ここでは,\(1\) から \(n\) までの要素に優先度を割り当てます.優先度の型は任意です.

具体的には,\(i\) の優先度は \(a_i\) とします.

  • \(\mathtt{push}(i, a_i)\)
    • \(i\) の優先度を \(a_i\) で登録する
    • \(i\) はまだ登録されていないとする
  • \(\mathtt{pop}()\)
    • 最も優先度の高い要素を取り除く
  • \(\mathtt{top}()\)
    • 最も優先度の高い要素とその優先度 \( (i, a_i)\) を返す
  • \(\mathtt{prioritize}(i, a_i')\)
    • \(i\) の優先度を \(a_i\) から \(a_i'\) に変更する

データの管理

上に書いた二分ヒープを表す配列 \(A[1\dots n]\) と,補助の配列 \(B[1\dots n]\) を持っておきます.

\(A[j]\) ではペア \( (i, a_i)\) を管理します.

\(B\) は \(A\) の逆引きをするための配列とします. すなわち,\(A[j]\) が \( (i, a_i)\) を管理しているとき,\(B[i] = j\) であるとします.要素 \(i\) が \(A\) のどこで管理されているかを知りたいということです.

push や pop については,通常の二分ヒープの操作を \(A\) に対して行い,それに伴って \(B\) も書き換えます. これは単純な swap などでできます.

prioritize については,まず \(B[i] = j\) を得ます.すなわち,\( (i, a_i)\) は \(A[j]\) で管理されています. よって,\(A[j]\) の優先度を \(a_i'\) に書き換えます.

その後は,通常の二分ヒープの操作を \(A[j]\) から \(A[1]\) への向き(push するときの向き)で順に行えばよいです.

優先度を下げたいときも,たぶん \(A[j]\) から \(A[n]\) への向き(pop するときの向き)で順に行えばよいはずです.

実装

提出コード

Fibonacci ヒープの 37 ms に比べて,(おそらく)オーダーは悪いながら 41 ms と,悪くない速度だと思います.

prioritize をしない普通の二分ヒープでは 114 ms だったので,3 倍くらい速いですね.

おわり

にゃんこひーぷ