なにこれ
前回の続き
今回は話がガラッと変わって、優先度付きキューの実装の話です。
特殊な二分木であるヒープを使います。
ヒープとは「雑多に積まれたもの」という意味があり、今までの「高度に構造化されて積み上げられたもの」であったBinarySearchTree等とは対照的であるそう。
- BinaryHeap
優先度付きキュー
要素の集まりからremoveする際に、最小の値を削除して、返します。
BinaryHeap
完全二分木を配列を使って表現します。
要素がヒープ順に並ぶように補正をかけます。ヒープ順とは各ノードは上位のノードの値以上であるような順番です。
こうすることでindex=0は常に配列の中で最小値となっているため、優先度付きキューを効率的に表現することができます。
- addする場合
- 最後尾に加える
- そしてヒープ性を保つように加えた値と上位のノードの比較を繰り返して上げていく
- removeする場合
- index=0を取り出す
- 最後尾の値をindex=0に置く
- 最後尾の値はだいたい配列の中で大きめの値が入っているはずで、おそらくヒープ性は満たせていないので、index=0の値と下位のノードを比較し下げていく
- 性能
- 完全二分木であり、高さはlog(n)で抑えられているので、add・removeともにO(logn)となる