概要
概要
ヒープは親子の大小関係だけを保つ構造です。最小値・最大値の取り出しが速く、優先度付きキューの実装に使われます。
データ構造 / Binary Heap（二分ヒープ）
ヒープは親子の大小関係だけを保つ構造です。最小値・最大値の取り出しが速く、優先度付きキューの実装に使われます。
目次
このページでわかること
概要
ヒープは親子の大小関係だけを保つ構造です。最小値・最大値の取り出しが速く、優先度付きキューの実装に使われます。
考え方
push into last position
bubble up
pop root
move last to root and bubble down要点
O(1)
O(log n)
O(log n)
priority queue
補足
左右全体の順序までは保証しません。
根に最小または最大が来るので取り出しが速いです。
木と配列の対応をセットで見せます。
動きで確認
ここでは「何が制約か」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。