ヒープ

概要

親ノード<子ノードを満たすような木構造

データを自由に追加できるがデータを取り出すときは最小値から順に取り出される

データの追加にO(logn)

一番下の段に左詰で格納する

親ノードと比較して、親ノード<子ノードが満たされるように値を入れ替える

入れ替え数は最大でも木の高さ→logn

データの取り出しにO(1)

しかし木の再構築にO(logn)かかる

最小値(もしくは最大値)を常に取り出したい場合で使われる

優先度付きキューを実装するのに使われる