ヒープ
ナビゲーションに移動
検索に移動
ヒープとは、「親は自分よりも小さい」ことが保証されている木構造のことである。
概要
すべての要素について、親は自分よりも小さいことが保証されている。最小値を取り出したいときは、根にあたる要素を抜き取り、根の子であった要素のうち小さい方を新しい根とする。 値を追加したいときは、適当な要素の子とし、親子の大小関係が正しくなるまでスワップする。
平衡が保たれるよう適切に実装することで、最小値の取り出しと値の追加がともにO(logN)時間でできるようになる。
用途
いわゆる優先度付きキューと呼ばれるものがこれにあたる。優先度のついた行動フローを順次行うAIの作成などに用いることができる。