二分ヒープ

ヒープの条件

最大ヒープは、どの親の値も子の値以上になっている木です。最大値はいつも根にあります。左右の子のどちらが大きいかは決めません。上の段から左詰めで埋めるので、段数は要素数の対数で済みます [1]。

木を配列に入れる

上の段から順に配列へ並べると、親と子の位置は添字の計算で求まります。子へのポインタは要りません [3]。

記号: $i$ は 0 から数える添字です。

格納

• 1 個ずつ追加: 末尾に入れ、親より大きい間は親と交換する。1 個あたり最大で段数ぶん上がるので $O(\log n)$ [1]
• まとめて構築: 全部を配列へ入れてから、子を持つ要素を下の段から順に直す [2]

まとめて構築では、大半の要素が下の段にあって短い距離しか動きません。高さ $h$ の要素は約 $n/2^{h+1}$ 個で、それぞれ最大 $h$ 回下がります。合計は要素数に比例し、全体で $O(n)$ です [3]。

ソート

根を取り出すと最大値が得られます。空いた根へ末尾の要素を移し、大きいほうの子と交換しながら下げると、条件が元に戻ります。これを全要素に行うと値の大きい順に出て、全体で $O(n\log n)$ です [1]。図の配列のように、取り出した値を末尾から順に置けば、追加の領域なしで並べ替えられます。これがヒープソートです。

d 分ヒープ

子の数を $d$ 個に増やすと段数が減り、追加は速くなります。取り出しでは 1 段ごとに子をすべて比べるので、比較は増えます [4]。計算量の記号はどちらも $O(\log n)$ です。

ポインタでつなぐヒープ

配列に入れず、子へのポインタで木をつなぐヒープです。木どうしのマージが速いので、追加も取り出しもマージで作れます。

• 左傾ヒープ: どの要素でも左の子のほうが右の子より高い。右の枝が短いので、右の枝どうしをマージする [5]
• スキューヒープ: 高さを覚えず、マージのたびに左右の子を入れ替える。1 回は遅くても、続けると対数に収まる [6]
• 二項ヒープ: 大きさが 2 のべきの木を、大きさごとに 1 本ずつ持つ。追加は 2 進数の繰り上がりと同じ動きになる [7]
• ペアリングヒープ: 根どうしを比べて負けたほうを子にするだけ。取り出しのときに、子を 2 個ずつつないでまとめる [8]
• フィボナッチヒープ: 追加は根の列に足すだけで、つなぐ作業を取り出しまで遅らせる。値の変更は切り離すだけで済む [10]

計算量

配列は追加が速く取り出しが遅い構造です。ヒープは追加と取り出しの両方を対数以下に抑えます [3]。* は償却で、操作を続けたときの 1 回あたりを表します。ペアリングヒープの値の変更は厳密な増え方がまだ定まっておらず、上限だけがわかっています [9]。

音

音の高さはバーの高さで決めます。$v$ はバーの値（1〜99）です。

出典

1. ヒープとヒープソートJ. W. J. Williams, Algorithm 232: Heapsort, Communications of the ACM, Vol. 7, No. 6, pp. 347–348, 1964
2. 下の段から直す構築R. W. Floyd, Algorithm 245: Treesort, Communications of the ACM, Vol. 7, No. 12, p. 701, 1964
3. ヒープの性質、構築の計算量、優先度付きキューT. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, Chapter 6
4. d 分ヒープD. B. Johnson, Priority queues with update and finding minimum spanning trees, Information Processing Letters, Vol. 4, No. 3, pp. 53–57, 1975
5. 左傾ヒープC. A. Crane, Linear Lists and Priority Queues as Balanced Binary Trees, Ph.D. thesis, Stanford University, 1972, STAN-CS-72-259
6. スキューヒープD. D. Sleator, R. E. Tarjan, Self-Adjusting Heaps, SIAM Journal on Computing, Vol. 15, No. 1, pp. 52–69, 1986
7. 二項ヒープJ. Vuillemin, A data structure for manipulating priority queues, Communications of the ACM, Vol. 21, No. 4, pp. 309–315, 1978
8. ペアリングヒープM. L. Fredman, R. Sedgewick, D. D. Sleator, R. E. Tarjan, The pairing heap: A new form of self-adjusting heap, Algorithmica, Vol. 1, pp. 111–129, 1986
9. ペアリングヒープの値の変更の計算量S. Pettie, Towards a Final Analysis of Pairing Heaps, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pp. 174–183, 2005
10. フィボナッチヒープM. L. Fredman, R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM, Vol. 34, No. 3, pp. 596–615, 1987

このツールで決めたこと

• 比較は値を比べた回数で、子の中から選ぶ比較も数える
• 移動は要素かポインタを書き込んだ回数で、交換は 1 回と数える
• 確認は根か末尾を読む 1 回を比較に含める
• 値の変更は根に近づく向きに変える。変える場所はわかっているものとし、探す回数は数えない
• 二項ヒープの確認は最良の根を覚えず、根を全部見る
• 格納とソートの回数は工程ごとに 0 から数える
• 二項・ペアリング・フィボナッチヒープのまとめて構築は 1 個ずつ追加と同じ手順にする
• 操作の表の回数は、31 要素の状態から 1 回実行したときの 24 通りのデータの平均。償却の操作は 31 回続けた 1 回あたり
• 一覧の表から操作を選ぶと、要素数の 2/3 を追加した状態から始める
• 配列の図では、取り出した値を末尾から順に置く